2279 字

6 分钟

捆绑游戏——链表

2026-03-28

数据结构

/

c

/

c++

/

链表

/

指针

捆绑游戏——初见链表#

一、背景#

我们都知道，咱们的数组存储数据会把他们存储在连续的虚拟内存地址中。就像是你按下电梯，来到一层楼，这一层楼的房间后是101，102等等紧密挨着且连续的。😋

这样的设定使得查找数组中的元素变得十分简单。✊

但是捏，数组也存在自身的痛点！为了解决数组的痛点，所以有了链表。

adad

二、数组的痛点与解决#

这里主要介绍一下数组的痛点，至于链表后续会说明，在这里有个模糊的概念或者直接跳过链表的解就行！

1.固定内存长度，无法更改#

比如你声明了int array[10]，就得给它挖好10个坑。

如果你只存了3个数，剩下7个坑就浪费了。一个int整型占四个字节，那么就浪费了28个字节！
如果你想存11个数？爆栈！ 直接报错，除非你重新挖个大坑把原来的土全搬过去（扩容），累死人。

链表的解：随心所欲，动态扩容。

链表不需要预先挖坑。来一个数据，我就在内存里随便找个空地儿放一个
节点，然后用线连起来。内存里哪怕只有碎片空间，链表也能塞进去。想存1万个？没问题，只要内存够，它能无限长。

这里你可能会说不是还有动态数组吗？但是动态数组扩容的原理还是复制原来的数组，再新建一个数组，造成了性能开销🤔

2.插队删人，全员搬家（插入/删除痛点）#

数组的痛：这是数组最恶心的地方。🤣

假设数组有1000个元素，你要在第1个位置插个数据。
对不起，后面1000个元素全得往后挪一位！这时间复杂度是 O(n)，数据量大时慢得像蜗牛。🐌🐌

链表的解：

改个纸条就行，无需搬家。
你想在A和B之间插个C？
只需要把A手里的纸条改成“去找C”，再给C一张纸条“去找B”。
完事！不管后面有1万个节点还是1亿个节点，都跟这事儿没关系，它们原地不动。时间复杂度 O(1)，爽不爽？爽！✊👌

3.内存必须连续，容易“卡壳”（内存分配痛点）#

数组的痛：数组要求内存必须是连续的。（这里指的是虚拟内存哦！物理内存因为页表的存在，可能是不连续的🐧）

比如你要申请100MB的数组，内存里必须有一块完整的、连续的100MB空地。
如果内存里虽然有空地，但都是东一块西一块的碎片（内存碎片），数组就申请失败（Stack Overflow 听过吧？就是这个闹的）。

链表的解：不挑食，有缝就钻。

链表节点在内存里可以是分散的。
节点A在内存开头，节点B可以在内存结尾，节点C可以在中间。只要指针连得上，它们住哪儿都行。这极大地提高了内存利用率。

三、链表的定义#

好啦，介绍一下链表吧。链表里的每一个元素叫节点（node）。每个节点就两样东西：数据域：存真正的数据（比如你的工资、名字）。指针域：存下一个节点的地址（一张小纸条）。

胖狗抽象😎

铁索连环的故事都听过吧。我来改编一下。😋

假设曹老板有十条大型战船，每艘船上都有几百个赛博坦星人，但是因为河流湍急的原因不得不用铁索将其一一相连。船的面积十分之庞大，对于人类来说，要从一艘船上另一艘船需要很大的精力！所以每艘船上都有一座传送阵！？🤔。

东吴完全拿曹老板没有办法，只得派出大将黄忠施展一手苦肉计（请鞭笞我吧，公瑾！😚）。曹老板喜好龙阳😋，觉得黄忠这小子有点用处，决定把他接到船上。

