Linked lists — the basics

The data structure that trades array's instant indexing for fast insertion anywhere — worth understanding as a genuine trade-off, not just "the other list type."

Beginner

3 min read

What a linked list actually is

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
 
# building 1 -> 2 -> 3 by hand
first = Node(1)
second = Node(2)
third = Node(3)
first.next = second
second.next = third

A linked list isn't one contiguous block of memory like an array — it's a chain of individual nodes, each holding a value and a reference (a pointer) to the next node in the chain. The list itself is really just "a reference to the first node" (first, here); everything else is reached by following .next links, one at a time, starting from that first node. There's no single block of memory holding the whole thing — each node can live anywhere in memory, connected only by these .next references.

Why this trade-off exists: insertion at the front

new_head = Node(0)
new_head.next = first    # 0 -> 1 -> 2 -> 3
first = new_head

Adding a new node at the front of a linked list is O(1) — create the node, point its .next at the old first node, update what counts as "first." Nothing else in the list has to move or shift, unlike an array, where inserting at the front means physically sliding every existing element over by one position (O(n)). This is the entire reason linked lists exist: they trade away array's instant indexed access for cheap insertion and removal anywhere in the chain, especially at the front.

The cost: no more instant access by position

def get_at(head, index):
    current = head
    for _ in range(index):
        current = current.next     # have to walk the chain, one node at a time
        if current is None:
            raise IndexError
    return current.value

numbers[2] on an array is O(1) — direct memory calculation. Getting the third node of a linked list is O(n) — there's no way to jump directly to a position; the only way to reach it is to start at the first node and follow .next references one at a time until you've walked far enough. This is the real trade-off, not a minor detail: linked lists are fast to insert into but slow to index into, arrays are the exact opposite, and choosing between them in practice comes down to which operation actually dominates the problem you're solving.

Traversing a linked list — the pattern every operation builds on

def print_all(head):
    current = head
    while current is not None:
        print(current.value)
        current = current.next

1
2
3

This "start at the head, follow .next until you hit None" loop is the foundation almost every linked-list operation is built from — searching for a value, computing the length, reversing the list, all start with some version of this same walk. current = current.next moving the "current position" forward is the linked-list equivalent of an array loop's i += 1.

When a linked list actually wins in practice

Real-world linked lists show up less often than arrays as a primary storage choice — but the underlying idea (a chain of nodes, each pointing to what's next) is the foundation other structures build on: a queue implemented efficiently, the "undo history" of an editor (each state points back to the previous one), and the traversal pattern itself is a direct preview of tree and graph traversal, where "follow a reference to the next thing" is the same core mechanism applied to a branching structure instead of a straight line.