Linked List

Definition: A linear data structure where elements (nodes) store a data payload and references (pointers) to adjacent nodes, without requiring contiguous memory allocation.

How It Works

Each node is a small object holding a value and one or more pointers to neighboring nodes. Unlike an array, nodes can live anywhere in memory; the structure’s order comes entirely from the pointer chain, not from physical adjacency.

Singly Linked List: each node points only to the next node. Traversal is one-directional, and deleting a node requires a reference to its predecessor (to redirect its next pointer), since there’s no way to walk backward from the node itself.
Doubly Linked List: each node points to both the previous and next nodes, enabling O(1) removal given only a reference to the node itself, and bidirectional traversal at the cost of an extra pointer per node.
Circular Linked List: the tail node points back to the head instead of to null, useful for round-robin scheduling and ring-buffer-like structures where traversal should wrap around indefinitely.

Insertion and deletion at a known node location are O(1), since they only involve rewriting a couple of pointers, no shifting of any other elements, which is the linked list’s core advantage over an array.

Maintaining a tail pointer alongside head turns append-to-end from O(n) into O(1); without a tracked tail, appending requires walking the entire list first just to find the last node.

Insertion, Pointer by Pointer

Inserting a new node X between A and B in a singly linked list head -> A -> B -> C:

before: head -> A -> B -> C
step 1: X.next = A.next        # X now points to B
step 2: A.next = X             # A now points to X
after:  head -> A -> X -> B -> C

Only two pointer writes, regardless of how long the list is, as long as a reference to A (the node just before the insertion point) is already in hand. Deleting X again is the mirror operation: A.next = X.next, splicing X out in a single write. This is the entire reason a linked list beats an array for this kind of edit: an array would need to shift every element from the insertion point onward.

Reversal, Traced

Reversing A -> B -> C -> null in place using three tracking pointers:

init:  prev=null, current=A, (A->B->C->null)

step 1: next=B; A.next=null (A now points to prev); prev=A; current=B
        state: null <- A    B -> C -> null

step 2: next=C; B.next=A (B now points to prev); prev=B; current=C
        state: null <- A <- B    C -> null

step 3: next=null; C.next=B (C now points to prev); prev=C; current=null
        state: null <- A <- B <- C

loop ends (current is null); new head = prev = C
result: C -> B -> A -> null

Each node’s next pointer is rewritten exactly once, giving O(n) time and O(1) extra space, no new nodes are allocated and no separate output list is built.

Complexity Analysis

Operation	Singly Linked	Doubly Linked	Array (for comparison)
Access by index	O(n)	O(n)	O(1)
Search by value	O(n)	O(n)	O(n)
Insert/delete at head	O(1)	O(1)	O(n) (shifting)
Insert/delete at tail (with tail pointer)	O(1) append, O(n) delete (needs predecessor)	O(1)	Amortized O(1) append
Insert/delete given a node reference	O(n) (needs predecessor)	O(1)	O(n)
Space overhead per element	1 pointer	2 pointers	None beyond the element

Why It Matters

Efficient for workloads with frequent insertion/deletion in the middle of a sequence, since no bulk shifting or reallocation is required, unlike an array where a middle insert costs O(n).
Forms the building block for other structures: Stack and Queue implementations, adjacency lists in Graph Representation, and the separate-chaining collision strategy inside a Hash Table.
LRU cache implementations classically pair a doubly linked list, for O(1) reordering of recency, with a hash table, for O(1) key lookup, to get both properties at once: fast lookup and fast “move to front” without shifting anything.

Common Pitfalls

Sequential access takes O(n) time; there is no random indexing, so algorithms assuming array-like O(1) access, like Binary Search, silently become O(n log n) or worse if ported naively onto a linked list.
Extra memory overhead for storing pointer references per element, roughly 8-16 bytes of pointer overhead per node on a 64-bit system, which can dominate the payload size for small elements like a single integer.
Poor CPU cache performance due to non-contiguous memory allocation; nodes scattered across the heap cause a cache miss on nearly every hop, making linked-list traversal much slower in practice than an array traversal of the same logical size, despite both being O(n).
Losing the only reference to the rest of the list, e.g. overwriting head before saving it, leaks the remaining nodes with no way to reach or free them in unmanaged languages.
Forgetting to update both prev and next pointers symmetrically in a doubly linked list during insert/delete, leaving the list traversable in one direction but corrupted in the other.

