Pop Using Linked List Node in DSA C

Mental Model

Pop means removing the first item from the list and returning it. We change the start pointer to the next item.

Analogy: Imagine a line of people holding hands. To pop, the first person lets go and leaves, so the second person becomes the new first.

head -> 1 -> 2 -> 3 -> null

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> null, pop once

Goal: Remove the first node and update the head to the next node

Step 1: store current head node (1) to return later

head -> [1] -> 2 -> 3 -> null

Why: We keep the first node to return its value after removal

Step 2: move head pointer to next node (2)

head -> [2] -> 3 -> null

Why: The second node becomes the new first node after pop

Step 3: disconnect old head node (1) from list

[1] -> null, head -> 2 -> 3 -> null

Why: Old first node is removed from the list to avoid dangling links

Result:

head -> 2 -> 3 -> null
popped value: 1

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure for linked list
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Function to push a new node at the front
void push(Node** head_ref, int new_data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = new_data;
    new_node->next = *head_ref;
    *head_ref = new_node;
}

// Function to pop the first node and return its data
int pop(Node** head_ref) {
    if (*head_ref == NULL) {
        return -1; // List empty
    }
    Node* temp = *head_ref; // store current head
    int popped_data = temp->data;
    *head_ref = temp->next; // move head to next node
    temp->next = NULL; // disconnect old head
    free(temp); // free memory
    return popped_data;
}

// Function to print the list
void printList(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("null\n");
}

int main() {
    Node* head = NULL;
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);

    printf("Original list: ");
    printList(head);

    int popped = pop(&head);
    printf("Popped value: %d\n", popped);

    printf("List after pop: ");
    printList(head);

    return 0;
}

Node* temp = *head_ref; // store current head

store the first node to return its data later

*head_ref = temp->next; // move head to next node

update head pointer to next node to remove first node

temp->next = NULL; // disconnect old head

disconnect old head from list to avoid dangling pointer

free(temp); // free memory

release memory of removed node

Output

Original list: 1 -> 2 -> 3 -> null

Popped value: 1

List after pop: 2 -> 3 -> null

Complexity Analysis

Time: O(1) because we only remove the first node without traversing the list

Space: O(1) because no extra space is used except temporary pointer

vs Alternative: Compared to removing from the end which requires O(n) traversal, popping from front is faster and simpler

Edge Cases

empty list

pop returns -1 indicating no node to remove

DSA C

if (*head_ref == NULL) { return -1; }

single node list

pop removes the only node and head becomes NULL

DSA C

*head_ref = temp->next; // moves head to NULL

When to Use This Pattern

When you need to remove the first element from a linked list quickly, use the pop pattern to update the head pointer.

Common Mistakes

Mistake: Not updating the head pointer after removing the first node
Fix: Always assign head to head->next to keep list valid

Mistake: Not freeing the removed node's memory
Fix: Call free() on the removed node to avoid memory leaks

Summary

Removes the first node from a linked list and returns its value.

Use when you want to quickly remove the front element of a list.

The key is to move the head pointer to the next node and free the old first node.

Practice

1. What does the pop operation do in a linked list implemented as a stack?

easy

A. Deletes the entire linked list

B. Adds a new node at the end of the linked list

C. Removes and returns the first node (top) of the linked list

D. Returns the last node without removing it

Solution

1. Step 1: Understand pop operation in stack

   Pop removes the top element from the stack, which is the first node in a linked list stack.

2. Step 2: Apply to linked list

   In a linked list used as a stack, the first node is removed and returned during pop.

3. Final Answer:

   Removes and returns the first node (top) of the linked list -> Option C

4. Quick Check:

   Pop = remove first node [OK]

Hint: Pop removes the first node in linked list stack [OK]

Common Mistakes:

• Thinking pop removes last node
• Confusing pop with push
• Assuming pop deletes entire list

2. Which of the following is the correct syntax to pop a node from a linked list stack in C?

easy

