数据结构（数组和链表）

为什么同样是存数据，数组查得飞快，链表删得轻松？一篇把数组和链表讲明白

很多人第一次学数据结构时，都会有一种错觉：

数组和链表，不就是两种“装数据的容器”吗？

可一旦开始写代码、做题、面试，这个错觉很快就会被打碎。

• 为什么数组能用下标a[3]一步拿到第 4 个元素，链表却不行？
• 为什么链表看起来删除很方便，但真实做题时又经常不如数组顺手？
• 为什么大多数工程项目里，大家更常用vector、ArrayList，而不是链表？

说到底，不是你记不住定义，而是你还没有真正看见它们背后的“空间结构”。

这篇文章不打算只告诉你“数组是连续的，链表是离散的”这几个字就结束。我们会从图示、生活类比、代码实现、复杂度对比一路讲到“什么时候该选谁”。读完之后，你至少会收获三件事：

• 真正理解数组和链表的底层差异，而不是死记硬背
• 看懂常见操作为什么有的快、有的慢
• 做题或写代码时，知道自己该优先考虑哪一种结构

一句话先讲透本质

如果只用一句话概括：

• 数组：把元素放在一段连续的内存空间里
• 链表：每个元素单独存放，再用指针把它们串起来

这句话很短，但它几乎决定了后面所有行为。

你可以先把它们想成两个完全不同的世界：

• 数组像一排编号整齐的公寓，想找 5 号房，直接按门牌号过去
• 链表像一节一节串起来的火车车厢，想到第 5 节，得先经过前 4 节

很多后面的结论，都是从这两个画面自然推出来的。

一图先看懂：数组和链表到底差在哪

如果平台支持 Mermaid，可以直接看这张图：

如果平台不支持 Mermaid，也可以直接看下面这个 ASCII 图：

数组： 地址连续 下标: 0 1 2 3 值: [10] [20] [30] [40] 链表： 地址可以不连续，靠 next 指针串起来 [10|next] -> [20|next] -> [30|next] -> [40|null]

你现在先记住两个结论：

• 数组强在“找得快”
• 链表强在“改链接”

后面的一切复杂度，都是这两个特点的展开。

数组：为什么它查得这么快

1. 数组的核心优势，是可以随机访问

数组最厉害的地方，不是“能存很多元素”，而是：

只要知道起始地址和元素大小，就能立刻算出任意下标的位置。

比如一个int占 4 个字节，数组首地址是base，那第i个元素的位置就是：

base + i * 4

这就是为什么我们可以直接写：

arr[3]

它不是“从头数到第 4 个”，而是直接算地址，一步命中。

所以，数组在“按下标取值”这件事上非常强。

2. 数组为什么插入和删除往往比较慢

数组的问题也正是因为它“太整齐”了。

假设当前数组是：

[10] [20] [30] [40]

如果你想在20和30之间插入一个25，为了保证数组依然连续，后面的元素都要整体往后挪：

[10] [20] [25] [30] [40]

也就是说：

• 中间插入，后面元素要搬家
• 中间删除，后面元素也要整体补位

所以数组常见的特点是：

• 查询快
• 中间插入、删除偏慢

3. 数组并不一定是“固定长度”

很多初学者一提到数组，就会把它和“长度固定”完全绑定。

这并不准确。

严格说：

• 传统静态数组长度通常固定
• vector、ArrayList这类动态数组，本质上仍然是数组，只是会在容量不够时扩容

扩容时会发生什么？

• 申请一块更大的连续空间
• 把旧数据整体拷贝过去
• 释放旧空间

这也是为什么动态数组平时用起来很顺手，但在极少数扩容时，会有一次额外成本。

4. 用 C++ 写一个最简单的数组例子

#include<iostream>usingnamespacestd;intmain(){intarr[5]={10,20,30,40,50};cout<<arr[0]<<endl;// 10cout<<arr[3]<<endl;// 40arr[2]=99;cout<<arr[2]<<endl;// 99return0;}

