Linked List
Nodes scattered in memory, each pointing to the next. O(1) insertion or removal at a known node — but reaching that node costs O(n), and the CPU cache dislikes the pointer-chasing.
Each node holds a value and a pointer to the next node; the list is just a pointer to the head. Inserting at the head is two pointer writes. Deleting a node is one write — make its predecessor point past it — which is why lists shine when you already hold a reference to the position.
The trade-off is access: no indexing, only walking. Element k costs k hops, and because nodes are heap-scattered, every hop is a potential cache miss — an array often beats a list in wall-clock time even at the same big-O. Doubly linked variants add a prev pointer for O(1) removal anywhere and backward iteration, at the cost of one extra pointer per node.
Classic interview terrain: reverse in place by walking three pointers (prev, cur, next); detect cycles with Floyd's tortoise-and-hare; find the middle with slow/fast pointers.
Operations
| Operation | Complexity |
|---|---|
| insert head | O(1) |
| insert tail (with tail ptr) | O(1) |
| find / index | O(n) |
| delete known node | O(1) (Assumes you already hold a reference to the node. Singly-linked: true via the "copy next node's data" trick. Doubly-linked: true directly, since you can reach the predecessor.) |
Where it's used
Queues and deques, LRU caches (paired with a hash map), undo chains, any structure that splices ranges without shifting elements.