Linked Lists

A linked list stores sequence order in references between separately allocated nodes rather than in contiguous slots.

from dataclasses import dataclass


@dataclass
class Node:
    value: int
    next: "Node | None" = None

Open full-size image

Follow head and tail between rows. Adding x extends the tail; remove and pop advance the head; push(y) adds a new head. These operations update endpoint references without shifting the remaining nodes to fill the space left by a removal.

Pat Morin, Open Data Structures, Figure 3.1 (cropped from p. 62). · CC BY 2.5 CA

Variants and invariants

• Singly linked nodes point forward; the tail points to None.
• Doubly linked nodes point forward and backward; updates must preserve both directions.
• Circular lists connect the tail back to an endpoint and need an explicit termination rule for traversal.

Maintaining head, tail, and size fields improves some operations but creates more invariants that every mutation must preserve.

Cost model

Operation	Singly linked list
Access/search by position or value	$O(n)$
Insert after a known node	$O(1)$
Remove after a known predecessor	$O(1)$
Append with a maintained tail	$O(1)$
Remove tail	$O(n)$

The constant-time insertion/deletion claim excludes the cost of finding the node. A doubly linked list can remove a known node in $O(1)$ because it also knows the predecessor.

Trade-offs

Linked lists offer stable node identity and cheap local splicing, but pay for references, allocation, pointer chasing, and weaker cache locality. They are valuable inside structures such as intrusive lists and hash-table chains, but a dynamic array is usually the better default sequence.

Splicing without losing the suffix

The singly linked list construction changes links rather than moving the remaining values. Using Node above:

head = Node(10, Node(30))
pred = head
pred.next = Node(20, pred.next)
assert head.next.value == 20
assert head.next.next.value == 30

removed = pred.next
if removed is None:
    raise IndexError("no successor to remove")
pred.next = removed.next
removed.next = None
assert head.next.value == 30

The new node must receive the old successor before the predecessor is redirected. Otherwise the suffix can become unreachable. Removal bypasses the node; clearing its link detaches it but does not destroy other references to that node.

This small example keeps only a head pointer. A full container must also update its tail when inserting after the old tail or removing the last node, and change size exactly once. In an empty list, head and tail are both None and size is zero; removing the sole element must restore that state. A head insertion uses head = Node(value, head) because there is no predecessor. A dummy sentinel node can make that boundary resemble an ordinary splice.

The cost table counts a constant number of link operations and assumes fixed-cost element handling; allocation and reclamation do not have a universal latency guarantee. A “known node” must still belong to this list. Reusing a linked node in two lists, or linking a node back to itself accidentally, breaks ownership or termination even when each assignment is constant time.

Source

• Open Data Structures: Linked Lists

My reading · Opened notes are remembered in this browser.