Linked List Traversal and Insertion

A linked list is a chain of individually allocated nodes, where each node stores a value and a reference (a pointer) to the next node in the chain. Unlike a Python list, which is backed by one contiguous block of memory, a linked list’s nodes can live anywhere in memory — the only thing holding them together is these next-pointers. This lesson covers the two operations you’ll use constantly when working with linked lists: traversal (walking the chain from the head to the end) and insertion (adding a new node at the head, tail, or somewhere in the middle).

Overview: How Linked Lists Work

Every singly linked list is built from a simple building block, a Node, that holds a value and a next reference pointing at the following node (or None if it’s the last node). The list itself is just a single reference to the first node, called the head. There is no index you can jump to directly — to reach the fifth node you must walk through the first four, following each next pointer in turn. That’s the fundamental trade-off of a linked list versus a Python list (really a dynamic array): you give up O(1) random access by index in exchange for O(1) insertion and deletion once you already have a reference to the right spot, with no need to shift every following element.

Picture a scavenger hunt where each clue tells you where to find the next one: you can’t skip to clue 5 without having read clues 1 through 4, because clue 4 is the only thing that tells you where clue 5 is. That’s traversal — starting at the head and following next pointers until you hit None. Insertion means splicing a brand-new node into that chain of clues: you create the new node, point its next at whatever used to come next, and then repoint the previous link at the new node. Get the order of those two steps wrong and you’ll drop the rest of the list on the floor — more on that in Common Mistakes.

There are three insertion positions worth knowing by name:

• Insert at head — the new node becomes the first node. This is always O(1): create the node with its next pointing at the old head, then update the head reference.
• Insert at tail — the new node becomes the last node. Without a tracked tail reference this requires traversing the whole list first to find the current last node, making it O(n).
• Insert in the middle (at an index, or after a given node) — requires traversing to the insertion point, then relinking two pointers.

Time and Space Complexity

The table below breaks down every operation covered in this lesson. n is the number of nodes in the list.

Operation	Time Complexity	Why
Traverse the full list	O(n)	Every node must be visited exactly once by following next pointers; there is no shortcut.
Access the value at index i	O(n)	There’s no random access — reaching index i means walking i pointers from the head.
Insert at head	O(1)	Only the head reference and the new node’s next pointer change; nothing shifts.
Insert at tail (no tail reference kept)	O(n)	You must traverse to the last node before you can attach the new one.
Insert at tail (tail reference kept)	O(1)	You already hold a direct reference to the last node.
Insert after a node you already have a reference to	O(1)	Relinking two pointers doesn’t depend on list length.
Insert at an arbitrary index	O(n)	Reaching the insertion point requires traversing up to that index first.

Space complexity for a single insertion is O(1) extra (one new node object), and the list as a whole uses O(n) space for n nodes, plus a bit of per-node pointer overhead — the price paid for not needing contiguous memory. Compare this to a Python list: appending is O(1) amortized and indexing is O(1), but inserting or deleting at the front is O(n) because every remaining element has to shift over. That’s precisely the gap a linked list closes.

Examples

Example 1: Building a List by Hand and Traversing It

The simplest way to understand traversal is to build a tiny list by hand, wiring the next pointers together directly, and then walk it with a loop.

class Node:
    def __init__(self, value: int, next: "Node | None" = None) -> None:
        self.value = value
        self.next = next


def traverse(head: "Node | None") -> list[int]:
    values = []
    current = head
    while current is not None:
        values.append(current.value)
        current = current.next
    return values


# Build the list 10 -> 20 -> 30 manually
third = Node(30)
second = Node(20, third)
head = Node(10, second)

print(traverse(head))

Output:

[10, 20, 30]

traverse starts with current = head (the node holding 10). Each iteration appends current.value to the values list and then moves current to current.next. It appends 10, then 20, then 30; on the fourth iteration current is None (since the last node’s next was never set, defaulting to None), so the loop exits and [10, 20, 30] is returned and printed.

Example 2: A LinkedList Class with Head, Tail, and Positional Insertion

A real linked list is usually wrapped in a class that tracks the head and exposes insertion methods. This example builds a list by appending to the tail three times, inserting at the head once, and then inserting at a specific index.

