Pop Using Linked List Node in DSA C++

Mental Model

Pop removes the last item from a linked list by unlinking the last node and returning its value.

Analogy: Imagine a chain of paper clips linked together. To remove the last clip, you unhook it from the one before it, leaving the rest connected.

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

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> null, pop last node

Goal: Remove the last node (3) and update the list to end at node 2

Step 1: start at head node (1)

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

Why: We need to find the node before the last to unlink the last node

Step 2: move to next node (2)

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

Why: Keep moving until the next node is the last node

Step 3: detect next node (3) is last node (next is null)

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

Why: Node 2 is the one before last, so we can unlink last node

Step 4: unlink last node by setting node 2's next to null

head -> 1 -> 2 -> null

Why: Removing last node from list by breaking its link

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <stdexcept>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {}

    void push(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = newNode;
            return;
        }
        Node* curr = head;
        while (curr->next) {
            curr = curr->next;
        }
        curr->next = newNode;
    }

    int pop() {
        if (!head) {
            throw runtime_error("Pop from empty list");
        }
        if (!head->next) {
            int val = head->data;
            delete head;
            head = nullptr;
            return val;
        }
        Node* curr = head;
        while (curr->next->next) {
            curr = curr->next;
        }
        int val = curr->next->data;
        delete curr->next;
        curr->next = nullptr;
        return val;
    }

    void printList() {
        Node* curr = head;
        while (curr) {
            cout << curr->data;
            if (curr->next) cout << " -> ";
            curr = curr->next;
        }
        cout << " -> null" << endl;
    }
};

int main() {
    LinkedList list;
    list.push(1);
    list.push(2);
    list.push(3);
    list.printList();
    int popped = list.pop();
    cout << "Popped value: " << popped << endl;
    list.printList();
    return 0;
}

while (curr->next->next) { curr = curr->next; }

advance curr to node before last to unlink last node

int val = curr->next->data;

store last node's value before removal

delete curr->next; curr->next = nullptr;

unlink and delete last node to pop it

Output

1 -> 2 -> 3 -> null

Popped value: 3

1 -> 2 -> null

Complexity Analysis

Time: O(n) because we traverse the list to find the node before the last

Space: O(1) because we only use a few pointers regardless of list size

vs Alternative: Compared to using a doubly linked list where pop can be O(1), singly linked list pop requires traversal making it O(n)

Edge Cases

empty list

throws runtime error to prevent popping from empty list

DSA C++

if (!head) { throw runtime_error("Pop from empty list"); }

single element list

removes the only node and sets head to null

DSA C++

if (!head->next) { int val = head->data; delete head; head = nullptr; return val; }

When to Use This Pattern

When you need to remove the last element from a singly linked list, use pop by traversing to the node before last and unlinking the last node.

Common Mistakes

Mistake: Trying to pop without checking if the list is empty or has one node
Fix: Add checks for empty list and single node list before traversal

Mistake: Not updating the second last node's next pointer to null after deleting last node
Fix: Set curr->next to nullptr after deleting last node to properly unlink

Summary

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

Use when you want to remove the tail element but only have a singly linked list.

You must find the node before the last to unlink the last node safely.

Practice

1. What does the pop() operation do in a linked list when implemented using nodes?

easy

A. Removes the first node and returns its value

B. Adds a new node at the end

C. Deletes all nodes in the list

D. Finds a node with a specific value

Solution

1. Step 1: Understand pop operation in linked list context

   Pop means removing the top or first element from the list, similar to popping from a stack.

2. Step 2: Identify what happens to the first node

   The first node is removed and its value is returned, and the head pointer moves to the next node.

3. Final Answer:

   Removes the first node and returns its value -> Option A

4. Quick Check:

   Pop = Remove first node [OK]

Hint: Pop removes the first node like taking the top card [OK]

Common Mistakes:

• Thinking pop adds a node
• Confusing pop with delete all
• Assuming pop searches for a value

2. Which of the following is the correct syntax to remove the first node in a singly linked list in C++?

easy

A. delete head->next;

