数组、链表与动态数组

数组随机访问 O(1) 但插入 O(n)，链表相反；动态数组通过倍增实现摊还 O(1) 追加。本章结合缓存局部性解释为什么现代硬件上数组几乎总是赢，以及链表仍然有用的场景。