class Node:
    def __init__(self, value: int, next: "Node | None" = None) -> None:
        self.value = value
        self.next = next


class LinkedList:
    def __init__(self) -> None:
        self.head: "Node | None" = None

    def insert_at_head(self, value: int) -> None:
        self.head = Node(value, self.head)

    def insert_at_tail(self, value: int) -> None:
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            return
        current = self.head
        while current.next is not None:
            current = current.next
        current.next = new_node

    def insert_at(self, index: int, value: int) -> None:
        if index == 0:
            self.insert_at_head(value)
            return
        current = self.head
        position = 0
        while current is not None and position < index - 1:
            current = current.next
            position += 1
        if current is None:
            raise IndexError("index out of range")
        current.next = Node(value, current.next)

    def to_list(self) -> list[int]:
        values = []
        current = self.head
        while current is not None:
            values.append(current.value)
            current = current.next
        return values


linked_list = LinkedList()
linked_list.insert_at_tail(1)
linked_list.insert_at_tail(2)
linked_list.insert_at_tail(4)
linked_list.insert_at_head(0)
linked_list.insert_at(3, 3)

print(linked_list.to_list())

Output:

[0, 1, 2, 3, 4]

The tail inserts build 1 -> 2 -> 4 one node at a time — each call to insert_at_tail traverses to the current last node before attaching the new one. insert_at_head(0) then makes 0 the new first node in O(1), giving 0 -> 1 -> 2 -> 4. Finally insert_at(3, 3) walks to the node just before index 3 and splices in 3, producing 0 -> 1 -> 2 -> 3 -> 4 — matching the printed output [0, 1, 2, 3, 4]. See the step-by-step section below for a pointer-by-pointer walk of that last call.

Example 3: Traversal-Driven Insertion — Insert After a Target Value

Insertion often depends on a value you find by searching, not a fixed index. This example traverses the list looking for a target value and splices a new node in right after it.

class Node:
    def __init__(self, value: int, next: "Node | None" = None) -> None:
        self.value = value
        self.next = next


def insert_after_value(head: "Node | None", target: int, value: int) -> "Node | None":
    current = head
    while current is not None:
        if current.value == target:
            current.next = Node(value, current.next)
            return head
        current = current.next
    raise ValueError(f"{target} not found in list")


def to_list(head: "Node | None") -> list[int]:
    values = []
    current = head
    while current is not None:
        values.append(current.value)
        current = current.next
    return values


# Build 5 -> 10 -> 15
head = Node(5, Node(10, Node(15)))
head = insert_after_value(head, 10, 12)

print(to_list(head))

Output:

[5, 10, 12, 15]

insert_after_value walks the list comparing each node’s value to target. It skips past 5 (no match), finds 10 matches, and immediately builds Node(12, current.next) — capturing the old next (the node holding 15) before overwriting current.next to point at the new node. The result is 5 -> 10 -> 12 -> 15, printed as [5, 10, 12, 15]. If no node matched target, the function would fall through the loop and raise a ValueError instead of silently doing nothing.

How It Works, Step by Step

Let’s trace the insert_at(3, 3) call from Example 2 in detail. Before the call, the list holds 0 -> 1 -> 2 -> 4, and we want to insert the value 3 at index 3 (so it ends up between 2 and 4).

1. index is 3, which is not 0, so we skip the head-insertion shortcut and start walking from current = self.head (the node holding 0), with position = 0.
2. Loop check: position (0) < index - 1 (2) is true, so we advance: current moves to the node holding 1, and position becomes 1.
3. Loop check again: position (1) < 2 is still true, so we advance again: current moves to the node holding 2, and position becomes 2.
4. Loop check again: position (2) < 2 is now false, so the loop stops. current is sitting on the node holding 2 — exactly one node before where the new value belongs.
5. We build the new node with Node(3, current.next). At this moment current.next is the node holding 4, so the new node’s next is set to point at 4 before anything else changes.
6. Finally, current.next = <new node> repoints the node holding 2 at the new node holding 3. The chain is now 0 -> 1 -> 2 -> 3 -> 4, with nothing lost, because step 5 captured the old next pointer before step 6 overwrote it.

