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).

Solution 1

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

Solution 2

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.

Solution 3

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.

Solution 4

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.

View more solutions

Comments

[Gene]

@Travv92 Test carefully. If you are starting with a NULL head and pushing nodes, this will never pop the last node.

[verbose]

@Gene could you explain why that might happen? I have some code here that does appear to pop the last nodes correctly: ideone.com/tVYck0. (Please ignore the fact I have not freed allocated memory there)

[Gene]

@verbose Someone fixed the problem! It's fine now. I still think using the pointer-to-pointer rather than a real list head makes the code brittle.

[chux - Reinstate Monica]

@Gene pros & cons either way. Having a Head structure can be useful. Having a head structure with a length provides quick length assessment should something more than non-zero-ness be needed. Also useful for other tagged information. Head structure w/length is redundant as the list is NULL terminated and coherency becomes an issue. Head w/length takes 2x space. This is significant when there may be a significant majority of empty lists. BTW: my son was recently on the Plain for A-Day.

[Gene]

@chux Okay, but four bytes are seldom decisive, whereas changing a gazillion list ops to a new convention often is. If you like headless lists, you should use go circular with the external pointer P being to the tail so P->next is the head. Then you get a queue for free. Congrats on your plebe. We may have him in IT105. If not, then next semester.

[chux - Reinstate Monica]

@Gene Totally agree about circular queue - FIFO and stack in same class. Didn't think OP was ready yet. GABN!

[carloswm85]

You "think"? So, you were not sure about what you were answering.