跳到主要内容单链表数据结构详解与 C 语言实现 | 极客日志C算法
单链表数据结构详解与 C 语言实现
单链表作为物理存储非连续、逻辑有序的线性表结构，解决了顺序表在中间或尾部插入删除数据时效率低及空间浪费问题。教程详细解析单链表节点定义，演示 C 语言环境下头部插入、尾部插入、头部删除、尾部删除、查找、指定位置前后插入删除及销毁链表的完整实现过程，包含核心代码逻辑与测试用例。
前言
前面我们学习了顺序表，但是顺序表有三个缺点：
- 中间 / 尾部插入 / 删除数据，时间复杂度都为
O(N)
- 增容，需要申请新空间，拷贝，释放旧空间，会有不小的消耗。
- 不可避免浪费。
那么，有没有其他的数据结构，能够实现中、尾部插、删数据的运行时间更短、只需一次释放、不会浪费空间这三点呢？
这时，我们引入单链表。
1、链表的概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表的性质：
- 链式结构，在逻辑结构上是有序的，在物理结构上，不一定有序。
- 链表是由一个一个节点组成的，节点一般是在堆上申请的 (
malloc())。
- 从堆上申请的节点空间，可能连续，可能不连续。
2、链表的节点
链表的节点，包含两个部分：
- 存放的数据元素。
- 指针变量，指向下一个节点的位置。
我们可以用画图的方法，来理解链表与节点的关系：
其中，所有节点构成一个有限的链表。
3、单链表的实现
我们还是创建三个文件：SList.h SList.c test.c，分别实现：定义与声明、功能的实现、测试。
3.1、链表节点的定义
既然节点包括两种元素，那么我们很容易想到结构体：
typedef int SLTDataType;
typedef struct SListNode {
SLTDataType data;
struct SListNode* next;
} SLNode;
3.2、链表的打印
思路：
- 首先找到链表的首节点。
- 利用循环打印每个节点的数据，再利用指针变量找到下一个节点。
- 当找到尾节点（该节点成员中指针变量为
NULL），循环停止。
void SLTPrint(SLNode* phead) {
SLNode* pcur = phead;
while(pcur) {
printf("%d -> ", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
3.3、创建新节点
由于接下来插入新数据这一操作，将会频繁进行，所以我们封装一个创建新节点的函数：
SLNode* SLTBuyNode(SLTDataType key) {
SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
if(newNode == NULL) {
perror("newNode malloc");
exit(1);
}
newNode->next = NULL;
newNode->data = key;
return newNode;
}
3.4、尾部插入新数据
- 创建新节点
- 如果链表为空，直接赋值。
- 如果链表非空，从头节点开始，找到尾节点，加上新节点
void SLTPushBack(SLNode** pphead, SLTDataType key) {
SLNode* newNode = SLTBuyNode(key);
if(*pphead == NULL) {
*pphead = newNode;
}
else {
SLNode* ptail = *pphead;
while(ptail->next != NULL) {
ptail = ptail->next;
}
ptail->next = newNode;
}
}
3.5、头部插入新数据
- 判断 pphead 有效性
- 申请一个新链表
- 建立联系
- 更新头节点
void SLTPushFront(SLNode** pphead, SLTDataType key) {
assert(pphead);
SLNode* newNode = SLTBuyNode(key);
newNode->next = *pphead;
*pphead = newNode;
}
3.6、尾部删除数据
- 判断
pphead和*pphead的有效性
- 对于链表节点的个数，进行讨论：
- 如果有两个及以上节点，遍历找尾节点。可以再定义一个节点，找到当前链表的，尾节点，的上一个节点
- 如果只有一个节点，直接释放。否则，按照上一种情况的思路，会遇到对空指针解引用的情况。
void SLTPopBack(SLNode** pphead) {
assert(pphead && *pphead);
if((*pphead)->next == NULL) {
free(*pphead);
*pphead = NULL;
}
else {
SLNode* perv = NULL;
SLNode* ptail = *pphead;
while(ptail->next) {
perv = ptail;
ptail = ptail->next;
}
perv->next = NULL;
free(ptail);
ptail = NULL;
}
}
3.7、头部删除数据
- 判断 pphead，和*pphead 的有效性
- 先存下，下一个节点，的地址
- 后释放
- 更新头节点
void SLTPopFront(SLNode** pphead) {
assert(pphead && *pphead);
SLNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
3.8、查找函数
既然是查找当前链表的某一个节点，哪么首先，查找函数的返回值，就是该节点的地址。
- 定义变量，遍历函数
- 找到就停下，返回地址；找不到，返回
NULL
- 由于查找节点不改变原链表，传递头节点只需一级指针
SLNode* SLTFind(SLNode* phead, SLTDataType key) {
assert(phead);
SLNode* pcur = phead;
while(pcur) {
if(pcur->data == key) {
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
3.9、指定位置，之前插入
当需要在头节点之前插入，相当于头插操作，需使用调用头插函数。否则，会出现对空指针进行解引用（用于遍历链表的指针不能跳出循环，直到变成 NULL）的情况。
- 创建新节点
- 遍历找到当前节点，的前一个节点
- 节点与节点之间，建立联系
void SLTInsertBefore(SLNode** pphead, SLNode* pos, SLTDataType key) {
assert(pphead && pos);
if(pos == *pphead) {
SLTPushFront(pphead, key);
} else {
SLNode* newnode = SLTBuyNode(key);
SLNode* pcur = *pphead;
while(pcur->next != pos) {
pcur = pcur->next;
}
newnode->next = pos;
pcur->next = newnode;
}
}
3.10、指定位置，之后插入
- 创建新节点
- 由于之后的节点，能通过当前节点直接定位，故不需要头节点和遍历操作。
- 首先，新节点与之后节点建立联系；然后，当前节点与新节点建立联系。否则，如果颠倒顺序，会出现之后节点找不到的情况。
void SLTInsertAfter(SLNode* pos, SLTDataType key) {
assert(pos);
SLNode* newnode = SLTBuyNode(key);
newnode->next = pos->next;
pos->next = newnode;
}
3.11、指定位置，删除节点
由于当前节点的前一个结点无法直接找到，故还需头节点与遍历。
- 如果删除的是头节点，直接调用头删函数（防止对空指针进行解引用的情况出现）
- 如果不是：
- 遍历找到当前节点，的前一个节点
- 先建立联系
- 后释放当前节点
void SLTErase(SLNode** pphead, SLNode* pos) {
assert(pphead && pos && *pphead);
if(pos == *pphead) {
SLTPopFront(pphead);
} else {
SLNode* pcur = *pphead;
while(pcur->next != pos) {
pcur = pcur->next;
}
pcur->next = pos->next;
free(pos);
pos = NULL;
}
}
3.12、指定位置，之后删除
不难想到，这里我们无需从头节点开始遍历，就可以找到我们需要的节点。
- 首先，判断指针有效性，以及当前指针，之后是否还有指针
- 如果还有指针：
void SLTEraseAfter(SLNode* pos) {
assert(pos && pos->next);
SLNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
这时候，你可能会问了：怎么没有删除之前的节点了呢？
如果是这样一种情况，那又何必另外写一个函数？直接调用删除当前节点函数，就可以了。
3.13、销毁链表
- 遍历链表
- 保存当前节点，的下一个节点，的地址
- 释放当前节点
void SLTDestroy(SLNode** pphead) {
assert(pphead);
SLNode* pcur = *pphead;
while(pcur) {
SLNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
4、结尾
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode {
SLTDataType data;
struct SListNode* next;
} SLNode;
void SLTPrint(SLNode* phead);
void SLTPushBack(SLNode** pphead, SLTDataType key);
void SLTPushFront(SLNode** pphead, SLTDataType key);
void SLTPopBack(SLNode** pphead);
void SLTPopFront(SLNode** pphead);
SLNode* SLTFind(SLNode* phead, SLTDataType key);
void SLTInsertBefore(SLNode** pphead, SLNode* pos, SLTDataType key);
void SLTInsertAfter(SLNode* pos, SLTDataType key);
void SLTErase(SLNode** pphead, SLNode* pos);
void SLTEraseAfter(SLNode* pos);
#include "SList.h"
SLNode* SLTBuyNode(SLTDataType key) {
SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
if(newNode == NULL) {
perror("newNode malloc");
exit(1);
}
newNode->next = NULL;
newNode->data = key;
return newNode;
}
void SLTPrint(SLNode* phead) {
SLNode* pcur = phead;
while(pcur) {
printf("%d -> ", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
void SLTPushBack(SLNode** pphead, SLTDataType key) {
SLNode* newNode = SLTBuyNode(key);
if(*pphead == NULL) {
*pphead = newNode;
}
else {
SLNode* ptail = *pphead;
while(ptail->next != NULL) {
ptail = ptail->next;
}
ptail->next = newNode;
}
}
void SLTPushFront(SLNode** pphead, SLTDataType key) {
assert(pphead);
SLNode* newNode = SLTBuyNode(key);
newNode->next = *pphead;
*pphead = newNode;
}
void SLTPopBack(SLNode** pphead) {
assert(pphead && *pphead);
if((*pphead)->next == NULL) {
free(*pphead);
*pphead = NULL;
}
else {
SLNode* perv = NULL;
SLNode* ptail = *pphead;
while(ptail->next) {
perv = ptail;
ptail = ptail->next;
}
perv->next = NULL;
free(ptail);
ptail = NULL;
}
}
void SLTPopFront(SLNode** pphead) {
assert(pphead && *pphead);
SLNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
SLNode* SLTFind(SLNode* phead, SLTDataType key) {
assert(phead);
SLNode* pcur = phead;
while(pcur) {
if(pcur->data == key) {
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
void SLTInsertBefore(SLNode** pphead, SLNode* pos, SLTDataType key) {
assert(pphead && pos);
SLNode* newnode = SLTBuyNode(key);
if(pos == *pphead) {
SLTPushFront(pphead, key);
} else {
SLNode* perv = *pphead;
while(perv->next != pos) {
perv = perv->next;
}
perv->next = newnode;
newnode->next = pos;
}
}
void SLTInsertAfter(SLNode* pos, SLTDataType key) {
assert(pos);
SLNode* newnode = SLTBuyNode(key);
if(pos->next == NULL) {
SLTPushBack(&pos, key);
}
else {
newnode->next = pos->next;
pos->next = newnode;
}
}
void SLTErase(SLNode** pphead, SLNode* pos) {
assert(pphead && pos);
assert(*pphead);
if(pos == *pphead) {
SLTPopFront(pphead);
}
else {
SLNode* perv = *pphead;
while(perv->next != pos) {
perv = perv->next;
}
perv->next = pos->next;
free(pos);
pos = NULL;
}
}
void SLTEraseAfter(SLNode* pos) {
assert(pos && pos->next);
SLNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
void SLTDestroy(SLNode** pphead) {
assert(pphead);
SLNode* pcur = *pphead;
while(pcur) {
SLNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
#include "SList.h"
void test1() {
SLNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
SLNode* pos = SLTFind(plist, 4);
SLTDestroy(&plist);
}
void test0() {
SLNode* node1 = (SLNode*)malloc(sizeof(SLNode));
if(node1 == NULL) {
perror("malloc");
exit(1);
}
SLNode* node2 = (SLNode*)malloc(sizeof(SLNode));
if(node2 == NULL) {
perror("malloc");
exit(1);
}
SLNode* node3 = (SLNode*)malloc(sizeof(SLNode));
if(node3 == NULL) {
perror("malloc");
exit(1);
}
SLNode* node4 = (SLNode*)malloc(sizeof(SLNode));
if(node4 == NULL) {
perror("malloc");
exit(1);
}
node1->data = 1;
node2->data = 2;
node3->data = 3;
node4->data = 4;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;
SLTPrint(node1);
}
int main() {
test1();
return 0;
}
