Thread: Creating a Queue using Double Linklist

Which video?

All your &head stuff is plainly wrong.

You start with
head.first = head.last = NULL;

To enqueue, you do this first, to make sure your pointers are initialised.
item->prev = item->next = NULL;


Then you do

Code:

if ( head.first == NULL ) {
  // first in the list
  head.first = head.last = item;
} else {
  // append
  head.last->next = item;  // forward link to the new item
  item->prev = head.last; // back link from the item to the existing tail
  head.last = item;  // the new tail
}

Tutorial - Google Drive

This is the link to the video.

Like I said further videos in this series make use of this tutorial

I cannot access the video. One thing I'd suggest is for you to avoid that global variable named head. In the long run, you might want more than one of these linked lists, so having a global variable is limiting. Furthermore, it encourages sloppy thinking: you don't see your functions as operating on the linked list via its head, but rather just happen to access the head variable. Hence, declare your functions like this:

Code:

void enqueue(LISTHDR *head, LISTITEM *item);
LISTITEM* dequeue(LISTHDR *head);

Now, you can see that you enqueue item into the linked list denoted by head, and you dequeue an item from the linked list denoted by head, returning a pointer to the dequeued item.

EDIT:
Actually, you might find it easier to understand if you named your structs according to what they model, not according to what was used to implement them, e.g.,

Code:

typedef struct QueueItem {
    int data;
    struct QueueItem *next;
    struct QueueItem *prev;
} QueueItem;

typedef struct {
    QueueItem *first;
    QueueItem *last;
} Queue;

void enqueue(Queue *queue, QueueItem *item);
QueueItem* dequeue(Queue *queue);

I guess it helps if you copy the code correctly.

Code:

$ gcc -Wall foo.c
foo.c: In function ‘enqueue’:
foo.c:26:5: warning: statement with no effect [-Wunused-value]
     head.last - item;
     ^

But it still doesn't work.

Code:

$ gcc -Wall foo.c
$ ./a.out 
First element = 6295648
Last element = 2
EMPTY

Try this, which does work, and also removes that messy global variable.

Code:

#include <stdio.h>
#include <stdlib.h>


typedef struct listItem {
    int data;
    struct listItem *next;
    struct listItem *prev;
}LISTITEM;


typedef struct listHDR {
    struct listItem *first;
    struct listItem *last;
}LISTHDR;

void enqueue(LISTHDR *head,LISTITEM *item) {
    if ( head->first == NULL ) {
        head->first = head->last = item;
    } else {
        head->last->next = item;
        item->prev = head->last;
        head->last = item;
    }
}

LISTITEM* dequeue(LISTHDR *head) {
    LISTITEM *temp = NULL;
    if ( head->first ) {
        temp = head->first;
        head->first = temp->next;
        if ( head->first == NULL ) {
            head->last = NULL;
        }
    }
    return temp;
}

int main()
{
    LISTHDR head = { 0, 0 };
    LISTITEM *Temp;
    for(int i = 0; i < 3; i++) {
        Temp = malloc(sizeof(LISTITEM));    //!! no need to cast malloc in C
        Temp->next = NULL;
        Temp->prev = NULL;
        Temp->data = i;
        enqueue(&head,Temp);
    }

    printf("First element = %d\n", head.first->data);
    printf("Last element = %d\n", head.last->data);

    do {
        Temp = dequeue(&head);
        if(Temp != NULL) {
            printf("Data: %d\n", Temp->data);
            free(Temp);
        }
        else {
            printf("EMPTY\n");
        }
    } while(Temp != NULL);

    return 0;
}


$ ./a.out 
First element = 0
Last element = 2
Data: 0
Data: 1
Data: 2
EMPTY

> Like I said further videos in this series make use of this tutorial
Look forward to more mistakes from this author then.

One thing I'd suggest is for you to avoid that global variable named head. In the long run, you might want more than one of these linked lists, so having a global variable is limiting. Furthermore, it encourages sloppy thinking: you don't see your functions as operating on the linked list via its head, but rather just happen to access the head variable. Hence, declare your functions like this:

In coming videos, he's using this method. I tried that code. But first variable is some junk value. I tried to understand his code by makeing a spreadsheet and trying to poin to various address, first variable is always pointing to the address of head that's the value I get when I use

Code:

printf("First element = %d\n", head.first->data)

this. I will try your code.

What I don't understand is how the author getting the answer. Have you seen the video???

Tutorial - Google Drive

Here's the youtube link


YouTube

Originally Posted by Athul

What I don't understand is how the author getting the answer. Have you seen the video???

As I mentioned earlier, I could not access your video. Now that I see it... oh gosh, you mean he actually wrote:

Code:

temp = head.first;
if (temp == (LISTITEM*)&head) // if the head of the queue points to itself ...

This is a terrible idea. LISTITEM and LISTHDR are entirely different structs, so one should not be routinely casting between pointers to them. I don't think the author is actually "getting the answer": the address of head is likely to be the address of its member named first, but that is fundamentally different from the address stored in that member, i.e., the value of head.first. Consequently, if he appears to be "getting the answer", he might be faking it, or perhaps the code that he actually tested is different from what he showed in the video. Either way, I would not recommend this tutorial at all.

What you should be doing is stuff like:

Code:

if (head.first)

because if you code this sensibly, then when the queue is empty, both head.first and head.last will be null pointers.

EDIT:
OHHH... I see now. Look at enqueue:

Code:

item->next = (LISTITEM*)&head;

What this tutorial is doing is basically using (LISTITEM*)&head as a sentinel value, i.e., a special value that denotes the end, but otherwise is not a valid value. It makes no sense, but that's what they are doing. The usual approach is to write:

Code:

item->next = NULL;