Comparison

	Singly Linked List	Doubly Linked List	Array	Dynamic Array
Random access	O(n)	O(n)	O(1)	O(1)
Insert/delete at known position	O(1)	O(1)	O(n)	O(n)
Memory layout	Scattered	Scattered	Contiguous	Contiguous
Reverse traversal	Not possible	O(n)	O(n)	O(n)
Cache locality	Poor	Poor	Excellent	Excellent
Memory overhead per element	1 pointer	2 pointers	None	None (until resize headroom)
Iterator/reference stability on mutation	Stable (nodes don’t move)	Stable	Invalidated on resize	Invalidated on resize

Variants

Skip List: a linked list augmented with multiple “express lane” layers of pointers that skip over several nodes at once, giving O(log n) expected search, insert, and delete while remaining a fundamentally pointer-based structure. Redis’s sorted set (ZSET) uses a skip list internally alongside a hash table.
XOR Linked List: a memory-saving trick that stores a single XOR of the previous and next pointers per node instead of two separate pointers, halving pointer overhead at the cost of needing the previous node’s address to compute the next one, which makes it incompatible with garbage-collected languages and rarely used outside of low-level systems programming.
Unrolled Linked List: each node holds a small fixed-size array of elements instead of just one, reducing pointer overhead and improving cache locality relative to a plain linked list while keeping O(1) mid-list insertion within a node’s array capacity.

Example

Implementing an undo history buffer where nodes can be quickly added or removed at pointer locations is a natural fit for a doubly linked list:

head -> [Edit1] <-> [Edit2] <-> [Edit3] <- tail

Undoing Edit3 just moves a current pointer from Edit3 to Edit2 in O(1); no data is copied or shifted. Removing the last element of a plain array-backed list is also O(1), but removing from the middle of that array costs O(n) for the element shift, versus O(1) for a doubly linked list given a direct reference to the node being removed.

Classic Linked List Techniques

Fast/slow pointer (Floyd’s cycle detection): advance one pointer one node at a time and another two nodes at a time; if they ever meet, the list contains a cycle. This runs in O(n) time and O(1) space, versus O(n) space for a hash-set-based visited check.
Reversing a list in place: walk the list once, at each node redirecting its next pointer to the previous node instead of the next, using three tracking pointers (prev, current, next). O(n) time, O(1) extra space.
Dummy/sentinel head node: prepending a placeholder node before the real head simplifies edge cases (deleting the actual head, inserting before the first element) by removing the need for special-case null checks.

FAQ

Why not just always use a dynamic array instead? Arrays win when random access or cache-friendly sequential scanning dominates the workload. Linked lists win when the workload does frequent insertion/deletion at arbitrary positions with a known node reference, and array-style shifting would be too costly.

Is a doubly linked list always better than singly linked? No, it costs an extra pointer per node and extra bookkeeping on every insert/delete to keep both directions consistent. Singly linked lists remain the right default when only forward traversal and head/tail operations are needed.

Real-World Systems

Language runtimes implement LinkedHashMap (Java) and OrderedDict-style structures by pairing a hash table with a doubly linked list, using the list purely to track insertion or access order while the hash table handles O(1) key lookup.
Operating system schedulers historically used linked lists to track runnable processes before more scalable structures like Red-Black trees replaced them for large process counts (see AVL Tree and Red-Black Tree).
Music and video players’ “playlist” abstractions map naturally onto a doubly linked list: next/previous track navigation is exactly the doubly linked list’s core O(1) operation.

Common Interview Questions

How do you detect a cycle in a linked list without extra memory? — Floyd’s fast/slow pointer technique: two pointers advancing at different speeds are guaranteed to meet if a cycle exists, in O(n) time and O(1) space.
How do you find the middle of a linked list in one pass? — advance a slow pointer by one node and a fast pointer by two; when the fast pointer reaches the end, the slow pointer is at the middle.
Why is merging two sorted linked lists O(1) space, unlike merging two sorted arrays? — because linked list nodes can be relinked in place by adjusting pointers, with no need for a separate output buffer the way array merging requires.

Referenced by

Dig deeper

Spot an error in this note?