Linked Lists
A linked list is a linear data structure where elements (called nodes) are stored non-contiguously in memory. Each node contains a value and a pointer (or reference) to the next node in the sequence. Unlike arrays, linked lists excel at insertions and deletions in the middle of the sequence without shifting elements.
Singly Linked Lists
In a singly linked list, each node has a single pointer to the next node. Traversal is forward-only, starting from the head node.
Basic operations:
- Insert at head: O(1) — create a new node, point its
nextto the current head, update head. - Insert at tail: O(n) — traverse to the last node, point its
nextto the new node. - Delete a node: O(1) given a reference to the previous node; O(n) to find it first.
- Search: O(n) — linear scan.
Doubly Linked Lists
Each node in a doubly linked list has both a next and a prev pointer, enabling bidirectional traversal and O(1) deletion when given a direct node reference.
Trade-off: Each node requires an extra pointer (more memory), but operations like deleting a node or iterating backward become efficient.
Common Patterns
| Technique | Use Case | Complexity |
|---|---|---|
| Two-pointer (slow/fast) | Cycle detection, middle element | O(n) |
| Sentinel/dummy node | Simplify edge cases for insert/delete at head | O(1) overhead |
| Reversal in-place | Reverse all pointers | O(n) |
| Runner technique | Find k-th from end | O(n) |
Comparison: Arrays vs Linked Lists
| Operation | Array | Linked List |
|---|---|---|
| Random access | O(1) | O(n) |
| Insert at head | O(n) | O(1) |
| Insert at tail | O(1) amortized | O(n) (O(1) with tail ptr) |
| Delete at head | O(n) | O(1) |
| Memory overhead | Low (contiguous) | High (per-node pointers) |
| Cache locality | Excellent | Poor |
When to Use Linked Lists
- When frequent insertions and deletions occur at the beginning or middle of the sequence.
- When the size of the data is unpredictable and dynamic.
- When implementing queues, stacks, or adjacency lists for graphs.
When to Avoid Linked Lists
- When random access by index is needed (use arrays).
- When memory overhead and pointer chasing hurt cache performance.
- When the data fits comfortably in a contiguous array.