Data structures · foundation
Linked list
A linked list stores elements in separate nodes connected by references, with each node pointing to the next node and, in a doubly linked list, also to the previous one.
Why it matters
Linked lists support local insertion and removal without shifting a contiguous block, but sacrifice direct indexing and often data locality.
Mental model
How to reason about linked list
The list knows an entry node, not every node's position. To reach index i, follow i links; once the relevant node or predecessor is already known, relinking nearby pointers is constant work.
Analogy
A scavenger hunt gives the location of the next clue at each stop. Adding a clue between two known stops is easy, but reaching the fiftieth clue requires following the chain.
Examples
See the boundary, not just the happy path
Worked example · Insert after a known node
new.next = current.next
current.next = newWith current already in hand, insertion changes a fixed number of links and is Theta(1).
Worked example · Traverse all nodes
while node != null: visit(node.value); node = node.nextThe traversal follows each of n links once, giving Theta(n) time.
Useful contrast · Index lookup
value = list[500]A linked representation must walk from an endpoint to the requested position; it cannot calculate an address as an array can.
Common mistakes
Misconceptions to remove early
Claiming insertion is always constant time
Relinking is constant only after the insertion point is known. Searching for a value or index can still take Theta(n).
Ignoring ownership and invalidation
Removing a node while iterating can invalidate the current traversal or leak memory in manual-memory languages. Preserve the next link and follow the API's ownership rules.
Quick check
Can you predict the result?
1. What is the usual cost of accessing index i in a singly linked list?
- • Theta(i), and Theta(n) in the worst case
- • Theta(1) for every index
- • Theta(log n) because links halve the range
2. When is insertion into a linked list genuinely constant time?
Keep building