Linked Lists

Why linked lists exist#

The previous page ended on a specific pain point: inserting or deleting at the front of an array costs O(n), because every existing element has to physically shift over. A linked list solves exactly this problem by giving up the array's "all elements sit next to each other in memory" property in exchange for cheap insertion and deletion anywhere, as long as you already have a reference to the right spot.

Analogy: think of a treasure hunt where each clue tells you where to find the next clue, rather than a numbered map where you can jump straight to clue #7. You can't skip ahead — you have to follow the chain from the start — but inserting a brand new clue into the middle of the hunt is trivial: you just change what one clue points to. No other clue needs to move.

Node structure#

A linked list is built from nodes. Each node holds a piece of data plus a reference ("pointer") to the next node in the chain. In a singly linked list, that's the entire structure — each node points forward, one direction only:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None    # reference to the next node; None means "end of the list"

A doubly linked list adds a second pointer per node, pointing backward to the previous node as well:

class DoublyNode:
    def __init__(self, value):
        self.value = value
        self.next = None    # reference forward
        self.prev = None    # reference backward

That second pointer costs a bit of extra memory per node, but it buys you the ability to traverse backward and to delete a node in O(1) once you're holding a reference to it (you don't need to walk from the head to find its predecessor — node.prev already knows it).

A complete singly linked list implementation#

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


class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    def push_front(self, value):
        """Insert at the front — O(1), no shifting required."""
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node
        self.size += 1

    def push_back(self, value):
        """Insert at the end — O(n), since we must walk to the last node."""
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next is not None:
                current = current.next
            current.next = new_node
        self.size += 1

    def delete_value(self, value):
        """Delete the first node holding this value — O(n) to find it."""
        if self.head is None:
            return False

        if self.head.value == value:
            self.head = self.head.next
            self.size -= 1
            return True

        current = self.head
        while current.next is not None:
            if current.next.value == value:
                current.next = current.next.next   # skip over the deleted node
                self.size -= 1
                return True
            current = current.next

        return False

    def traverse(self):
        """Visit every node in order — O(n)."""
        values = []
        current = self.head
        while current is not None:
            values.append(current.value)
            current = current.next
        return values


ll = SinglyLinkedList()
ll.push_back(1)
ll.push_back(2)
ll.push_back(3)
ll.push_front(0)
print(ll.traverse())   # [0, 1, 2, 3]

ll.delete_value(2)
print(ll.traverse())   # [0, 1, 3]

Trace push_front(0) on a list that's currently 1 -> 2 -> 3: a new Node(0) is created, its .next is pointed at the current head (Node(1)), and then self.head is reassigned to the new node. Nothing about nodes 1, 2, or 3 changed at all — only two pointer assignments happened, regardless of how long the list is. That's the O(1) insertion the array couldn't offer at the front.

Array vs linked list: the trade-offs#

The row that surprises people most is "insert in the middle": a linked list's insertion itself is O(1), but you still generally pay O(n) to walk to the right position first — so in practice, inserting at an arbitrary position is O(n) either way. The linked list's real advantage shows up specifically when you already have a direct reference to the node (for example, you're already iterating and want to insert right where you are) — there, it beats an array decisively.

The other underrated factor is cache-friendliness: because array elements sit contiguously in memory, modern CPUs can prefetch and scan through them very fast. A linked list's nodes can be scattered anywhere in memory, so even an O(n) traversal of a linked list is typically slower in practice than an O(n) traversal of an array of the same size, despite having the same Big-O. Big-O describes the number of steps, not always the real-world wall-clock time — this is a good early example of where that distinction matters.

Classic problem: detect a cycle (Floyd's tortoise and hare)#

A cycle in a linked list means some node's .next eventually loops back to a node earlier in the chain, instead of ending in None — so a naive traversal would run forever. How do you detect this without unbounded extra memory?

The elegant solution is Floyd's cycle detection algorithm (also called "tortoise and hare"): use two pointers that both start at the head, but one (slow, the tortoise) moves one node at a time, while the other (fast, the hare) moves two nodes at a time. If there's no cycle, fast simply reaches the end (None) first. But if there is a cycle, fast will eventually lap slow from behind and the two pointers will land on the exact same node — proving a cycle exists.

Analogy: two runners on a circular track, one running twice as fast as the other. If the track is a straight line (no cycle), the faster runner just finishes and leaves. If it's a loop, the faster runner will eventually catch up to and pass the slower one from behind — the fact that they end up standing in the same spot again proves the track loops.

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


def has_cycle(head) -> bool:
    slow = fast = head

    while fast is not None and fast.next is not None:
        slow = slow.next          # moves 1 step
        fast = fast.next.next     # moves 2 steps

        if slow is fast:           # they've met — a cycle exists
            return True

    return False                   # fast reached the end — no cycle


# Build 1 -> 2 -> 3 -> 4 -> back to 2 (a cycle)
n1, n2, n3, n4 = Node(1), Node(2), Node(3), Node(4)
n1.next, n2.next, n3.next, n4.next = n2, n3, n4, n2   # n4 points back to n2

print(has_cycle(n1))  # True

# A normal, non-cyclic list for comparison
a, b, c = Node(1), Node(2), Node(3)
a.next, b.next = b, c
print(has_cycle(a))    # False

Why this works, traced through the cyclic example above (1 -> 2 -> 3 -> 4 -> 2 -> 3 -> 4 -> ...):

Because fast moves twice as fast, once both pointers are inside the cycle, the gap between them shrinks by exactly one node every step — so fast is guaranteed to catch slow eventually, rather than perpetually skipping over it. This runs in O(n) time and, crucially, O(1) extra space — no matter how long the list is, you only ever need two pointer variables, unlike a naive approach that stores every visited node in a set (which would also work, but at O(n) extra space).

Common mistakes#

• Losing the head reference. Since a linked list has no index-based access, if you lose your reference to head, the entire list becomes unreachable and is effectively garbage — always keep a stable reference to the start.
• Forgetting to update .next in the right order during deletion, which can accidentally disconnect part of the list. Always double-check: does this node still need to be reachable after this pointer change?
• Assuming linked lists are always better for insertion. They're only better at the front, or when you already hold a reference to the exact insertion point — otherwise, finding where to insert still costs O(n), same as an array.
• Not handling the empty-list case (head is None) at the start of insert/delete functions — a very common source of AttributeError: 'NoneType' object has no attribute ... bugs.