Giorgio M. Giorgio M. - 3 months ago 19
C Question

enqueue function in linked list

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

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.

Comments