enqueue function in linked list

Question

I'm trying to understand the function "enqueue" my professor did but i don't get some steps.

struct queue_node {
int item;
struct queue_node* next;
};
typedef struct queue_node* queue;


int enqueue (queue* tail, int i) {
queue n;
queue *iter;
n = (queue)malloc(sizeof(struct queue_node));
if (!n) return 1;
n->item = i;
n->next = NULL;
for (iter=tail; *iter != NULL; iter = &((*iter)->next)
;
*iter = n;
return 0;
}

First of all that "typedef struct queue_node* queue;" is confusing me so i tried to reinterpret the code this way (please correct the code if i'm wrong)

struct queue_node {
int item;
struct queue_node* next;
};
typedef struct queue_node queue;

int enqueue (queue **tail, int i) {
queue *n;
queue **iter;
n = (queue)malloc(sizeof(struct queue_node));
if (!n) return 1; --->what does that mean?
n->item = i;
n->next = NULL;
for (iter=tail; **iter != NULL; iter = &((*iter)->next)--->last part of the for is unclear to me... can i rewrite it as "iter = **((iter)->next)"?
;
*iter = n; -->this is the part i don't really get...
return 0;
}

So by the way before trying to read the solution of my professor i tried to do an "enqueue" function on my own

typedef struct node{
int value;
struct node *next;
}node;

void enqueue(node *head,int data){
if(head->next != NULL){
enqueue(head->next,data);
}
node *new=NULL;
new=malloc(sizeof(node));
new->value=data;
new->next=NULL;
head->next=new;
}

Is this good? or i can't use it? Thank you all in advance for the help

Answer 1

If to use your definition of the queue

struct queue_node 
{
    int item;
    struct queue_node *next;
};

typedef struct queue_node queue;

then the function will look the following way.

int enqueue( queue **tail, int item ) 
{
    queue *node = ( queue * )malloc( sizeof( queue ) );
    int success = node != NULL;

    if ( success )
    {
        node->item = item;
        node->next = NULL;

        while ( *tail != NULL ) tail = &( *tail )->next;

        *tail = node;
    }

    return success;
}

Opposite to your function definition this function returns 1 in case of the success that is when the new node that will be appended to the queue is allocated successfully and 0 otherwise.

So if you declared a queue the following way

queue *head = NULL;

then a function call can look like

enqueue( &head, value );

where value is some integer expression.

As you see you need to pass the head of the queue indirectly using pointers. Otherwise if not to use pointers and to pass the head directly to the function then the function gets a copy of the head. So any changes of the copy in the function will not influence on the original head.

In this statement

    queue *node = ( queue * )malloc( sizeof( queue ) );

a new node is created. The function malloc returns pointer to the allocated dynamically node.

In this statement

    int success = node != NULL;

there is assigned the result of the expression node != NULL (either 1 or 0) depending on whether the call of malloc was successful or not.

If the call of malloc was successful that is node is not equal to NULL then the new node is initialized and it is appended to the end of the queue. if ( success ) { node->item = item; node->next = NULL;

        while ( *tail != NULL ) tail = &( *tail )->next;

        *tail = node;
    }

How to find the tail of the list?

If the list initially was empty then *tail is equal to NULL and the condition on the while *tail != NULL will be equal to false. So the current value of the tail that is equal to NULL is substituted for the address of the allocated node

*tail = node;

Otherwise if *tail is not equal to NULL we gets the data field next of the current node

( *tail )->next

and in turn take its address the same way as we passed the head to the function by reference

&( *tail )->next

AT last when this data field contains NULL we substitute this NULL for the address of the new created node.

if you want to write a recursive function that appends a new node to the queue then it can look like

typedef struct node
{
    int value;
    struct node *next;
} node;

void enqueue( node **tail, int data )
{
    if ( *tail != NULL )
    { 
        enqueue( &( *tail )->next, data );
    }
    else
    {
        node *tmp = malloc( sizeof( node ) );
        tmp->value = data;
        tmp->next = NULL;

        *tail = tmp;
    }
}

Answer 2

You and your professor are basically treating the variables differently. Based on then naming I think the professor is aiming for a picture that looks kind of like this:

The tail pointer refers to that rightmost node you would dequeue from, and to get to the location that you enqueue, you iterate until you reach the front of the queue. Now the important thing to note here is that iter does not point directly to nodes, it points to the next cells within each node until it finds an NULL one, as I try to illustrate here.

I think in practice you are right with not wanting to loop through the queue just to add a node. Actual queue implementations (which are sometimes made using linked lists) want constant time O(1) enqueues and dequeues, so they hold on to a pointer to either end of the queue at all times.

On a final note, everyone has different opinions about C naming conventions, but I tend to agree with you that the professor's example had some confusing typedefs. Some code bases like the linux kernel recommend to not use typedefs at all for pointers or even structs.

Answer 3

The typedef struct queue_node* queue;defines a new type so that you can write

queue* myqueue = (queue*)malloc(sizeof(struct queue_node));

instead of

struct queue_node** myqueue = (struct queue_node**)malloc(sizeof(struct queue_node));

As pointed out in the comment this is a pointer-to-pointer type.

The line

if (!n) return 1;

tests if the pointer n is valid (i.e. not NULL) and returns 1 as an error code if the comparison fails.

Now the code

for (iter=tail; **iter != NULL; iter = &((*iter)->next)
{
    *iter = n; /* -->this is the part i don't really get... */
    return 0;
}

iterates over the list until you encounter a NULL pointer. The line *iter = n; dereferences the current iterator (in this case a pointer to the current node and assigns n to it. So this essentially searches for the end of the queue and assigns the the new element to the end.

**((iter)->next) 

is not the same as

&((*iter)->next)

the statement (*iter)->next dereferences iter which is a pointer to a pointer to a struct queue_node so that you only have the actual pointer to queue. Then it gets the next field from the queue. The & gives you a pointer to the element that is referenced by next (it is the address operator), whereas your code will give you the actual object that is referenced by ->next.

Now for you're code:

void enqueue(node *head,int data)
{
    if(head->next != NULL) /* what happens if head is  NULL ?*/
    {
         enqueue(head->next,data);
    }
    node *new=NULL;
    new=malloc(sizeof(node));
    new->value=data;
    new->next=NULL;
    head->next=new;
}

Other than my comment at the beginning I can't see anything wrong with it. But I have not actually tested if the code runs ;)

I hope that makes things clearer. :) If there are any ambiguities with my explanation, please comment and do not simply downvote, I know I am not the most experienced C programmer.