c - How to pop from linked list?

Question

I've implemented a Linked-List with a 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 pop would be something like:

Temp is: node1 value
Temp is: node2 value

That is to say that temp is becoming temp->next when I assign *head = *head->next.

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

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

score 3 · Accepted Answer

First, note that your code (and some of the previous solutions) will never pop the last element off the list. You want

if (*head != NULL) ...

Next, passing a pointer to a pointer will work. But it's actually better to make a list header like this:

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 a list like this:

List list[1];

init_list(list);

Declaring an array of one element makes every reference to list a pointer automatically, which eliminates lots of &'s 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 this better? Say you decide later to keep a count of items in the list. With the separate header node this is very easy:

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;
}

Note no calling code needs to change. With the pointer to pointer approach you are at a dead end. There are many other use cases where having a separate list header makes your code more flexible for future changes.

score 2 · Accepted Answer

Your need to pass the address of head for your function to modify it. Then your function needs to dereference this address. Further, the last pop() needs to change *AddressOfHead as well

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

...

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

score 1 · Accepted Answer

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

In order for the value of the node pointer 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 value of *head, because if you are at the last node of the stack and the next node is NULL, you want the list to be NULL anyway.

Karthik T's answer has the right explanation for why the value of temp was changing in your original code.

score 1 · Accepted Answer

Others have told you how to fix it, let me answer why temp changed..

Node * pop (Node * head) {

You are passing head as a pointer to a Node.

Thus when you do

*head = *head->next;

I think it is parsed as

 *head = *(head->next);

And thus COPIES the object that is in next into the object at head, which is ofcourse the same object at temp.

score 0 · Accepted Answer

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

c - How to pop from linked list?

5 回答 5

Related

Reference