How to pop out of a linked list?

Question

I implemented a Linked-List using the Pop function in C:

Node * pop (Node * head) { Node * temp = head; printf("Temp is: %s\n", temp->val); if (head->next != NULL) { *head = *head->next; } printf("Temp is: %s\n", temp->val); return temp; } 

And the output, when I popped up, would be something like:

 Temp is: node1 value Temp is: node2 value 

That is, the tempo becomes temp-> next when I assign *head = *head->next .

So, how can I get the value of the current head and return it while moving the title of the linked list to head->next ?

Doing head = head->next does NOT remove the link to the first node. (i.e. when I print the list, the first node is still there).

Answer 1

You need to pass the head address for your function in order to change it. Then your function should dereference this address. In addition, the last pop () should also change * AddressOfHead

 Node *pop(Node **AddressOfHead) { Node *temp = *AddressOfHead; if (temp) { *AddressOfHead = temp->next; } return temp; } 

...

 // Usage example Node *TopOfList = pop(&Head); 

Answer 2

First, note that your code (and some of the previous solutions) will never infer the last item from the list. Do you want to

 if (*head != NULL) ... 

Further, passing a pointer to a pointer will work. But it’s better to make the list title as follows:

 typedef struct node_s { struct node_s *next; ... data declaration here } Node; typedef struct list_s { struct node_s *head; } List; void init_list(List *list) { list->head = NULL; } 

Now declare the list as follows:

 List list[1]; init_list(list); 

Declaring an array of one element makes each link to list pointer automatically, which excludes a lot of & in your code. Then it's nice and clean to implement push and pop:

 void push(List *list, Node *node) { node->next = list->head; list->head = node; } Node *pop(List *list) { Node *head = list->head; if (head) { list->head = head->next; head->next = NULL; } return head; } 

Why is it better? Say that you later decided to keep the number of items in the list. With a separate node header, this is very simple:

 typedef struct list_s { struct node_s *head; int length; } List; void init_list(List *list) { list->head = NULL; length = 0; } void push(List *list, Node *node) { node->next = list->head; list->head = node; ++list->length; } Node *pop(List *list) { Node *head = list->head; if (head) { list->head = head->next; head->next = NULL; --list->length; } return head; } 

Please note that the call code should not change. With a pointer to a pointer approach, you are at a dead end. There are many other uses where a separate list heading makes your code more flexible for future changes.

Answer 3

Pointers are passed by value. That is, when you pass a pointer to the stack, changing the called function to what the pointer points to is not reflected in the calling function.

In order for the node pointer value to be changed in the calling function, you need to pass the stack as a pointer to a pointer:

 Node* pop (Node** head) { Node* temp = *head; if (temp) { *head = temp->next; // to update stack in calling function temp->next = NULL; // to detach temp from the rest of the list } return temp; } 

You do not need to check if ((*head)->next) or in this case if (temp->next) before updating the *head value, because if you are in the last node of the stack and the next node is NULL , you want so that the list is NULL anyway.

Karthik T's answer has the correct explanation of why temp changed in your source code.

Answer 4

Others told you how to fix this, let me answer why temp has changed ..

 Node * pop (Node * head) { 

You pass head as a pointer to Node .

This way when you do

 *head = *head->next; 

I think it is being analyzed as

  *head = *(head->next); 

And thus COPIES an object that is in the next object in head , which, of course, has the same object in temp .

Answer 5

 void pop(struct node** tol) { struct node* t = *tol; while (t->link->link != NULL){ t = t->link; } t->link = NULL; }