44、链表和数组有什么区别？

目录

一、先给一个面试中的标准结论

一句话总结

二、数组和链表的本质区别

1. 存储结构不同

数组

链表

面试表达方式

三、访问元素的方式不同

1. 数组支持随机访问

2. 链表不支持随机访问

面试高分说法

四、插入和删除的区别

1. 数组插入/删除

2. 链表插入/删除

但是要注意一个细节

面试中这样说最加分

五、查找效率的区别

数组查找

链表查找

六、内存使用上的区别

数组

优点

缺点

链表

优点

缺点

面试可加分点：CPU 缓存友好性

七、时间复杂度对比

八、为什么数组查找快，链表插入删除快？

数组查找快

链表插入删除快

九、实际使用场景怎么选？

适合用数组的场景

适合用链表的场景

十、链表有哪些类型？

1. 单链表

2. 双向链表

3. 循环链表

十一、JavaScript 里怎么理解数组和链表？

JavaScript 中的数组

JavaScript 中没有原生链表

十二、面试怎么回答更精彩？

版本1：基础标准版

版本2：高分版

十三、面试官继续追问时怎么答

追问1：链表一定比数组插入快吗？

追问2：数组一定比链表查找快吗？

追问3：为什么实际开发数组比链表常用？

追问4：LRU 为什么常用双向链表？

十四、如果让你一句话总结

十五、最适合背诵的面试模板

一、先给一个面试中的标准结论

一句话总结

数组适合查找，链表适合频繁插入和删除。
本质原因是：数组是连续内存空间，链表是节点通过指针连接的非连续结构。

这句话很适合先抛出来，再往下展开。

二、数组和链表的本质区别

1. 存储结构不同

数组

数组在内存中通常是连续存储的。

比如：

[10, 20, 30, 40]

它在内存里更像是挨着排好的：

1000 -> 10 1004 -> 20 1008 -> 30 1012 -> 40

因为地址连续，所以可以通过“首地址 + 偏移量”快速找到任意元素。

链表

链表的节点在内存中不要求连续，每个节点除了存数据，还会保存指向下一个节点的引用（指针）。

例如单链表：

[10 | next] -> [20 | next] -> [30 | next] -> [40 | null]

所以链表更像是“火车车厢”：

• 每节车厢知道下一节是谁
• 但车厢在停车场里不一定挨着放

面试表达方式

数组和链表最核心的区别在于底层存储结构。数组是连续内存空间，链表是通过指针把分散的节点串起来。这直接决定了它们在访问、插入、删除上的性能差异。

三、访问元素的方式不同

1. 数组支持随机访问

数组可以通过下标直接访问：

arr[5]

因为它知道起始地址，访问第i个元素时可以直接算出地址，所以时间复杂度是：

• O(1)

这也是为什么数组读取特别快。

2. 链表不支持随机访问

链表想访问第i个节点，不能直接跳过去，只能从头节点一个一个往后找：

head -> node1 -> node2 -> node3 -> ...

所以访问第i个节点的时间复杂度是：

• O(n)

面试高分说法

数组最大的优势是支持按下标随机访问，读取任意位置元素的复杂度是 O(1)；链表必须顺着指针逐个遍历，所以访问效率是 O(n)。

四、插入和删除的区别

这是最常考的点。

1. 数组插入/删除

假设数组中间插入一个元素：

[1, 2, 3, 4]

要在2后面插入99：

[1, 2, 99, 3, 4]

那么原来3、4这些元素都要往后挪。

同理，删除中间元素后，后面的元素也要整体前移。

所以数组在中间插入删除的时间复杂度一般是：

• O(n)

2. 链表插入/删除

链表只需要修改指针指向。

例如：

A -> B -> C

如果要在B和C之间插入X：

A -> B -> X -> C

只要改两个引用即可。

所以如果你已经拿到了要操作位置的前驱节点，那么链表的插入/删除复杂度可以做到：

• O(1)

但是要注意一个细节

