数组和链表、队列和栈有什么区别？｜阿里巴巴算法面经解析

60 秒回答模板

可以从“存储结构”和“抽象规则”两层回答。数组通常在连续内存中存放元素，能通过首地址加下标偏移直接定位元素，因此随机访问是 O(1)，遍历时缓存局部性好，适合频繁按下标读取、排序、二分和动态规划；缺点是头部或中间插入删除要移动元素，动态扩容还可能发生重新分配和复制。链表由节点和指针组成，不要求连续内存，在已经定位节点或前驱节点时插入删除可以是 O(1)，容量增长灵活；缺点是访问第 k 个元素需要遍历，额外指针占空间，缓存命中率较差。队列强调先进先出，适合任务调度、消息缓冲、生产者消费者、广度优先搜索；栈强调后进先出，适合函数调用、递归、括号匹配、深度优先搜索、撤销回退。工程上要根据访问模式选择实现：栈常用数组维护栈顶下标，队列常用循环数组维护 head/tail，也可以用链表维护头尾指针。

考点 先区分两类概念

主线 数组和链表的内存布局

易错点 只背数组查找快、链表增删快，没有说明随机访问、定位成本…

深入解析

先区分两类概念

数组和链表讨论的是数据如何组织在内存中，属于底层线性存储结构；队列和栈讨论的是元素允许怎样进入和离开，属于抽象数据类型。这个区分非常关键：数组不等于栈，链表也不等于队列。栈可以由数组实现，也可以由链表实现；队列可以由循环数组实现，也可以由链表实现。底层结构决定访问、扩容、内存和缓存成本，抽象规则决定业务语义和操作约束。

数组和链表的内存布局

数组的逻辑元素连续，典型实现中物理内存也连续。知道首地址、元素大小和下标后，就能直接算出目标元素地址，所以数组支持按下标快速访问。链表由节点组成，每个节点保存数据和指向后继节点的指针，节点可以分散在堆内不同位置。链表不需要连续空间，新增节点更灵活，但每个节点都有额外指针开销，并且访问下一个节点需要沿指针跳转。

随机访问与遍历效率

数组最大的优势是 O(1) 随机访问，这对二分查找、动态规划表、矩阵存储、按位置读取都很重要。链表访问第 k 个元素需要从头或尾逐个走到目标位置，通常是 O(n)。即使都是顺序遍历，数组的实际性能也常常更好，因为连续内存利于 CPU 预取和缓存命中；链表节点分散，指针跳转会造成更多缓存未命中。

插入删除的真实前提

“链表增删快、数组增删慢”必须加前提。数组尾部追加在容量足够时是 O(1)，动态数组连续尾插还能做到均摊 O(1)；但头部或中间插入删除需要移动后续元素，通常是 O(n)。链表在已经定位目标节点或前驱节点时，插入删除只需改指针，是 O(1)；但如果还需要先查找位置，定位本身仍然是 O(n)。所以链表不是所有增删都天然更快。

扩容与空间成本

固定数组容量确定后不能无限原地增长，动态数组容量不足时通常申请更大的连续空间，再复制旧元素，这会带来单次 O(n) 扩容成本。链表不需要整体扩容，每次新增节点单独申请内存即可，但额外指针让空间开销更高，频繁分配释放还可能增加内存碎片和分配器压力。数组更紧凑，链表更灵活，选择时要看容量变化和性能抖动能否接受。

队列和栈的操作规则

队列强调先进先出，先进入的数据先被取出，典型操作是队尾入队、队头出队，适合排队、缓冲、任务调度、BFS 和消息消费。栈强调后进先出，最后进入的数据最先被取出，典型操作是栈顶入栈、出栈、查看栈顶，适合函数调用、递归展开、括号匹配、DFS、表达式求值和撤销恢复。它们的差异不是谁更快，而是访问顺序表达的问题模型不同。

实现方式与工程取舍

用数组实现栈很自然，只要维护栈顶下标，入栈出栈都发生在末尾，缓存局部性好。用链表实现栈也简单，把头节点当作栈顶即可，但有额外指针开销。队列如果用普通数组从头部删除，会频繁移动元素，更常见的是循环数组，用 head 和 tail 复用空间；链表队列维护头尾指针，入队改尾指针、出队改头指针，容量灵活但局部性较差。工程选择要看数据规模、访问方式、扩容频率和延迟稳定性。

易错点

只背数组查找快、链表增删快，没有说明随机访问、定位成本和插入删除位置的前提。
把队列和栈说成具体存储结构，忽略它们是抽象数据类型。
认为链表一定节省空间，实际上链表节点需要额外指针，空间开销通常比数组更高。
忽略缓存局部性，只从大 O 复杂度判断真实性能。
认为数组扩容每次都是 O(n)，没有说明动态数组尾插的均摊 O(1)。
讨论队列数组实现时没有提循环数组，导致头部出队搬移元素的问题没有解决。

面试官追问

为什么数组随机访问是 O(1)，链表不是？

数组元素按固定大小连续排列，可以通过首地址和下标偏移直接计算目标地址；链表节点不连续，只能沿 next 指针逐个访问，所以访问第 k 个节点通常需要 O(k)，最坏是 O(n)。

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

不一定。链表只有在已经定位插入或删除位置时，修改指针才是 O(1)。如果要先查找目标节点，查找过程仍然是 O(n)。数组中间插入删除通常要移动元素，但尾部追加在容量足够时是 O(1)。

为什么工程里很多时候更偏向数组？

现代硬件对连续内存更友好，数组缓存局部性好，遍历时 CPU 可以预取后续数据，常数性能优秀。链表虽然局部改指针快，但节点分散、指针跳转多、缓存命中率低，还会带来额外内存和分配成本。

队列用数组实现时为什么常用循环数组？

普通数组如果每次从头部出队都移动后续元素，出队会变成 O(n)。循环数组用 head 和 tail 指针把数组逻辑上首尾相接，出队只移动 head，入队只移动 tail，从而让入队和出队保持 O(1)。

栈和递归有什么关系？

递归调用依赖调用栈保存每一层函数的局部变量、返回地址和执行状态。最后进入的函数调用必须最先返回，正好符合栈的后进先出规则，因此很多递归算法也可以改写成显式栈。