Pop Using Linked List Node in DSA Python - Time & Space Complexity

Time Complexity: Pop Using Linked List Node

O(n)

Understanding Time Complexity

We want to understand how long it takes to remove the last item from a linked list.

How does the time needed change as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

def pop(head):
    if head is None:
        return None
    if head.next is None:
        return None  # List becomes empty after pop
    current = head
    while current.next.next is not None:
        current = current.next
    current.next = None
    return head

This code removes the last node from a singly linked list by walking through the list to find the second last node.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves through nodes to find the second last node.
• How many times: It runs once for each node until the second last one, so about n-2 times for a list of size n.

How Execution Grows With Input

As the list gets longer, the loop runs more times, almost once per node.

Input Size (n)	Approx. Operations
10	About 8 steps
100	About 98 steps
1000	About 998 steps

Pattern observation: The number of steps grows roughly in a straight line with the size of the list.

Final Time Complexity

Time Complexity: O(n)

This means the time to pop the last node grows directly with the number of nodes in the list.

Common Mistake

[X] Wrong: "Popping the last node is always quick and takes constant time."

[OK] Correct: Because we must find the second last node by walking through the list, which takes longer as the list grows.

Interview Connect

Understanding this helps you explain why some linked list operations are slower than others and shows you can analyze code carefully.

Self-Check

"What if the linked list kept a pointer to the last node? How would the time complexity of pop change?"