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

Answer 1

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.

Answer 2

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