Breaking the Contiguous Rule
A Linked List abandons the requirement for contiguous memory. Instead, it consists of Nodes scattered anywhere in RAM. Each node holds two things:
- The Value (the actual data).
- A Pointer (the memory address of the next node).
The list is navigated by following pointers from one node to the next, like a treasure hunt where each clue tells you where to find the next one. The list starts at a special reference called the Head and ends when a node's pointer is null.
Head
|
[Value: 10 | Next: →] → [Value: 20 | Next: →] → [Value: 30 | Next: null]
Trade-offs vs. Arrays
| Operation | Array | Linked List | Why |
|---|---|---|---|
| Read by index | O(1) | O(N) | No direct address calculation possible |
| Insert at front | O(N) | O(1) | Array shifts; list just updates Head pointer |
| Insert at back | O(1) amortized | O(N) or O(1) with tail pointer | Must traverse to end without tail |
| Delete from front | O(N) | O(1) | Array shifts; list just moves Head |
| Search | O(N) | O(N) | Both must scan linearly |
| Memory overhead | Low | Higher | Each node stores an extra pointer |
The critical insight: Linked Lists trade random access for O(1) insertion and deletion at known positions. If you have a reference to a node, inserting before or after it requires only pointer updates — no shifting, no copying.
Singly vs. Doubly Linked Lists
A Singly Linked List has one pointer per node (next). A Doubly Linked List has two pointers per node (next and prev), enabling traversal in both directions. The cost is double the pointer memory overhead. Python's collections.deque is implemented as a doubly linked list, which is why it supports O(1) append and pop from both ends.