Array vs linked list vs hash map
| Operation | Array | Linked list | Hash map |
|---|---|---|---|
| Access by index | O(1) | O(n) | n/a |
| Search by value | O(n), O(log n) if sorted | O(n) | O(1) by key |
| Insert / delete at end | O(1) amortized | O(1) with tail | O(1) |
| Insert / delete at front or middle | O(n), shifts | O(1) if you hold the node | O(1) |
| Memory | contiguous, cache friendly | scattered, a pointer per node | extra for buckets |
Arrays win most real benchmarks because the CPU cache loves contiguous memory. Linked lists win when you hold node references and splice often, as in an LRU cache.