Data Structures: Arrays vs Linked Lists
Arrays and linked lists both store sequences of elements but with different tradeoffs for access, insertion, and deletion. This post compares them so you can pick the right one for your use case.
Array
- Layout: Contiguous memory; elements are stored one after another.
- Indexing: By position (0, 1, 2, …). O(1) access by index.
- Insert/delete at end: O(1) amortized (may need to grow capacity).
- Insert/delete in middle: O(n) — elements must be shifted.
- Search by value: O(n) unless sorted (then O(log n) with binary search).
- Cache: Good — contiguous data benefits from cache lines.
Linked list
- Layout: Nodes; each node holds a value and a reference to the next (and optionally previous) node.
- Indexing: No direct index. To get the i-th element you traverse from the head. O(n) access by position.
- Insert/delete at head (or with pointer to node): O(1). No shifting.
- Insert/delete in middle: O(1) if you already have a pointer to the node (or its predecessor); otherwise O(n) to find it.
- Search by value: O(n); no random access.
- Cache: Weaker — nodes can be scattered in memory.
Comparison at a glance
| Operation | Array | Linked list |
|---|---|---|
| Access by index | O(1) | O(n) |
| Insert at end | O(1) amort. | O(1)* |
| Insert at head | O(n) | O(1) |
| Insert in middle | O(n) | O(1)** |
| Delete by position | O(n) | O(1)** |
| Search by value | O(n) | O(n) |
*If you keep a tail pointer. **If you have a pointer to the node (or predecessor).