数据结构——链表

code_monnkey_

发布于 2025-05-31 08:10:50

1380

前言

在计算机科学中，数据结构（data structure）是一种数据组织、管理和存储的格式。它是相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术相关。数据结构研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系。它包含三个方面的内容：即数据的逻辑结构、数据的存储结构和数据的操作，只有这三个方面的内容完全相同，才能成为完全相同的数据结构。

数据结构是计算机四大件之一，是与计算机组成原理、操作系统、计算机网络齐名的存在，因此数据结构的重要性不言而喻。

本章将带领大家去了解链表这一重要的数据结构。

基本概念

链表是⼀种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表也是线性表的一种，与顺序表一样，它们在逻辑结构上都是连续的，但与顺序表不同的是，链表在物理结构（即存储时）上是不一定连续的。这是为什么呢？我们可以从链表的结构上来找出原因：链表是由一个类似于火车的结构，每个车厢之间仅有一个“铁链”连接起来，增加车厢或者去掉车厢并不会影响其他的车厢，只是连接的顺序会发生改变，链表里的每节"车厢"都是独立申请下来的空间，我们称之为“结点”。

结点的组成主要有两个部分：当前结点要保存的数据和保存下一个结点的地址（指针变量）

如下图所示：

链表中每个结点都是独立申请的（即需要插入数据时才去申请⼀块结点的空间），我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。

因此链表最大的优点在于我们可以按需开辟空间，不会造成空间的浪费。即我们需要储存几个数据时，我们就开辟多少个链表结点。

1.单链表

1.1结构

在C语言中，我们同样用一个结构体来定义链表。链表也有许多不同的结构，我们先从最简单的单链表讲起，下面让我们来看一下如何具体的定义一个单链表：

上图是一个用结构体定义的单链表，我们一句一句进行剖析。

" typedef int SLTDateType " 该句是将int重新用一个单词来进行替换，这样做的好处在于当我们储存不同类型的结构时只需将上述中的int修改为相应的数据类型即可，而不需要修改整个文件中的每一个int；

在我们定义的SListNode这个结构体中，第一个成员变量"data"即是我们需要存储的元素；第二个变量"next"为我们存储下一个元素的结点的地址，因此它的变量类型为该结构体的指针。这样，当我们有了第一个结点的地址后，我们便可以通过"next"来找到后续存储的地址。

从此可以看出，当我们使用单链表来查找数据时必须从头开始遍历，而无法进行与顺序表一样的直接从下标来访问对应元素

单链表的缺陷：不支持随机访问。

1.2实现

想要实现一个单链表，我们需要有以下的函数接口：

通过上图大家可以看到我们在实现单链表时在一些函数接口上进行传参时大部分涉及到了二级指针，在下面函数接口的具体讲解中我将为大家阐明原因。

1.2.1动态申请结点

因为链表的空间是我们按需开辟，所以当我们在链表中增加元素时需要手动开辟空间，因此我们可以写一个专门用来开辟结点的函数，具体代码实现如下：

该函数也即为简单易懂，开辟一块空间，将需要存储的元素存入结点中，并使结点中指向下一块空间的地址置为NULL，最后返回我们开辟空间的地址即可。

1.2.2单链表尾插

在进行单链表的尾插时，我们可以看到函数中的第一个参数的类型为二级指针，这是因为当我们插入的数据为链表中的第一个数据时，我们的头节点的地址要发生改变，使其指向的是第一个结点的地址（即我们申请结点返回的地址），所以当我们想要在函数中修改一个地址时我们应该传入的是存储该地址指针的地址，即二级指针。具体的代码实现如下：

在图上我们可以看出，当我们传入的为一个空链表（即头节点为空）时，我们需要将头节点的地址变为第一个结点的地址。当链表不为空时，我们则需要通过遍历链表来找到链表存储元素的最后一个结点，将申请结点的地址赋给最后结点中的"next",使其指向申请的结点，让该结点成为链表的最后一个结点。

1.2.3单链表头插

我们通过对尾插分析后得知当我们需要对头节点进行改变时需要传入二级指针。因此当进行头插时我们每一次都要对头结点进行改变，因此也需要传入二级指针。具体的代码实现如下：