黄忠上船后就表现的十分乖巧，为的就是打听到传送阵的位置。在曹老板的战船上混了五天后，他摸清了所有传送阵的位置（每个传送阵会标记下一个传送阵的位置，而第一个传送阵的位置十分隐秘，只有曹军知道在哪）。黄忠体内有个小洞天，里面装着周瑜嘱托的异能炸弹，能轻松摧毁曹老板的战船，但是投射距离短并且起爆时间长，所以不得不将它们偷偷安置在船上。

这五天黄忠忍辱负重，每天都要看看自己洞天里的炸弹有没有因为曹老板搞里头而糟蹋了，咳咳· · · · · ·你绝对想歪了！搞里头说的是曹老板疑心重，喂给黄忠神秘小药水。🤔

曹老板的船正式抵达赤壁，东吴水师与其战斗起来。

有了东吴水师牵制赛博坦星人，黄忠顺利安置了所有炸弹并成功完成任务！

好啦，上面的故事里，每一艘船上的赛博坦星人就是重要的“数据”！没了他们，曹军也就失去了战力。而传送阵则是指针域，从第一艘船开始，一一把后面的船连起来（一个传送阵记录着下一个船和传送阵的地址，相当于前一个指针记录着后一块数据与指针的内存地址。最后一艘的传送阵则指向一个无效地址也就是0或者null）

那么这个时候就有人要问了，如何确定第一艘船的位置呢？实际上还有一个指针作为头指针会指向首元节点，也就是第一艘船。这份地图就藏在曹军手里（黄忠用酒套出了位置），只有按顺序从第一艘船开始才能保证不重复不遗漏且时间最短！🤔

fyh

四、一表速比#

特性	数组	链表	谁赢了？
内存布局	必须连续，像排排坐	分散随机，像满天星	链表（灵活）
大小	固定，很难改	动态，随便变	链表
插入/删除	慢，要移动大量元素	极快，改个指针就行	链表 (完胜)
查找/访问	极快，直接下标访问	慢，得从头一个个找	数组 (完胜)
内存浪费	容易浪费或不够用	按需分配，不浪费	链表

可以看到，数组也是有优点的！所以说没有最好的数据结构！只有最合适的数据结构！✊✊✊

五、c/c++实现链表#

既然一个节点（node）有两个域，一个存指针，一个存数据。那么对于c来说我们就可以定义一个结构体！（ps:结构体是一个可以存储不同数据类型的容器，可以自行百度✊）

1
#include <iostream>
2
using namespace std;
3

4
// 1. 定义节点结构体（C++ 里 struct 和 class 很像，这里用 struct 方便点）
5
struct Node {
6
    int data;           // 【数据域】
7
    Node* link;         // 【指针域】
8
    //上面的Node就是定义的结构体，*代表指针，Node*合起来就是指向Node的指针
9
};
10
int main(){
11
Node* A;//声明一个指向节点的指针A
12
A=nullptr;
13
Node* temp=new Node()//创建一个内存块用于存放,如果是c语言就是用malloc（）

此时差不多就是这样

asda

让我们接着创建链表吧！（接着上面的代码）

我们需要将一个数据放到右边我们开辟的内存里，比如2，假设右边那块的内存地址是200

1
(*temp).data=2;//这里用的解引，还可以写成 temp->data=2;
2
(*temp).link=nullptr;//这里用的解引，还可以写成 temp->link=NULL;
3
A=temp;

tgggg

当A接管temp的工作之后，temp就可以暂时退休了！

如果你想继续创建节点则可以按以下进行，分别是创建节点然后遍历链表，最后成功连接

1
temp=new Node();//假设创建出来的地址是100,要存放的数据是4
2
temp->data=4;
3
temp->link=nullptr;
4
//为了将新建的节点插到末尾，我们不得不遍历链表
5
Node* temp1=A;//这里不能直接用A操作，否则你会丢失头节点！😭所以我们定义零食变量！
6
while(temp1->link !=nullptr){
7
    temp1=temp1->link;
8
}
9
temp1->link=temp;
10
cout<<endl;
11
return 0;
12
}//这个是main的括号呀！不要忘了，可恶！