Notice the pattern: the loop always stops one node before the target index, because insertion requires rewriting the next pointer of the node that comes right before the new one. This “stop one early” logic is exactly why off-by-one errors are so common in linked-list code — always double check whether your loop should stop at the target node or the node just before it.

Common Mistakes

Mistake 1: Losing the Rest of the List When Inserting at the Head

A very common bug is creating a new node and reassigning head to it without pointing the new node’s next at the old head first. Once that happens, nothing in the program references the old chain anymore, and the rest of the list is effectively gone.

def insert_at_head_buggy(head: "Node | None", value: int) -> "Node | None":
    new_node = Node(value)
    head = new_node          # bug: new_node.next was never linked to the old head
    return head

The fix is to build the link in the right order: pass the current head as the new node’s next at construction time, so the new node is already wired into the chain before it becomes the head.

def insert_at_head_fixed(head: "Node | None", value: int) -> "Node | None":
    new_node = Node(value, head)   # link to the rest of the list first
    return new_node

Mistake 2: An Off-by-One Loop Condition During Traversal

It’s tempting to write the traversal condition as while current.next is not None instead of while current is not None. This is wrong in two ways: it raises AttributeError: 'NoneType' object has no attribute 'next' if the list is empty (head is None), and even on a non-empty list it stops one node too early, because the loop exits as soon as current reaches the last node (whose next is None) — so that last node’s value never gets appended.

def to_list_buggy(head: "Node | None") -> list[int]:
    values = []
    current = head
    while current.next is not None:   # bug: crashes if head is None, and stops one node early
        values.append(current.value)
        current = current.next
    return values

Checking current itself, not current.next, fixes both problems: the loop naturally does nothing on an empty list, and it processes every node, including the last one, before stopping.

def to_list_fixed(head: "Node | None") -> list[int]:
    values = []
    current = head
    while current is not None:
        values.append(current.value)
        current = current.next
    return values

Best Practices

• Always use a separate current variable to walk the list — never reassign head itself during traversal, or you’ll lose the only reference to the start of the list.
• When inserting, link the new node’s next pointer before repointing the previous node (or the head) at it. Getting this order backwards silently drops part of the list.
• If your code frequently inserts at the tail, keep a dedicated tail reference so tail insertion is O(1) instead of O(n).
• Handle the empty-list case (head is None) explicitly wherever you insert or traverse — it’s the edge case most linked-list bugs come from.
• For production code that just needs a general-purpose double-ended queue or list-like structure, reach for collections.deque rather than hand-rolling nodes — it’s implemented in C, supports O(1) appends and pops from both ends, and hand-rolled linked lists are mainly valuable for learning the mechanics or for specific structures (like the internal list of an LRU cache) where you need direct control over individual nodes.
• Avoid recursive traversal on lists that might be long — Python’s default recursion limit (around 1000) means a recursive walk over thousands of nodes will raise RecursionError; use an iterative while loop instead.

Practice Exercises

1. Length without recursion: Write def length(head: "Node | None") -> int: that returns the number of nodes in a linked list using iteration, not recursion. Test it on the list 10 -> 20 -> 30 and confirm it prints 3.
2. Insert before a value: Write def insert_before_value(head, target, value) that inserts a new node immediately before the first node containing target. This is trickier than inserting after, because a singly linked list has no way to look backwards — think about what you need to track as you traverse.
3. Safe positional insert: Modify the insert_at method from Example 2 so that if index is greater than the length of the list, it inserts the value at the end instead of raising IndexError. Verify it on a 3-node list with index=10.

Summary

• A linked list is a chain of Node objects, each holding a value and a next reference; the list is accessed only through its head.
• Traversal means following next pointers from head until reaching None, visiting every node exactly once — O(n) time, O(1) extra space.
• Insertion at the head is O(1); insertion at the tail is O(n) without a tracked tail reference, or O(1) with one; insertion at an arbitrary position is O(n) because reaching that position requires traversal first.
• Always link a new node’s next pointer before repointing the previous link — reversing that order drops the rest of the list.
• Traverse with a separate current variable and a while current is not None condition to avoid both crashing on empty lists and skipping the last node.
• Reach for collections.deque in real production code; build nodes by hand mainly to learn the mechanics or when you need fine-grained control over individual nodes.