这段代码最值得你注意的，不是语法，而是这种体验：

• 访问第几个元素非常直接
• 修改第几个元素也非常直接

只要你有下标，数组就像一本带页码的书，翻页特别快。

链表：为什么它删起来更灵活

1. 链表不是“排成一排”，而是“串成一串”

链表和数组最大的区别，不是长得不一样，而是它根本不要求内存连续。

链表中的每个节点，通常包含两部分：

• 当前节点存的数据
• 指向下一个节点的指针

比如一个单链表节点，通常可以写成：

structListNode{intval;ListNode*next;};

它的逻辑结构像这样：

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

注意，这些节点在内存里不一定挨着放。
它们之所以能形成一个整体，是因为每个节点都记住了“下一个是谁”。

2. 链表为什么插入和删除更自然

假设现在有这样一条链：

10 -> 20 -> 40

如果你想把30插入到20和40之间，链表不需要整体搬家，只需要改两个指针：

10 -> 20 -> 30 -> 40

同理，删除某个节点，本质上也不是“挪数据”，而是“绕过去”：

10 -> 20 -> 30 -> 40 删除 30 后 10 -> 20 -------> 40

所以链表的强项在于：

• 已知位置后，插入方便
• 已知位置后，删除方便

注意这里有四个非常重要的字：

已知位置后

这是很多人第一次学链表最容易忽略的地方。

3. 链表真的删除更快吗

这句话要分情况看。

如果你已经拿到了待删除节点的前一个节点，那么链表删除确实很快，因为只需要改指针。

但如果你连目标节点在哪都不知道，那你还是得从头一个个找过去。

这意味着：

• 链表“改结构”很快
• 链表“找位置”通常不快

所以不要把“链表删除快”理解成“任何删除都快”。
真正准确的说法应该是：

链表在找到插入点或删除点之后，修改成本低。

4. 用 C++ 写一个最基础的单链表

#include<iostream>usingnamespacestd;structListNode{intval;ListNode*next;ListNode(intx):val(x),next(nullptr){}};intmain(){ListNode*head=newListNode(10);head->next=newListNode(20);head->next->next=newListNode(30);ListNode*cur=head;while(cur!=nullptr){cout<<cur->val<<" ";cur=cur->next;}return0;}

这段代码最重要的体验是：

• 访问一个节点后，只能顺着next往后走
• 不能像数组那样直接跳到第k个节点

这就是链表和数组最本质的操作差异。

把它们放到一起对比，你会更清楚

这张表里最值得你记住的一点是：

数组赢在连续，链表赢在连接。

为什么工程里很多时候更常用数组，而不是链表

这恰恰是最容易被忽视、但又最接近真实开发的一点。

很多入门文章会让人产生一种印象：

• 数组查询快
• 链表插删快
• 所以它们像是平起平坐的两种选择

但真实工程里，动态数组往往更常用，原因有三个：

1. 大多数场景里，“访问”比“中间频繁插删”更常见

比如：

• 展示商品列表
• 保存成绩数据
• 存储日志结果
• 遍历配置项

这些场景里，按顺序访问和按下标访问远比“中间插一个、删一个”更常见。

2. 数组更缓存友好

因为数组是连续存储，CPU 读取时更容易把相邻元素一起加载进缓存，所以在遍历时通常表现很好。

链表虽然理论上插删方便，但它的节点分散在内存各处，CPU 在访问时不够“顺路”，所以很多时候实际性能并不占优。

3. 链表的指针操作更容易写错

学数组时，最常见的问题是越界。

学链表时，常见问题会更多：

• 忘记处理空链表
• 忘记更新头节点
• 指针断链
• 内存泄漏
• next指错位置

这也是为什么很多语言的标准库里，大家更常先选动态数组，再根据需求考虑链表。

所以你可以先记住一个很实用的结论：

如果没有明确理由，大多数时候先考虑数组；如果场景核心是频繁插删、结构动态变化，再认真考虑链表。

