Linked Lists — Singly, Doubly & Circular
Master linked list data structures for coding interviews: node pointer manipulation, list reversal, merging two sorted lists, and Floyd's cycle detection algorithm explained step by step.
A linked list stores each element in a node that holds the value plus a pointer to the next node. Nodes live wherever the allocator puts them, so the list has no contiguity and no index arithmetic. You hold a reference to the head, and every other node is reachable only by walking the chain.
That single design choice explains every trade-off. Splicing a node in or out is just rewiring two pointers, so it is O(1) once you are already standing at the right place. But getting to that place is the expensive part: reaching index i costs i hops, and there is no way to shortcut it.
Three variants cover almost all real use. A singly linked list has one next pointer per node — cheapest, but you can only move forward. A doubly linked list adds a prev pointer, which is what makes O(1) deletion possible when you hold only the node itself, and is why LRU caches and most language-level deque types use it. A circular list joins tail back to head, useful for round-robin scheduling and ring buffers.
| Operation | Array | Linked List |
|---|---|---|
| Random access by index | O(1) | O(n) |
| Search by value | O(n) | O(n) |
| Insert/delete at head | O(n) | O(1) |
| Insert/delete at tail | O(1) amortized | O(1) with tail pointer |
| Insert/delete at known node | O(n) — shifting | O(1) — pointer rewiring |
| Split or concatenate | O(n) | O(1) |
| Memory overhead | None | One or two pointers per node |
| Cache behaviour | Sequential, prefetch-friendly | Pointer chasing, poor locality |
Note the row that actually matters in interviews: insert or delete at a node you already have a reference to. Arrays must shift everything after it; a linked list just relinks. Whenever a problem hands you the node instead of the index, the linked list is usually the intended structure.
A practical caution
Linked lists look great in Big-O tables and often lose badly in reality because every node is a potential cache miss, and a 16-byte pointer overhead per element adds up. A dynamic array beats a linked list at traversal-heavy work even where the asymptotics say otherwise. Reach for a linked list when you genuinely need O(1) splicing or stable node references, not by default.