头插相对与尾插来说更为简便，这是因为我们不需要通过遍历先去找到最后一个结点，而是直接改变头节点，并使申请结点的"next"指向之前的头节点即可。

1.2.4单链表尾删

我们在进行尾插时只需要找到最后一个结点的位置即可，但是当我们进行尾删时光是找到最后一个结点位置是不够的，因为我们进行尾删操作时除了要将最后一个结点删除，还需要将其上一个结点存储的地址置为NULL，否则就会有"野指针"的出现，造成"内存泄漏"。因此，我们在进行尾删操作时要在找最后一个结点的同时去找到上一个的结点位置，我们通过一个临时变量"prev"便可以轻松做到。具体的代码实现如下：

与尾插一样，当链表为只剩下一个元素时，我们需要改变头节点的地址，因此我们需要传入二级指针。当链表元素大于一个时，我们需要有一个临时变量"prev"来存储上一个结点的指针，这样当我们找到最后一个结点时，prev中存储的即为倒数第二个结点的地址，此时我们将最后一个结点释放掉，把倒数第二个结点（即prev）中存储下一个结点的地址置空即可。

1.2.5单链表头删

头删操作相对来说比较简单，只需将头结点指向下一个结点即可。具体的代码实现如下：

因为要改变头结点，因此此处传的也是二级指针。

1.2.6单链表查找

进行查找操作时不涉及头结点的改变，因此此处我们不需要传入二级指针，只需要传入一级指针即可。具体的代码实现如下：

单链表的查找也就是从头遍历链表，若是找到了相应元素，返回该节点的地址，若遍历后没有找到，则返回一个空指针。

1.2.7单链表指定位置删除

一般来说我们在进行单链表指定位置删除操作时删除的是指定位置之后的结点，这是因为当我们删除指定位置的结点时还要知道其上一个结点和后一个结点，操作较为复杂，并且会涉及到二级指针。我们先来看删除指定位置的代码实现：

但是如果是删除指定位置之后的元素则简单许多，具体的代码实现如下：

两种方法各有优劣，大家选择合适的即可。

1.2.8单链表指定位置插入

与指定位置删除类似，单链表在指定位置插入也有两种方式，一种是在指定位置之前插入，一种是在指定位置之后插入。它们之间主要的区别也是涉及到了传参的类型，若是在指定位置之前插入，则有可能涉及到头结点的改变，因此需要传入二级指针。具体的代码实现如下：

而在指定位置之后插入则不会涉及到头结点的改变，因此不需要传入二级指针，具体的代码实现如下：

两种方法的选择都是可以的，适合自己即可。

1.2.9单链表摧毁

我们的链表中的每一个结点都是是用malloc开辟的空间，因此当我们退出程序时需要释放我们动态开辟的空间，防止造成内存泄漏，具体的代码实现如下：

由于结点之间只有一个地址相连，因此在释放空间时我们需要先记录下一个结点后再释放当前结点，否则将无法找到后面的结点。

2.分类

2.1带头/不带头

在上述的单链表中我们在涉及添加和删除操作中不可避免的会涉及到二级指针，那么有没有方法可以让我们不用二级指针也可以正常操作呢？基于此，在链表中有了一个分类：是否带头，这里的头我们称之为"哨兵位"，即创建一个结点，该节点不存储任何元素，只存储下一个结点的地址。这样当我们再进行添加或者删除操作时便不会涉及到头结点的改变，不需要再传入二级指针了。

2.2单向/双向

既然链表中可以存储下一个结点的地址，那么我们可不可以让链表中也存储上一个结点的地址呢？答案当然是可以的，因此链表又分为单向链表和双向链表。在双向链表中，我们有两个指针变量，一个用来存储下一个结点的地址，一个用来存储上一个结点的地址，如下图所示：

2.3循环/非循环

循环链表即指的是链表中的最后一个结点指向的地址不为空，而是指向第一个结点的地址，这样便得到了一个循环链表。

2.4如何选择

上述的三种不同的分类之间彼此组合，我们可以得到八种不同的链表，其中最为简单的就是我们上述所说的单链表，也就是单向非循环不带头链表，最为复杂的是双向循环带头链表（下面简称为双向链表），同时，这两种链表也是我们最常用的两种链表。

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。 2. 带头双向循环链表：结构最复杂，⼀般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。