当前位置：首页 > news >正文

c语言专题之单链表的实现

news 来源：原创 2025/7/5 22:24:24

在之前的博客中小编已经讲解了顺序表及其应用，所以在将讲单链表之前，我们先来重新思考一下顺序表，这里我先来讲顺序表的几个小缺点：

1.顺序表中在我们数据时，如头插、在指定位置插入等，我们通常需要整体挪动数据，这样一般会使代码更加复杂。

2.顺序表中当我们的空间不够时，我们会进行增容，而增容我们一般会选择成倍数的增加，这样有时就会导致我们空间的浪费！

3.我们通过realloc增容，需要申请新空间，有时还需要拷贝数据，释放旧空间。这样就会导致有性能的消耗！

那么以上问题该怎么解决呢？这就要提到我们接下来要讲的单链表了！

一、链表的概念及结构

1.概念：相较于顺序表在物理上和逻辑上都是连续的，链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

2.结构：链表的结构跟火车车厢相似，淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉或加上，不会影响其他车厢，每节车厢都是独⽴存在的。如下图：

⻋厢是独⽴存在的，且每节⻋厢都有⻋⻔。想象⼀下这样的场景，假设每节⻋厢的⻋⻔都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带⼀把钥匙的情况下如何从⻋头⾛到⻋尾？最简单的做法：每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙。这里的钥匙就是指针！在链表中就是这样的：

与顺序表不同的是，单链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/节点”

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

图中指针变量plist保存的是第⼀个节点的地址，我们称plist此时“指向”第⼀个节点，如果我们希望plist“指向”第⼆个节点时，只需要修改plist保存的内容为0x0012FFA0。

为什么还需要指针变量来保存下⼀个节点的位置呢？

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

结合前⾯学到的结构体知识，我们可以给出每个节点对应的结构体代码：假设当前保存的节点为整型：

这个结构体我们需要在一个.h文件中实现，而我们后续要写的函数则保存在一个.c文件中，然后另需一个test.c文件用来测试我们的代码。

接下来小编就来讲单链表的实现了！

二、单链表的实现

1.插入数据

在插入数据之前，我们需要先创建一个plist指针并使其为空，然后这个指针在后续就用来指向单链表的第一个节点了！

然后我们就可以开始写插入数据的函数了！如上，我定义了一个尾插函数SLPushBack，，并将plist指针的地址作为参数上传，注意：这里传指针的地址的原因是因为我们后续要修改plist指针，使其成为链表中第一个元素的地址！而后面的”1“则只是代表我们要插入的数据了。接下来我来讲解尾插，请看以下代码：

以上有两个函数，第一个函数SLTbyeNode用来申请节点，第二个函数SLPushBack及是尾插函数，尾插函数里面就会用到第一个用来申请节点的函数！下面我来分别介绍两个函数：

SLTbyeNode申请节点：由于在链表中我们是一个一个的插入数据并不用扩容，所以我们这里用的是malloc函数来申请空间！申请完之后我们需要判断是否申请成功，若成功就可以继续给结构体中的data和next数据赋值了！这样我们就创建好了一个节点并给他赋值好了数据！

SLPushBack尾插：在尾插函数中我们先创建了一个newnode指针来接收我们之前创建好的节点的地址，然后我们的下一步就是将这个节点连接到链表的最后一个节点的后面去，当然若链表为空，则直接使*pphead=newnode，若此时我们的链表中已经有数据了，则我们需要通过循环来找到链表中的最后一个节点并将我们刚创建好的节点连接上去就可以了！及ptail->next=newnode；

尾插讲完了，接下来就是头插了。看下图：

其实当我们理解了尾插之后，理解其他插入方法就会变得很简单了，这里尾插与头插不一样的就是我们新创建的节点中的next指针要指向我们原来链表的第一个节点，及newnode->next=*pphead;同时我们也需要使*pphead指向newnode，因为我们需要*pphead（plist指针）一直指向链表的第一个节点！

第三个我们就来讲在指定位置之后插入数据了，看以下代码：

我们创建了SLInsertAfter函数，这里需要提的是它的参数pos，pos指向的是链表中某一个节点的地址，我们就是要在这个节点后插入数据，若是我们需要在某一个节点后插入数据，那么我们就需要先遍历链表找到那个节点的地址，然后将其作为参数传给函数就行了。由于比较简单，小编就不讲怎么寻找了；

插入讲完了之后我们就要讲删除了！

二、删除节点

1.尾删

如图：

尾删需要注意的是pphead和*pphead都不能为空，否则就没有数据给他删除，这里，当链表只有一个节点时，我们直接删除第一个节点就行了。当不止一个节点时，我们需要先创建两个指针prev和ptail，通过遍历链表来时ptail指向最后一个节点，prev则指向其前一个节点，然后我们再进行删除就行了，注意：这里prev的作用就是在删除后将最后一个节点的next指针指向为空！

2.头删

看下图：

头删就较为简单了，直接删除就行了，需要注意的是要将*pphead指向删除后的第一个节点的位置！

3.删除指定位置

看图：

删除指定节点也需要我们提前找到我们要删除的那个节点的地址，这里需要注意的是我们还需要定义一个指针prev使其指向pos位置的前一个位置，否则我们将无法链接pos位置的前后节点！

到这里，我们的单链表就讲完了！希望大家看完后能有所收获，若有不懂的可以提问哦，欢迎大家共同学习交流！

点个关注，防止迷路！后续小编还会更新更多关于C语言以及C++的知识，希望大家共同学习交流！