两者都存储序列，但它们具有完全相反的成本特征。数组是连续内存，具有 O(1) 索引；链表是由指针连接的分散节点，在两端具有 O(1) 插入/删除，但不支持索引。
| Operation | Array (dynamic) | Linked list |
|---|
| Access by index | O(1) | O(n) |
| Search | O(n) | O(n) |
| Insert/delete at head | O(n) | O(1) |
| Insert/delete at tail | O(1) amortized | O(1) with tail ptr |
| Insert/delete in middle | O(n) | O(n) find + O(1) splice |
| Memory overhead | low | high (pointer per node) |
| Cache locality | excellent | poor |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
实际上，数组在大多数时候都能胜出，因为对于典型的大小，缓存局部性的影响远远超过 Big-O 的差异。
了解两者都能让你在面试中为你的选择辩护，而不是盲目默认 — 并解释为什么 "O(1) 插入" 很少能击败连续数组。