B. head->next = head;

C. head = head->next;

D. head = NULL;

Solution

1. Step 1: Understand how to move head pointer

   To remove the first node, head must point to the second node, which is head->next.

2. Step 2: Check each option

   head = head->next; correctly assigns head to head->next. head->next = head; reverses pointers incorrectly. delete head->next; deletes the second node, not the first. head = NULL; sets head to NULL, deleting entire list.

3. Final Answer:

   head = head->next; -> Option C

4. Quick Check:

   Move head to next node = head = head->next; [OK]

Hint: Pop means head points to next node [OK]

Common Mistakes:

• Deleting wrong node
• Setting head to NULL incorrectly
• Reversing pointer assignment

3. What will be the output after executing the following code?

struct Node {
  int data;
  Node* next;
};

Node* head = new Node{10, nullptr};
head->next = new Node{20, nullptr};

int popValue = head->data;
head = head->next;

std::cout << popValue << " -> " << (head ? std::to_string(head->data) : "null") << std::endl;

medium

A. 20 -> 10

B. 10 -> 20

C. 10 -> null

D. 20 -> null

Solution

1. Step 1: Trace initial list nodes

   head points to node with data 10, which points to node with data 20.

2. Step 2: Execute pop operation

   popValue stores 10 (head's data), then head moves to next node (20).

3. Step 3: Print values

   Output prints popValue (10) and head's data (20), separated by ' -> '.

4. Final Answer:

   10 -> 20 -> Option B

5. Quick Check:

   Pop value = 10, new head = 20 [OK]

Hint: Pop returns old head data, head moves to next node [OK]

Common Mistakes:

• Printing new head data as pop value
• Confusing order of output
• Not updating head pointer

4. Identify the error in the following pop function for a singly linked list:

int pop(Node*& head) {
  int val = head->data;
  delete head;
  head = head->next;
  return val;
}

medium

A. Accessing head->next after deleting head

B. Not checking if head is NULL before pop

C. Returning value before deleting node

D. Function should return void

Solution

1. Step 1: Analyze order of operations

   The code deletes head node first, then tries to access head->next, which is invalid after deletion.

2. Step 2: Identify correct order

   Must save head->next before deleting head to avoid accessing freed memory.

3. Final Answer:

   Accessing head->next after deleting head -> Option A

4. Quick Check:

   Delete before accessing next = error [OK]

Hint: Save next pointer before deleting node [OK]

Common Mistakes:

• Deleting node before saving next
• Ignoring NULL head check
• Wrong return type assumption

5. Given a linked list with nodes containing values [5, 10, 15], write the correct sequence of operations to pop all nodes and print their values in order using C++ pointers.
Which code snippet correctly implements this?

hard

A. while(head) { int val = head->data; head = head->next; std::cout << val << " "; }

B. while(head) { std::cout << head->data << " "; delete head; }

C. while(head) { delete head; head = head->next; }

D. while(head) { int val = head->data; Node* temp = head; head = head->next; delete temp; std::cout << val << " "; }

Solution

1. Step 1: Understand safe pop and print

   We must print the current node's data, save the current node pointer, move head to next, then delete the saved node.

2. Step 2: Check each option

   while(head) { int val = head->data; head = head->next; std::cout << val << " "; } does not delete nodes, causing memory leak. while(head) { int val = head->data; Node* temp = head; head = head->next; delete temp; std::cout << val << " "; } correctly saves node in temp, moves head, deletes temp, and prints value. while(head) { delete head; head = head->next; } deletes head before moving, causing invalid access. while(head) { std::cout << head->data << " "; delete head; } deletes head but does not move head pointer, causing infinite loop or crash.

3. Final Answer:

   while(head) { int val = head->data; Node* temp = head; head = head->next; delete temp; std::cout << val << " "; } -> Option D

4. Quick Check:

   Save node, move head, delete node, print value [OK]

Hint: Save node before delete, move head after [OK]

Common Mistakes:

• Deleting node before moving head
• Not deleting nodes causing leaks
• Not moving head pointer