Arrays & Linked Lists
Sequential vs node-based storage
The Fundamental Trade-off
Arrays and linked lists represent two fundamentally different approaches to storing sequential data. Arrays store elements in contiguous memory, enabling O(1) random access but O(n) insertions. Linked lists store elements in nodes connected by pointers, enabling O(1) insertions at known positions but O(n) access.
Use Arrays When:
- • You need fast random access by index
- • The size is relatively fixed
- • Memory locality matters (cache efficiency)
- • You mostly append/remove from the end
Use Linked Lists When:
- • You frequently insert/delete in the middle
- • The size changes dramatically
- • You need O(1) insertion at head
- • Memory fragmentation is acceptable
Array Visualization
10
[0]
25
[1]
37
[2]
42
[3]
58
[4]
Complexity Comparison
| Operation | Array | Linked List |
|---|---|---|
| Access by index | O(1) | O(n) |
| Search | O(n) | O(n) |
| Insert at beginning | O(n) | O(1) |
| Insert at end | O(1) | O(n) |
| Insert at middle | O(n) | O(1) |
| Delete from middle | O(n) | O(1) |
* Linked list insert/delete at middle assumes you already have a reference to the node. Finding that node first takes O(n).