Linked Lists

An array’s insertion and deletion cost arose from a single requirement: elements staying contiguous. If contiguity is abandoned, shifting disappears with it.

A linked list makes this trade-off. Elements sit wherever they like in memory; order is established by each element carrying the address of the next one.

Node and Link

The structure’s unit is the node: a value and the address of the next node.

head → [12 | •] → [18 | •] → [7 | •] → [25 | ⏚]

The last node’s link is empty; this emptiness marks the end of the list. The list itself is represented by a single thing: the address of the first node, that is, the head.

Address arithmetic does not apply here. Where the third element is cannot be computed; two links must be followed starting from the head. This means losing the array’s constant-time access: in a linked list, access to the $i$-th element is $O(n)$.

class Node:
    """A value and the link to the next node."""

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


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

    def prepend(self, value: int) -> None:
        """Links the new node at the head: constant time."""
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node
        self.length += 1

    def find(self, value: int) -> int:
        """Returns the value's index; -1 if absent. Takes as many steps as the links followed."""
        index = 0
        node = self.head
        while node is not None:
            if node.value == value:
                return index
            node = node.next
            index += 1
        return -1

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


linked_list = LinkedList()
for measurement in (25, 7, 18, 12):    # inserted in reverse order
    linked_list.prepend(measurement)

print(linked_list.values())                        # [12, 18, 7, 25]
print(linked_list.find(7), linked_list.find(99))    # 2 -1
print(linked_list.length)                           # 4

Prepending is constant time: two links are written, no element is moved. The same operation shifted every element in an array.

Locating Versus Linking

The most commonly misunderstood aspect of the linked list is this: insertion and deletion are cheap, but locating the position is expensive.

If a node reference is already in hand, inserting after it is a few pointer writes — $O(1)$. But if the request is “insert after the tenth element,” nine links must be followed first; the total cost is $O(n)$ after all.

This distinction determines the linked list’s proper use: the structure pays off if the reference to the relevant node is already held; it does not if every operation searches from the head.

Doubly Linked List

Deleting a node in a singly linked list requires changing the previous node’s link, yet there is no way to go backward from the node. The solution is to add a back-link to every node as well.

In a doubly linked list, every node knows both its next and its previous. Consequences:

• Deletion is $O(1)$ when a node reference is already in hand.
• The list can be traversed in either direction.
• Every node carries one more pointer; memory overhead increases.
• Every insertion and deletion updates four links instead of two; the code is more error-prone.

If both head and tail pointers are kept, insertion at either end of the list becomes constant time. This is the natural foundation of the stack and queue structures in the next two lessons.

A third variant is the circular list, in which the last node links back to the head; it is used in scheduling and buffering applications that keep cycling to the next item.

Sentinel Node

The source of errors in linked list code is edge cases: inserting into an empty list, deleting the first node, inserting after the last node. Each requires a separate if block, and when one of these blocks is forgotten, the bug shows up only in that specific case.

A sentinel node is a dummy node that carries no value and is placed permanently at the head of the list. Because the head always exists, “deleting the first node” stops being a separate case — every node has a predecessor.

class SentinelList:
    """Deletion runs with a single code path thanks to the head sentinel node."""

    def __init__(self) -> None:
        self.sentinel = Node(0)        # its value is never used

    def insert(self, value: int) -> None:
        new_node = Node(value)
        new_node.next = self.sentinel.next
        self.sentinel.next = new_node

    def remove(self, value: int) -> bool:
        previous = self.sentinel       # a valid "previous" always exists
        while previous.next is not None:
            if previous.next.value == value:
                previous.next = previous.next.next
                return True
            previous = previous.next
        return False


sentinel_list = SentinelList()
for measurement in (7, 18, 12):
    sentinel_list.insert(measurement)
print(sentinel_list.remove(12), sentinel_list.remove(99))    # True False

The same technique is also used in circular doubly linked lists, and it markedly reduces the number of edge cases in the code.

Memory Overhead and Cache

The linked list’s advertised advantages are limited in practice by two costs.

Extra space. Every node carries one or two pointers alongside its value. With eight-byte pointers, in a singly linked list of four-byte integers the structural data outweighs the actual data. Compared to an array, memory usage can grow by a multiplicative factor.

Locality. Nodes sit scattered on the heap. Moving from one node to the next means jumping to an unpredictable address in memory; fetching a cache line brings no benefit, and prefetching does not work. The difference calculated in the cache lesson of the How Computers Work course works in reverse here: while array traversal uses many elements per cache line, list traversal carries a separate miss risk for every node.

The result is this: a linked list insertion that is $O(1)$ on paper can, in actual measurements, be slower than an array insertion that is $O(n)$ — especially when the element count is small or moderate. The complexity class ignores constant factors; hardware does not.

When to Use a Linked List

The structure’s legitimate use cases are narrow but real:

• When a node reference is already held. The best-known example is a doubly linked list used together with a hash table: the table hands over the node directly, and the list updates the ordering in constant time. Least-recently-used cache designs are built on this pair.
• When reallocation is unacceptable. A dynamic array’s growth makes a single operation take a long time; systems with a latency bound may not tolerate this.
• When reference stability is required. A node’s address in a linked list does not change when new elements are added to the list; in a dynamic array, reallocation invalidates every address.
• When lists are frequently merged. Joining two lists end to end amounts to writing a single link.

Outside of these, the default choice is the array.

Cost Table

Structure	Access	Search	Insert at start	Insert at end	Delete (node in hand)
Array (fixed size)	$O(1)$	$O(n)$	$O(n)$	$O(1)$*	$O(n)$
Dynamic array	$O(1)$	$O(n)$	$O(n)$	$O(1)$ amortized	$O(n)$
Singly linked list	$O(n)$	$O(n)$	$O(1)$	$O(n)$**	$O(n)$
Doubly linked list	$O(n)$	$O(n)$	$O(1)$	$O(1)$**	$O(1)$

* As long as room remains. ** $O(1)$ if a tail pointer is kept.

Summary

• In a linked list, elements do not sit contiguously; order is established by each node carrying the address of the next one.
• Address arithmetic does not apply; access to the $i$-th element is linear time.
• Insertion and deletion are cheap because they amount to writing pointers; what is expensive is locating the position.
• In a doubly linked list, the back-link makes deletion constant time when a node is in hand; the cost is extra memory and more complex updates.
• Pointer overhead and scattered layout can pull the list’s practical performance below its theoretical cost.
• The structure is chosen when a node reference is already held, when reallocation is unacceptable, or when reference stability is required.

Next Step

The next two lessons take up two abstract data types built on top of the structures defined so far. The first is the stack, which permits access only to the most recently added element; how function calls are managed will be recalled from the previous course.