Pop Using Linked List Node in DSA Python

Mental Model

Pop means removing the last item from a linked list and returning it. We find the second last node and cut off the last node.

Analogy: Imagine a chain of paper clips linked together. To remove the last clip, you hold the second last clip and unhook the last one.

head -> 1 -> 2 -> 3 -> null
                 ↑
               tail

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 second last node to remove the last

Step 2: move to next node (2)

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

Why: Check if next node is last; if yes, we can pop

Step 3: next node (3) is last, so set node 2's next to null

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

Why: Cut off last node by removing reference from second last

Result:

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

Annotated Code

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, val):
        new_node = Node(val)
        if not self.head:
            self.head = new_node
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node

    def pop(self):
        if not self.head:
            return None  # empty list
        if not self.head.next:
            val = self.head.val
            self.head = None
            return val
        curr = self.head
        while curr.next.next:
            curr = curr.next  # advance to second last node
        val = curr.next.val
        curr.next = None  # remove last node
        return val

    def __str__(self):
        vals = []
        curr = self.head
        while curr:
            vals.append(str(curr.val))
            curr = curr.next
        return ' -> '.join(vals) + ' -> null'

# Driver code
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
print("Before pop:", ll)
popped_value = ll.pop()
print("Popped node value:", popped_value)
print("After pop:", ll)

if not self.head: return None # empty list

handle empty list case by returning None

if not self.head.next: val = self.head.val self.head = None return val

handle single node list by removing head and returning its value

while curr.next.next: curr = curr.next # advance to second last node

move curr to second last node to prepare for pop

val = curr.next.val curr.next = None # remove last node return val

store last node value, remove last node by cutting link, return value

Output

Before pop: 1 -> 2 -> 3 -> null

Popped node value: 3

After pop: 1 -> 2 -> null

Complexity Analysis

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

Space: O(1) because we only use a few pointers, no extra space grows with input

vs Alternative: Compared to arrays where pop from end is O(1), linked list pop requires traversal O(n) because no direct access to last node

Edge Cases

empty list

pop returns None without error

DSA Python

if not self.head:
    return None  # empty list

single node list

pop removes the only node and sets head to None

DSA Python

if not self.head.next:
    val = self.head.val
    self.head = None
    return val

When to Use This Pattern

When you need to remove the last element from a singly linked list, use the pop pattern by finding the second last node and cutting off the last.

Common Mistakes

Mistake: Trying to pop by moving to the last node directly and setting it to None
Fix: Move to the second last node and set its next pointer to None to remove last node

Mistake: Not handling empty or single node list cases causing errors
Fix: Add checks for empty list and single node list before traversal

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 access to head.

You must find the second last node to cut off the last node since singly linked lists have no backward pointers.