A. node* pop(node** head) { node* temp = *head; *head = (*head)->next; return temp; }

B. node pop(node head) { head = head->next; return head; }

C. void pop(node* head) { head = head->next; }

D. node* pop(node* head) { head = head->next; return head; }

Solution

1. Step 1: Check parameter passing for head pointer

   To modify the head pointer, we pass a pointer to pointer (node** head).

2. Step 2: Verify pop logic

   Store current head in temp, move head to next node, return temp node.

3. Final Answer:

   node* pop(node** head) { node* temp = *head; *head = (*head)->next; return temp; } -> Option A

4. Quick Check:

   Pointer to pointer needed to update head [OK]

Hint: Use node** to update head pointer in pop [OK]

Common Mistakes:

• Passing head by value instead of pointer to pointer
• Returning wrong node or void
• Not updating head pointer correctly

3. What will be the output of the following code snippet?

typedef struct node { int data; struct node* next; } node;

node* pop(node** head) {
  if (*head == NULL) return NULL;
  node* temp = *head;
  *head = (*head)->next;
  return temp;
}

int main() {
  node n3 = {3, NULL};
  node n2 = {2, &n3};
  node n1 = {1, &n2};
  node* head = &n1;
  node* popped = pop(&head);
  printf("%d -> %d -> %d -> NULL", head->data, head->next->data, head->next->next->data);
  return 0;
}

medium

A. 2 -> 3 -> 0 -> NULL

B. 2 -> 3 -> NULL -> NULL

C. 2 -> 3 -> NULL

D. 2 -> 3 -> (segmentation fault)

Solution

1. Step 1: Trace pop operation

   Pop removes node with data 1, head now points to node with data 2.

2. Step 2: Trace printf arguments

   head->data = 2, head->next->data = 3, head->next->next = NULL, accessing ->data causes segmentation fault after printing "2 -> 3 -> " .

3. Final Answer:

   2 -> 3 -> (segmentation fault) -> Option D

4. Quick Check:

   Accessing NULL->data causes crash [OK]

Hint: Accessing next of last node causes crash [OK]

Common Mistakes:

• Assuming NULL prints as 'NULL' string
• Ignoring segmentation fault on NULL dereference
• Misreading linked list after pop

4. Identify the bug in this pop function and select the correct fix:

node* pop(node* head) {
  node* temp = head;
  head = head->next;
  return temp;
}

medium

A. Pass head as node** and update *head inside function

B. Return head instead of temp

C. Set temp->next = NULL before return

D. No bug, function is correct

Solution

1. Step 1: Analyze head pointer update

   Function updates local copy of head, original head outside remains unchanged.

2. Step 2: Fix pointer update

   Pass pointer to pointer (node**) to modify original head pointer.

3. Final Answer:

   Pass head as node** and update *head inside function -> Option A

4. Quick Check:

   Use node** to update head pointer [OK]

Hint: Use node** to update head pointer in pop [OK]

Common Mistakes:

• Updating local copy of head only
• Not passing pointer to pointer
• Returning wrong node

5. Given a linked list stack with nodes containing integers, write the logic to pop all nodes and print their data in order. Which approach is correct?

hard

A. Traverse list without popping and print data

B. Use a loop: while head != NULL, pop node, print data, free node

C. Pop once, print data, then stop

D. Recursively call pop until head is NULL, then print all data after recursion

Solution

1. Step 1: Understand popping all nodes

   Pop removes top node each time, so loop until list is empty.

2. Step 2: Print and free nodes in loop

   Print data of popped node immediately, then free memory to avoid leaks.

3. Final Answer:

   Use a loop: while head != NULL, pop node, print data, free node -> Option B

4. Quick Check:

   Loop pop-print-free until empty [OK]

Hint: Loop pop until head NULL, print and free each node [OK]

Common Mistakes:

• Recursing without printing in correct order
• Not freeing nodes causing memory leaks
• Stopping after one pop