很多人面试时会漏掉：

链表插入删除快，是建立在“已经找到目标位置”的前提下。

如果你还需要先遍历去找那个位置，那么查找过程还是：

• O(n)

所以更严谨地说：

• 查找位置：O(n)
• 找到后插入/删除：O(1)

面试中这样说最加分

链表插入删除快，不代表整体操作一定快。更准确地说，链表在已知目标节点位置的情况下，插入和删除只需要改指针，复杂度是 O(1)；但如果要先查找节点，整体仍然可能是 O(n)。

这句话很专业。

五、查找效率的区别

数组查找

如果只是按下标取值：

• O(1)

如果是按值查找某个元素：

• 无序数组：O(n)
• 有序数组：可以二分查找O(log n)

链表查找

链表无论按位置还是按值，基本都需要从头开始遍历：

• O(n)

而且链表很难像数组那样高效二分，因为它不支持随机访问。

六、内存使用上的区别

数组

优点

• 存储更紧凑
• 不需要额外存指针
• 缓存命中率通常更高

缺点

• 需要连续空间
• 扩容成本可能较高
• 动态数组扩容时可能会发生整体拷贝

链表

优点

• 不要求连续内存
• 动态扩展更灵活

缺点

• 每个节点都要额外存指针/引用
• 内存开销更大
• 访问时局部性差，缓存友好性不如数组

面试可加分点：CPU 缓存友好性

这个点很多人不会说，但说出来会比较亮眼。

数组因为内存连续，更符合 CPU 缓存预取机制，所以在实际工程里，虽然理论复杂度相同，数组很多时候也会更快。链表节点离散，缓存命中率低，遍历性能通常不如数组。

七、时间复杂度对比

下面这个表非常适合面试时总结。

八、为什么数组查找快，链表插入删除快？

这个问题经常是追问，本质上要回到“连续存储 vs 指针连接”。

数组查找快

因为数组内存连续，可以根据下标直接算地址。

公式理解：

元素地址 = 首地址 + 下标 * 每个元素大小

所以不用逐个找，直接定位。

链表插入删除快

因为链表节点之间靠指针连接，只要把前后节点的指针改一下就行，不需要整体搬移元素。

九、实际使用场景怎么选？

这部分很能体现你是否会“结合场景思考”。

适合用数组的场景

• 需要频繁按索引读取
• 数据量稳定
• 读取远多于插入删除
• 需要排序、二分查找
• 需要缓存友好、高性能遍历

例如：

• 商品列表
• 表格数据
• 前端大多数列表渲染
• 栈、队列的顺序存储实现

适合用链表的场景

• 频繁在中间插入或删除
• 不关心随机访问
• 数据结构需要灵活拼接
• 实现 LRU、队列、编辑器历史记录等场景

例如：

• LRU 缓存中双向链表
• 任务调度队列
• 撤销/重做记录
• 操作系统中的某些调度结构

十、链表有哪些类型？

面试有时会顺便追问。

1. 单链表

每个节点只保存下一个节点的指针。

A -> B -> C -> null

2. 双向链表

每个节点既有next，也有prev。

null <- A <-> B <-> C -> null

优点：

• 可以双向遍历
• 删除某节点更方便

3. 循环链表

最后一个节点指向头节点。

A -> B -> C -> A

适合某些循环调度场景。

十一、JavaScript 里怎么理解数组和链表？

这个点如果面试的是前端，可以说一下，会比较加分。

JavaScript 中的数组

JS 的数组并不是传统意义上最纯粹的底层静态数组，它更像是动态数组 + 对象特性的结合。

也就是说：

• 它可以动态扩容
• 可以有稀疏数组
• 本质上不是我们在 C/C++ 教材里最理想化的固定数组

但在面试讨论数据结构时，通常还是按“数组支持随机访问”的模型去理解。

JavaScript 中没有原生链表

JS 里没有内置LinkedList，链表一般需要手写节点结构：

