数组和链表有什么区别？｜阿里巴巴后端开发面经解析

60 秒回答模板

数组和链表的核心区别在于内存布局。数组是一段连续空间，可以通过下标直接计算元素地址，所以随机访问是 O(1)，缓存局部性好；但如果在中间插入或删除，需要移动后续元素，通常是 O(n)，动态数组扩容时还可能申请新空间并复制元素。链表由一个个节点组成，节点在内存中不要求连续，每个节点保存数据和指向其他节点的引用，所以不能按下标直接跳到某个位置，查找通常是 O(n)；但如果已经拿到要操作位置的前驱节点或当前节点，插入删除只改引用，时间是 O(1)。不过链表每个节点有额外引用开销，内存占用更高，缓存命中率通常更差。Java 里 ArrayList 底层是数组，适合读多、按下标访问多、尾部追加多的场景；LinkedList 是双向链表，也实现了 Deque，适合在已持有节点位置或频繁队头队尾操作的场景，但普通按下标访问和遍历性能通常不如 ArrayList。

考点 内存布局

主线 访问效率

易错点 只说数组查询快、链表插入删除快，没有解释内存布局这个根…

深入解析

内存布局

数组的元素在逻辑和物理上通常是连续排列的，因此第 i 个元素地址可以由起始地址、下标和元素大小计算出来。链表的节点通常分散在堆上，每个节点除了数据，还保存 next，双向链表还保存 prev。数组的连续性带来随机访问和缓存优势；链表的离散性带来灵活连接，但也带来引用开销、对象头开销和更多内存访问跳转。

访问效率

数组支持真正的随机访问，按下标访问是 O(1)，前提是下标合法且底层数组已存在。链表按下标访问不是 O(1)，因为必须从头或尾逐个节点走过去，单链表通常是 O(n)，双向链表可以从更近的一端开始，但复杂度仍是 O(n)。这也是很多工程场景中 LinkedList 的 get(index) 很慢的根本原因。

插入删除

数组在尾部有空余容量时追加通常是 O(1)，但在头部或中间插入、删除时要移动一段元素，平均是 O(n)。链表如果已经定位到目标节点或前驱节点，插入删除只需要改引用，是 O(1)；但如果操作条件只是“在第 k 个位置插入”或“删除某个值”，定位过程仍然是 O(n)，整体不能简单说成 O(1)。

缓存局部性

数组连续存储，CPU 读取一个元素时往往会把相邻元素所在的缓存行一起加载进来，顺序遍历时缓存命中率高。链表节点分散，遍历时每一步都要跟随引用跳到另一个地址，容易产生缓存未命中。实际工程里，即使链表某些操作理论复杂度更好，常数开销和缓存损失也可能让它比数组慢。

扩容机制

普通静态数组容量固定；动态数组会在容量不足时扩容，通常申请更大的连续空间，再把旧元素复制过去。比如 Java ArrayList 会维护一个 Object[]，添加元素超过容量时触发扩容。尾部 add 的摊还复杂度是 O(1)，但单次扩容是 O(n)。链表没有整体扩容问题，新增节点时单独申请节点对象，但频繁分配对象也会增加 GC 压力。

链表变体

单链表每个节点只有 next，适合单向遍历，删除某节点通常需要知道前驱。双向链表有 prev 和 next，便于前后移动，也便于删除当前节点，但内存开销更高。循环链表的尾节点会连回头节点，适合循环调度等场景。带哨兵节点的链表可以简化头尾边界处理，减少特殊分支。

Java 对照

ArrayList 底层是动态数组，get(index) 是 O(1)，尾部 add 摊还 O(1)，中间插入删除通常 O(n)，内存紧凑且遍历快。LinkedList 底层是双向链表，头尾 add/remove 是 O(1)，但 get(index) 是 O(n)，每个节点都有额外对象和引用成本。实际 Java 开发中，除非明确需要 Deque 或频繁头尾操作，普通列表场景通常优先 ArrayList。

工程选型

读多、遍历多、按下标访问多、数据规模较稳定时，数组或 ArrayList 更合适。频繁在头尾插入删除时，可以考虑 LinkedList、ArrayDeque 或专门队列结构；如果是频繁中间插入删除，链表也只有在已经持有节点引用时才有优势。面试回答要避免只背 O(1) 和 O(n)，要讲清楚定位成本、缓存、内存和语言运行时开销。

易错点

只说数组查询快、链表插入删除快，没有解释内存布局这个根因。
把链表插入删除直接说成 O(1)，忽略定位节点的 O(n) 成本。
忽略 CPU 缓存局部性，导致答案只停留在教科书复杂度。
把 ArrayList 和数组、LinkedList 和链表机械等同，没提动态扩容、对象引用、GC 和双向链表实现。
认为 LinkedList 在 Java 中适合大量中间插入删除，但如果没有节点引用，按下标定位仍然很慢。
忽略数组扩容成本，只说尾插 O(1)，没有说明摊还复杂度。

面试官追问

为什么数组能 O(1) 随机访问？

因为数组元素连续存放，知道起始地址、元素大小和下标后，可以直接计算目标地址，不需要逐个遍历。这也是数组按下标访问、二分查找和顺序扫描都比较高效的基础。

链表插入删除一定比数组快吗？

不一定。只有在已经找到目标位置时，链表改引用才是 O(1)。如果还要先查找位置，查找成本是 O(n)。同时链表缓存局部性差，节点对象和引用也有额外开销，实际运行可能更慢。

ArrayList 和 LinkedList 怎么选？

大多数普通列表场景选 ArrayList，因为随机访问快、遍历快、内存更紧凑。只有明确需要频繁头尾操作或 Deque 语义时，才考虑 LinkedList，但很多队列场景 ArrayDeque 也更合适。

数组的插入删除为什么是 O(n)？

如果在中间插入，需要把插入位置之后的元素整体后移；删除时需要把后续元素前移以保持连续性。移动元素数量和数据规模相关，所以平均复杂度是 O(n)。

为什么说复杂度要看前提？

因为链表删除 O(1) 默认已经拿到要删除的节点或其前驱；数组尾插 O(1) 默认还有容量，动态数组还要考虑扩容的摊还成本。脱离前提背复杂度是不准确的。