Linked Lists
Imagine building a music playlist app. Users constantly reorder songs, insert new tracks, and delete others. If you store the playlist in an array, inserting a song at position 3 means shifting every song after it one slot over. This is an O(n) operation that gets slower as the playlist grows. A linked list solves this by giving up the array's contiguous memory layout. In exchange, it offers O(1) insertion and deletion once you already have a reference to the right spot. This tradeoff — sacrificing fast random access for fast splicing — is one of the oldest and most instructive decisions in data structure design. Linked lists appear inside the implementation of stacks, queues, and hash tables (via Separate Chaining Collision Resolution). They also appear inside operating system schedulers that track runnable processes. They appear inside text editors that model a document as a chain of lines. They also appear inside version-control-like "undo" systems that need to insert and remove history entries cheaply. Anywhere you need a sequence with frequent insertions and deletions at arbitrary positions, a linked list is a natural fit. This holds true if you're willing to give up O(1) random access. The same goes for one of its descendants like a skip list. The central idea is deceptively simple. Instead of storing elements in consecutive memory cells, store each element in its own node. Have each node hold a pointer to the next node. In a doubly linked list, it also points to the previous node. This indirection is what buys you cheap insertion and deletion. The cost is losing the ability to jump directly to the k-th element. There is also extra memory needed for the pointers themselves. This article builds singly and doubly linked lists from first principles. It covers the node structure, and the pointer-splicing operations that make insertion and deletion O(1). It also covers the O(n) traversal that search and access require. It includes a rigorous comparison against Arrays and Dynamic Arrays. You will see exact pseudocode for every core operation. You will also see a worked trace through a real sequence of operations. You will also see the classic bugs — dangling pointers, lost tail references, off-by-one traversal. These trip up nearly everyone the first time they implement one.
- A linked list stores elements in separate nodes, each holding data plus a pointer to the next node (and, for doubly linked lists, the previous node).
- Insertion and deletion at a known position are O(1) — you just rewire a few pointers, no shifting required.
- Search, indexed access, and reaching the k-th element are O(n) — you must walk the chain from the head (or tail).
- Doubly linked lists add a `prev` pointer, enabling O(1) backward traversal and O(1) deletion given only a node reference.
- Arrays win on random access and cache locality; linked lists win on splice-heavy workloads with unknown final size.
- Linked lists are the backbone of Stacks, Queues and Deques and the chaining scheme in Separate Chaining Collision Resolution.
Trading contiguous memory for per-element pointers turns O(n) array insertion/deletion into O(1) pointer rewiring, at the price of O(n) access and search.
The idea
A linked list is a linear collection of nodes where each node stores a piece of data together with one or more pointers (or references) to other nodes in the collection. In a singly linked list, each node has exactly one pointer, `next`, pointing to its successor; the list itself is represented by a pointer `head` to the first node, and the last node's `next` is a sentinel value, typically `null` or `nil`. In a doubly linked list, each node additionally stores `prev`, a pointer to its predecessor, and the list often maintains both a `head` and a `tail` pointer so that operations at either end are O(1). The crucial structural difference from an array is non-contiguity. An array's elements live at addresses `base + i * elementSize`, so the address of the i-th element is computable in O(1) via arithmetic — this is what gives arrays O(1) random access. A linked list's nodes can live anywhere in memory; the only way to reach the i-th node is to follow `next` pointers starting from `head`, i-1 times. This is the fundamental reason indexed access and search are O(n) in a linked list but the reason insertion and deletion are O(1): adding a node between two existing nodes requires rewriting only a constant number of pointers, never shifting any other element. Two further variants are worth naming precisely. A circular linked list has its last node point back to the first (and, if doubly linked, the first node's `prev` points to the last), which is useful for round-robin scheduling and buffer structures. A list with a sentinel node (a permanently allocated dummy head, sometimes also a dummy tail) removes almost all of the special-case logic for empty lists and boundary insertions, because the dummy node guarantees every real node always has both a predecessor and successor to splice around — a technique worth internalizing early, since it eliminates an entire class of null-pointer bugs.
How it works
The heart of a linked list is a small set of pointer-manipulation primitives. We describe them for a singly linked list first, then note the extensions for a doubly linked list.
Node structure. Each node holds a value and a `next` pointer (plus `prev` for doubly linked lists): ``` struct Node: value: T next: pointer to Node // singly linked prev: pointer to Node // doubly linked only ```
Traversal / search. To find a value or reach a given position, walk from `head`, following `next` until you find the value, run off the end, or reach the desired index: ``` function SEARCH(head, target): curr = head while curr != null and curr.value != target: curr = curr.next return curr // null if not found function GET(head, index): // 0-indexed curr = head i = 0 while curr != null and i < index: curr = curr.next i = i + 1 if curr == null: error "index out of bounds" return curr ```
Insertion at the front is the canonical O(1) operation: allocate a node, point its `next` at the old head, and update `head`. ``` function INSERT_FRONT(head, value): node = new Node(value, next = head) head = node return head // caller must update its head reference ```
Insertion after a given node is where the real payoff of linked lists shows up — no shifting, just pointer rewiring: ``` function INSERT_AFTER(prevNode, value): if prevNode == null: error "prevNode must not be null" node = new Node(value, next = prevNode.next) prevNode.next = node ``` Note the order: you must set the new node's `next` before overwriting `prevNode.next`, or you lose the reference to the rest of the list. This ordering dependency is the single most common source of bugs in linked-list code.
Deletion of the node after a given node: ``` function DELETE_AFTER(prevNode): if prevNode == null or prevNode.next == null: error "nothing to delete" target = prevNode.next prevNode.next = target.next free(target) ```
Deleting the head requires special handling in a plain singly linked list, since there is no "previous" node to hold a pointer: ``` function DELETE_FRONT(head): if head == null: error "list is empty" oldHead = head head = head.next free(oldHead) return head ```
Doubly linked list splicing. With a `prev` pointer, insertion and deletion at an arbitrary known node become truly O(1) with no need to track "the previous node" separately, because the node itself carries that information: ``` function INSERT_AFTER_DLL(node, value): newNode = new Node(value) newNode.next = node.next newNode.prev = node if node.next != null: node.next.prev = newNode node.next = newNode function DELETE_NODE_DLL(node): if node.prev != null: node.prev.next = node.next else: head = node.next // node was the head if node.next != null: node.next.prev = node.prev else: tail = node.prev // node was the tail free(node) ``` This `DELETE_NODE_DLL` is the key advantage of doubly linked lists over singly linked ones: given only a reference to the node to delete (not its predecessor), deletion is still O(1). In a singly linked list, deleting a given node without a predecessor reference requires an O(n) scan to find that predecessor — unless you use the trick of copying the next node's value into the target and deleting the next node instead, which fails only when the target is the last node.
Sentinel (dummy head) trick. Many production implementations avoid null-checks entirely by allocating a permanent dummy node before the real head (and sometimes a dummy tail after the real tail). Every real node then always has a genuine predecessor and successor node to splice against: ``` function INSERT_AFTER_SENTINEL(prevNode, value): // no null-checks needed node = new Node(value, next = prevNode.next) prevNode.next = node ``` Since `prevNode` is guaranteed non-null (worst case it's the sentinel), `INSERT_FRONT` becomes just `INSERT_AFTER_SENTINEL(sentinel, value)` — one code path, no special case for "inserting into an empty list."
Complexity & correctness
Time complexity summary (n = number of nodes in the list):
| Operation | Singly linked | Doubly linked | Array (unsorted, dynamic) |
|---|---|---|---|
| Access by index | O(n) | O(n) | O(1) |
| Search by value | O(n) | O(n) | O(n) |
| Insert at front | O(1) | O(1) | O(n) (shift) |
| Insert at back (with tail ptr) | O(1) | O(1) | O(1) amortized |
| Insert/delete at known node | O(n)* | O(1) | O(n) (shift) |
| Delete at front | O(1) | O(1) | O(n) (shift) |
| Extra space per element | 1 pointer | 2 pointers | 0 (contiguous) |
For singly linked lists, "insert/delete at a known node" is O(1) only if you already hold a pointer to the <strong>predecessor</strong>; deleting a node given only a pointer to that node itself* costs O(n) because you must scan from the head to find its predecessor (the value-copy trick sidesteps this for deletion of non-tail nodes, but is a special-cased hack, not a general O(1) guarantee).
Why insertion/deletion is O(1): `INSERT_AFTER` and `DELETE_AFTER` perform a fixed, constant number of pointer reads and writes — no dependence on n — regardless of where in the list the operation occurs. This is the whole point of the indirection: nodes do not need to be contiguous, so adding or removing one does not require moving any other node's data, unlike an array where inserting at index i shifts all n − i trailing elements.
Why traversal-based operations are O(n): there is no arithmetic shortcut to the k-th node's address, because nodes are scattered in memory and only reachable by following pointers one hop at a time. In the worst case (index n − 1, or value not present) you must visit all n nodes. This is a direct consequence of giving up contiguity: you cannot compute `base + k * size` when there is no `base` that determines every node's location.
Correctness argument (loop invariant for `SEARCH`). Consider `SEARCH(head, target)`. The loop invariant is: at the top of each iteration, `curr` points to a node not yet examined, and no node strictly before `curr` in the list equals `target`. Initially `curr = head` and the invariant holds vacuously (no nodes examined yet). Each iteration either terminates (curr is null, meaning the whole list was scanned with no match — correctly reported as not found; or `curr.value == target`, correctly returned) or advances `curr = curr.next`, preserving the invariant since the just-examined node was confirmed not equal to `target`. Because the list is finite and acyclic (assuming a proper, non-circular list) and `curr` strictly advances, the loop terminates after at most n steps. This establishes both partial correctness (if it returns, the answer is right) and termination, hence total correctness.
Correctness of `INSERT_AFTER`/`DELETE_AFTER`. The key invariant to preserve is list connectivity: every node reachable from `head` before the operation, except possibly the target of a deletion, must remain reachable afterward, in the same relative order. `INSERT_AFTER(prevNode, value)` sets `node.next = prevNode.next` before `prevNode.next = node`; this ordering is essential — reversing it would overwrite `prevNode.next` first, permanently losing the pointer to the remainder of the list (a classic bug, discussed below). With the correct ordering, the new node is spliced in without disturbing the pointer chain reachable from any other node. `DELETE_AFTER` similarly re-links `prevNode.next` directly to `target.next`, so every node after `target` remains reachable through `prevNode`, and `target` becomes unreachable (and its memory can be reclaimed) — precisely the desired postcondition.
Space complexity. A singly linked list uses O(n) space for data plus O(n) extra space for `next` pointers; a doubly linked list adds another O(n) for `prev` pointers — roughly double the pointer overhead, in exchange for O(1) backward traversal and O(1) deletion given a bare node reference. Arrays have zero per-element pointer overhead but may over-allocate (a dynamic array typically keeps some unused capacity to amortize growth).
The honest tradeoff. Linked lists lose on cache locality: because nodes are scattered across the heap, sequential traversal incurs a cache miss (or a TLB/page fault, in the worst case) roughly once per node, whereas array traversal streams through contiguous memory with excellent spatial locality. In practice, for small-to-medium n, a dynamic array is often faster even for insertions in the middle, because the O(n) shifting cost is a tight, vectorizable memory copy, while the "O(1)" linked-list insertion is preceded by an O(n) search to find the insertion point in the first place (unless you already hold a node pointer, e.g., from an iterator). Linked lists win decisively only when: (a) you already have a reference to the splice point (as in an iterator that deletes while traversing), (b) the list's size is highly unpredictable, or (c) you need to preserve pointers/iterators to elements across insertions/deletions elsewhere in the list, which array-based structures cannot generally guarantee since shifting invalidates indices.
Worked example
Let's trace a doubly linked list through a realistic sequence of playlist edits, starting empty, using a sentinel-free implementation with explicit `head`/`tail`.
Operations, in order: 1. `INSERT_FRONT("Song A")` 2. `INSERT_FRONT("Song B")` 3. `INSERT_AFTER(head, "Song C")` — insert C right after B 4. `INSERT_AFTER(head.next, "Song D")` — insert D right after C 5. `SEARCH("Song A")` 6. `DELETE_NODE(head.next)` — delete the node right after head (C)
| Step | Action | List state (head → … → tail) | Notes |
|---|---|---|---|
| 0 | initial | (empty) | head = tail = null |
| 1 | `INSERT_FRONT("Song A")` | A | new node; head = tail = A since list was empty |
| 2 | `INSERT_FRONT("Song B")` | B ⇄ A | B.next = A, A.prev = B; head = B |
| 3 | `INSERT_AFTER(head, "Song C")` | B ⇄ C ⇄ A | C.next = B.next (A); C.prev = B; A.prev = C; B.next = C |
| 4 | `INSERT_AFTER(head.next, "Song D")` | B ⇄ C ⇄ D ⇄ A | head.next is now C; D spliced between C and A |
| 5 | `SEARCH("Song A")` | B ⇄ C ⇄ D ⇄ A | walks B→C→D→A: 4 comparisons, returns pointer to A's node |
| 6 | `DELETE_NODE(head.next)` | B ⇄ D ⇄ A | head.next is C; C.prev(B).next = C.next(D); D.prev = B; C freed |
Walking through step 3 in full detail to nail the pointer arithmetic: before the call, `B.next = A` and `A.prev = B`. We allocate C with `C.next = B.next` (so `C.next = A`) and `C.prev = B` (implicit via the `INSERT_AFTER_DLL` logic). Then, since `B.next` (which is A) is non-null, we set `A.prev = C`. Finally `B.next = C`. After these four pointer writes, the chain reads B → C → A forward and A → C → B backward — exactly the desired splice, achieved in constant time regardless of how long the list is. Step 6 shows the payoff of the doubly linked structure: deleting C requires no scan to find its predecessor, because `C.prev` (which is B) is already stored in the node. We simply set `B.next = C.next` (D) and `D.prev = B`, then free C — four pointer operations, O(1), even though the list could have had a million nodes to C's left. Contrast this with what an array-based playlist would have done for the same sequence: each `INSERT_FRONT` and `INSERT_AFTER` would have required shifting all elements to the right of the insertion point, costing O(n) per insertion in the worst case (inserting near the front) — for m insertions this can total O(m·n) versus the linked list's O(m).
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Overwriting `prevNode.next` before saving it | `INSERT_AFTER` or `DELETE_AFTER` written in the wrong order loses the rest of the list permanently | Always read/save the old pointer (`node.next = prevNode.next`) before mutating `prevNode.next` |
| Losing the tail pointer after deleting the last node | Forgetting to check `if node == tail: tail = node.prev` | Explicitly update `head`/`tail` whenever the node being touched is the head/tail |
| Off-by-one in `GET(head, index)` | Confusing "steps taken" with "index reached," especially at index 0 or n−1 | Use a clean loop invariant: after k iterations `curr` is at index k; test `i < index`, not `i <= index` |
| Dangling pointer after `free(node)` | Using `node` (or a stale copy of it) after freeing it, e.g., in a caller that cached the pointer | Null out local references immediately after freeing; in GC'd languages this is less dangerous but still a logic bug |
| Infinite loop on an accidentally-circular list | A bug elsewhere set `tail.next = head` instead of `null`, and traversal code assumes `null` termination | Use Floyd's cycle detection (slow/fast pointers) defensively, or assert acyclicity in tests |
| Forgetting the empty-list case | `head == null` isn't handled, causing a null-dereference on the very first `head.value` | Always special-case (or use a sentinel node to eliminate the case entirely) |
| Singly linked "delete this node" without predecessor | Assuming you can delete any node in O(1) as in a doubly linked list | Either track the predecessor during traversal, or use a doubly linked list if arbitrary O(1) deletion is required |
Pioneers & history
The linked list has no single inventor in the way an algorithm might; it emerged as engineers and mathematicians working on early symbolic computation and list-processing systems converged on the idea that "a pointer to the next cell" was a more flexible representation than a fixed array. The concept crystallized most visibly in the design of list-processing languages built to manipulate symbolic expressions rather than numeric arrays, where the shape and length of data was inherently dynamic and unpredictable in advance.
Origins · 1 minJohn McCarthy and how this was discovered
McCarthy, working at MIT and later Stanford, designed the Lisp programming language in 1958 as a practical notation for symbolic computation and, soon after, for artificial intelligence research. Lisp's fundamental data structure, the cons cell — a pair holding a value and a pointer to the rest of the list — is exactly the singly linked list node described in this article, and Lisp's entire "everything is a list" philosophy popularized pointer-chained data structures throughout computer science. McCarthy also introduced garbage collection to automatically reclaim unreachable cons cells, directly motivated by the dangling-node and memory-reclamation issues linked lists raise.
Where this matters
Operating system kernels use doubly linked lists pervasively — the Linux kernel's `list_head` is a generic doubly linked list embedded directly inside structs, used for process run queues, free memory block lists, and device driver lists, precisely because kernel code constantly inserts and removes entries from the middle of dynamically sized collections. Text editors often represent a document as a linked list of lines (or a more advanced structure like a rope or gap buffer derived from the same idea) so that inserting or deleting a line does not require shifting the entire document. Hash tables implementing Separate Chaining Collision Resolution store all keys that hash to the same bucket in a linked list, giving O(1) expected insertion into a bucket regardless of how many other buckets exist. The Stacks, Queues and Deques family is most naturally implemented with a singly or doubly linked list when unbounded size and O(1) push/pop at the ends are required. Garbage collectors track free memory blocks in a linked "free list." Undo/redo systems, LRU caches (a doubly linked list plus a hash map, giving O(1) access, insertion, and move-to-front), and music/video playlists all lean on the same splice-at-a-known-point property. More advanced structures such as Skip Lists layer multiple linked lists at different "skip" granularities on top of this same node-and-pointer idea to recover fast search while keeping cheap insertion.
Ask the tutor: Can you show how a doubly linked list combined with a hash map implements an O(1) LRU cache?
Why is search O(n) in a linked list but insertion O(1)? Isn't that contradictory?
It isn't, because they measure different things. Search must locate an element with no shortcut — since nodes are scattered in memory, the only way to find the k-th node or a node with a given value is to follow pointers one at a time from the head, which costs O(n) in the worst case. Insertion, in contrast, assumes you already have a pointer to the splice location (e.g., the node you want to insert after). Given that pointer, rewiring a constant number of `next`/`prev` fields takes O(1) regardless of list length. The apparent contradiction disappears once you separate "finding the spot" (O(n)) from "modifying the spot once found" (O(1)); many real workloads amortize the search cost by keeping a live iterator or cached pointer around.
When should I use a linked list instead of a dynamic array?
Prefer a linked list when you need frequent insertions or deletions at arbitrary positions where you already hold (or cheaply obtain) a pointer to the splice point, when the final size is unpredictable and you want to avoid amortized-cost reallocation copies, or when you need pointers/references to individual elements to remain valid across insertions and deletions elsewhere in the structure (array reallocation and shifting invalidate such references). Classic cases include LRU cache internals, kernel scheduler queues, and hash table buckets. Prefer a dynamic array when you need fast random access by index, when you iterate sequentially very often (cache locality wins), or when memory overhead per element matters, since arrays have zero pointer overhead per element.
What is a sentinel node and why does it simplify the code so much?
A sentinel is a permanently allocated dummy node — often a dummy head, sometimes also a dummy tail — that never holds real data but always sits at the boundary of the list. Its purpose is to guarantee that every real node has a genuine node before it and after it to splice against, so insertion and deletion code never needs a special branch for "the list was empty" or "we're inserting at the very front." Instead of writing `if head == null then head = newNode else prevNode.next = newNode`, you always execute the single unconditional line `sentinel.next = newNode` (initially) or `prevNode.next = newNode` (later), because `prevNode` is guaranteed non-null. This uniformity dramatically reduces off-by-one and null-check bugs in production linked-list implementations.
How do you detect a cycle in a linked list, and why would one ever occur?
Cycles usually occur from a bug — for example, mistakenly setting the tail's `next` to point back into the list instead of to `null`, or from a double-insertion error. The standard detection method is Floyd's cycle-finding algorithm ("tortoise and hare"): advance one pointer one step at a time and another pointer two steps at a time; if they ever point to the same node, a cycle exists, and if the fast pointer reaches `null`, there is no cycle. This runs in O(n) time and O(1) extra space, in contrast to a hash-set-based approach that also detects cycles in O(n) time but uses O(n) extra space to record visited nodes. Interview questions frequently test this exact technique.
Does a linked list ever beat an array on raw speed, not just asymptotic complexity?
Only in specific circumstances. Because array traversal enjoys excellent cache locality (contiguous memory, predictable prefetching) while linked-list traversal typically incurs a cache miss per node (nodes are scattered across the heap), a dynamic array is frequently faster in practice for moderate n even for "O(n) shifting" insertions, since the shift is a tight, vectorized memcopy. Linked lists pull ahead mainly when you already hold a pointer to the splice location (no search needed), when insertions/deletions vastly outnumber accesses, or when you need stable references to elements that survive future insertions/deletions elsewhere — something array indices cannot promise once shifting occurs.
How does a linked list relate to stacks, queues, and hash tables?
A singly linked list with insertion/deletion restricted to the front alone directly implements a stack (LIFO) in O(1) per operation. A singly linked list with a tracked tail pointer, allowing insertion at the back and deletion at the front, directly implements a queue (FIFO); a doubly linked list generalizes this further into a deque supporting O(1) operations at both ends, as detailed in Stacks, Queues and Deques. Hash tables that resolve collisions via Separate Chaining Collision Resolution store each hash bucket as its own small linked list, so that multiple keys mapping to the same slot can coexist and be inserted/removed in O(1) expected time per bucket operation.
What is the space overhead of a linked list compared to an array, precisely?
An array of n elements of size s bytes uses roughly n·s bytes (plus, for a dynamic array, some unused reserved capacity from over-allocation). A singly linked list uses n·s bytes for data plus n·p bytes for `next` pointers, where p is the pointer size (commonly 8 bytes on 64-bit systems) — so overhead is one extra pointer per element. A doubly linked list doubles that pointer overhead to 2·n·p bytes for `prev` and `next`. For small elements (e.g., a single integer), this pointer overhead can dominate the actual payload, which is one reason arrays or hybrid structures (like unrolled linked lists, which store several elements per node) are often preferred when memory efficiency matters.