两个经典场景，帮你真正建立直觉

场景一：为什么通讯录更像数组思维

假设你有一个学生信息表，经常会做这些事：

• 查看第 100 个学生
• 遍历所有学生
• 按下标修改某个人的信息

这时候数组特别适合，因为它最擅长：

• 快速定位
• 顺序遍历
• 按下标读写

如果这里换成链表，你每次想找第 100 个学生，都得从头一路走过去，体验会非常差。

场景二：为什么火车车厢拼接更像链表思维

想象一列火车：

车头 -> 1号车厢 -> 2号车厢 -> 4号车厢

如果现在要把 3 号车厢插到 2 号和 4 号之间，你并不需要把所有车厢搬一遍，只要重新连接：

车头 -> 1号车厢 -> 2号车厢 -> 3号车厢 -> 4号车厢

这就是典型的链表思维：

• 核心不是“位置编号”
• 而是“前后关系”

只要前后指向改对了，结构就成立。

初学者最容易混淆的 4 个点

1. 链表插入是O(1)，不等于“做题时总是更快”

如果题目要你“找到第 100 个位置再插入”，那前面的查找过程仍然要花O(n)。

2. 数组删除慢，不等于数组就没用

很多题目根本不强调中间删除，而是强调：

• 快速访问
• 顺序处理
• 批量遍历

这时候数组非常合适。

3.vector本质上仍然是数组

很多人学了 C++ 之后，看到vector就忘了它底层其实还是动态数组。

它的随机访问快，本质原因仍然是连续存储。

4. 链表不只是“多了个指针”

多一个指针，不只是多一点空间那么简单。
它会影响：

• 存储方式
• 访问方式
• 插删方式
• 性能表现

所以链表和数组不是“长得不同”，而是“思维方式不同”。

面试和做题时，什么时候该想到数组，什么时候该想到链表

看到下面这些味道，优先想数组：

• 需要通过下标快速访问
• 需要频繁遍历
• 需要二分查找
• 需要双指针、滑动窗口、前缀和
• 数据整体连续、读多改少

看到下面这些味道，优先想链表：

• 结构经常断开再重连
• 需要在某些已知节点附近频繁插入、删除
• 题目出现“反转链表”“合并链表”“删除节点”“环形链表”
• 更关心节点之间的连接关系，而不是下标

一句话帮助你快速判断：

要靠编号快速定位，用数组；要靠前后关系灵活改结构，想链表。

时间复杂度别死背，顺着结构去理解

如果你总是记不住复杂度，就不要死背表格。
你只要反复问自己两个问题：

1. 它能不能直接定位到目标位置？
2. 它需不需要为保持结构而整体搬家？

能回答这两个问题，很多复杂度自然就能推出来。

最后总结：别把它们当定义，要把它们当画面

很多人学数组和链表学不会，不是因为代码难，而是因为脑子里没有图。

所以最后请你只记住这两个画面：

• 数组：像一排编号整齐的房间，找第几个，直接按门牌号去
• 链表：像一串手拉手的人，想去后面的人，得顺着前面一个个走

然后再把所有知识挂回这两个画面上：

• 数组为什么查得快？因为它有“编号”，而且空间连续
• 数组为什么中间插删慢？因为一改位置，后面就要整体挪动
• 链表为什么插删灵活？因为它改的是连接关系，不是整体搬家
• 链表为什么访问慢？因为它没有下标，只能顺着指针往后找

真正学会数据结构，不是会背“数组连续、链表离散”，而是你在看到题目时，脑子里能立刻浮现出结构画面，并知道应该利用它的哪一个优势。

如果你愿意继续往下学，下一步可以接着攻克这些高频内容：

• 数组方向：双指针、滑动窗口、前缀和、二分查找
• 链表方向：反转链表、快慢指针、合并有序链表、环形链表

当你把“结构”看清楚之后，很多题目就不再是硬做，而是顺着数据怎么存、怎么动，自然推出来。