class Node { constructor(value) { this.value = value this.next = null } }

这时候你可以顺带说明：

在前端业务开发里，数组远比链表常用；链表更多出现在算法题或某些底层结构设计里，比如 LRU 缓存常常会结合Map + 双向链表来实现。

这个回答很像有准备的人。

十二、面试怎么回答更精彩？

下面给你几个版本。

版本1：基础标准版

数组和链表最大的区别在于存储结构不同。数组是连续内存空间，链表是通过指针把多个节点连接起来的非连续结构。

这导致数组支持按下标随机访问，访问复杂度是 O(1)，而链表访问某个节点需要从头遍历，复杂度是 O(n)。

但在插入和删除方面，数组如果在中间插入或删除元素，通常需要移动后面的元素，所以是 O(n)；链表如果已经拿到目标位置，只需要修改指针，复杂度可以做到 O(1)。

所以一般来说，数组更适合查找和遍历，链表更适合频繁插入删除。

版本2：高分版

我一般会从存储结构、访问效率、插入删除成本和适用场景四个方面区分数组和链表。

第一，数组是连续内存空间，链表是分散节点通过指针连接的结构；
第二，数组支持随机访问，所以按下标取值是 O(1)，链表访问某个位置需要顺序遍历，是 O(n)；
第三，数组在中间插入删除通常需要搬移元素，所以是 O(n)，链表在已知目标节点位置时只需要改指针，插入删除是 O(1)；
第四，数组更适合读多写少、需要按索引访问的场景，链表更适合频繁插入删除的场景。

另外更严谨地说，链表插入删除快是建立在“已经定位到节点”的前提下，如果还需要先查找，整体复杂度依然可能是 O(n)。

从工程角度看，数组通常内存更紧凑、缓存友好，所以实际业务开发中使用频率也远高于链表；链表更多出现在算法题以及像 LRU 这种需要高效插删的结构里。

十三、面试官继续追问时怎么答

追问1：链表一定比数组插入快吗？

不一定。
如果链表还需要先遍历去找到插入位置，那查找本身就是 O(n)。
所以准确说法应该是：链表在已知节点位置时，插入删除更高效。

追问2：数组一定比链表查找快吗？

如果是按下标随机访问，数组明显更快，是 O(1)。
但如果是按值查找，数组和链表在无序情况下通常都是 O(n)。
如果数组有序，还可以使用二分查找做到 O(log n)，链表则不适合二分。

追问3：为什么实际开发数组比链表常用？

因为大多数业务场景更强调读取、遍历、渲染和按索引访问，而数组天然更方便；另外数组内存连续、缓存友好，实际性能也往往更好。链表虽然插删理论上有优势，但实现复杂，且很多业务里并不频繁在中间做高强度插删。

追问4：LRU 为什么常用双向链表？

因为 LRU 需要高效地把某个节点移动到头部，同时支持尾部淘汰。
双向链表可以在 O(1) 时间删除当前节点并插入到头部，再结合Map实现 O(1) 查询，就很适合做 LRU。

十四、如果让你一句话总结

你可以这样收尾：

数组和链表的核心区别是：数组用空间连续性换来了高效随机访问，链表用指针连接换来了更灵活的插入删除。实际选择时，要看业务更偏“查找读取”还是“频繁插删”。

十五、最适合背诵的面试模板

数组和链表最本质的区别是存储结构不同：数组是连续内存，链表是节点通过指针连接的非连续结构。
这决定了数组支持随机访问，所以按下标取值是 O(1)；链表必须顺序遍历，所以访问是 O(n)。
在插入删除方面，数组中间操作通常要移动元素，所以是 O(n)；链表在已知节点位置时只需要改指针，复杂度是 O(1)。
因此数组更适合读多写少、按索引访问频繁的场景，链表更适合频繁插入删除的场景。
不过工程里数组通常更常用，因为它内存更紧凑、遍历性能也更好；链表更多见于算法题或像 LRU 这样的结构设计中。