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

【数据结构】链表介绍及代码实现

news 2026/7/18 11:09:11

目录

一、链表介绍

二、单链表的实现

1.导入头文件并定义链表的结点

2.链表打印

3.链表插入

（1）链表尾插

（2）链表头插

4.链表删除

（1）链表尾删

（2）链表头删

5.查找

6.指定位置之前插入数据

7.在指定位置之后插入数据

8.删除pos结点

9.删除pos之后的结点

10.链表销毁

三、完整代码

SList.h

SList.c

一、链表介绍

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

与顺序表不同的是，链表是由一个个节点/结点组成的，每个结点有两个组成部分：当前节点要保存的数据和保存下一个结点的地址（指针变量）

因为链表的每个结点都是独立申请的（即需要插入数据时才申请一块结点的空间），所以需要通过指针变量保存下一个结点的地址才能从当前结点找到下一个结点。

链表的结点也是使用结构体保存，假设当前链表保存的数据是整型数据

struct SListNode { int data; // 结点数据 struct SListNode* next; // 指针变量用于保存下一个结点的地址 };

当我们想保存一个数据时，实际上是向操作系统申请了一块内存（一般是堆内存，每次申请的空间可能连续也可能不连续），这个内存不仅要保存整型数据，也需要保存下一个结点的地址（下一个结点为空时保存的地址为NULL）。

二、单链表的实现

为了养成好习惯，我们可以用三个文件来实现链表：SList.h（定义链表的结点和声明链表的方法）、SList.c（定义链表的方法）、test.c（测试链表的方法）。

1.导入头文件并定义链表的结点

先在Slist.h中导入可能使用到的头文件

#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h>

定义链表的结点

// 定义结点的结构，并给结点中存储的数据类型和结构体起别名 // 存储的数据和下一个结点的指针 typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode;

2.链表打印

在打印链表前，需要先创建一个链表，所以先在test.c文件中创建几个结点，再调用链表打印的方法

void SListTest01() { // 链表是由一个一个结点组成，先创建几个结点 SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode)); node1->data = 1; SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode)); node2->data = 2; SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode)); node3->data = 3; SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode)); node4->data = 4; // 将四个结点连接起来 node1->next = node2; node2->next = node3; node3->next = node4; node4->next = NULL; // 调用链表的打印 SLTNode* plist = node1; SLTPrint(plist); }

链表打印的方法需要在SList.c中定义，并在SList.h中声明。

void SLTPrint(SLTNode* phead) { SLTNode* pcur = phead; // 定义一个pcur存储链表的结点 while (pcur) // 等价于pcur != NULL，用来判断pcur不为空 { printf("%d->", pcur->data); pcur = pcur->next; } printf("NULL\n"); }

使用pcur保存当前结点，判断结点是否为空，如果不为空就打印结点中保存的数据，并将pcur指向下一个结点，直到pcur为空，输出NULL，换行并结束。

3.链表插入

和顺序表一样，链表的插入也有头插尾插

（1）链表尾插

链表尾插有两种情况：非空链表和空链表

先判断链表是否为空，如果是空链表就直接将phead指向新结点；如果是非空链表就先找到尾结点，再将尾节点和新结点连接起来

注意：此处传入二级指针才是传址调用

**pphead <--> *phead 第一个结点

*pphead <--> plist 指向第一个结点的指针

pphead <--> &plist 指向第一个结点的指针的地址

形参 实参

实参传入&plist，代表指向第一个结点的指针的地址，对其解引用代表指向第一个结点的指针，再次解引用代表第一个结点

// 链表插入 void SLTPushBack(SLTNode** pphead, SLTDataType x) // 这里需要用二级指针传入头结点（传址） { assert(pphead); // 确保pphead不为空（无法对NULL进行解引用） // 申请新结点：因为头插和尾插都需要申请结点，所以可以将申请结点写成一个函数 SLTNode* newnode = SLTBuyNode(x); // 链表尾插存在空链表和非空链表两种情况 // 空链表 if (*pphead == NULL) // *pphead代表指向第一个结点的指针，为空表示空链表 { *pphead = newnode; // 直接将phead指向新结点 } else // 非空链表 { // 找尾结点 SLTNode* ptail = *pphead; // 定义一个ptail先指向头结点 while (ptail->next) // 当ptail->next为空时说明ptail是尾节点，所以循环条件是ptail->next != NULL，可以省略成ptail->next { ptail = ptail->next; } //跳出循环说明ptail指向的结点是尾节点，需要将新结点和尾节点连接起来 ptail->next = newnode; // ptail->next指向新结点 } }

此时需要在test.c文件中测试链表尾插代码是否正确

void SListTest02() { SLTNode* plist = NULL; SLTPushBack(&plist,1); SLTPushBack(&plist,2); SLTPushBack(&plist,3); SLTPushBack(&plist,4); SLTPrint(plist); } int main() { SListTest02(); return 0; }

调用几次链表尾插，再将链表打印出来，结果正确

（2）链表头插

头插无需判断是否为空链表，直接将新结点的next指针指向第一个结点，再将头指针指向新结点即可。

void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); // 确保pphead不为空 // 头插无需判断是否为空链表 SListNode* newnode = SLTBuyNode(x); // 申请一块新空间用来保存新结点 newnode->next = *pphead; // 将新结点的next指针指向当前的头结点 *pphead = newnode; // 将头指针指向新结点 }

在test.c中测试链表头插

void SListTest02() { SLTNode* plist = NULL; // 测试头插 SLTPushFront(&plist, 1); SLTPushFront(&plist, 2); SLTPushFront(&plist, 3); SLTPushFront(&plist, 4); SLTPrint(plist); } int main() { SListTest02(); return 0; }

依次在链表头部插入1、2、3、4，打印链表，结果正确

4.链表删除

（1）链表尾删

链表尾删有两种情况：链表中只有一个结点和链表中有多个结点。

当链表中只有一个结点时，直接将链表的一个结点释放并置为空；当链表中有多个结点时，找到尾结点和尾结点的前一个结点，并将尾节点释放并置为空，尾节点的前一个结点的next置为空。

// 链表删除 void SLTPopBack(SLTNode** pphead) { assert(pphead && *pphead); // 因为链表删除时链表中必须有元素，所以需要同时判断链表是否为空 // 链表尾删有两种情况：链表中只有一个结点和链表有多个结点 if ((*pphead)->next == NULL) // ->的优先级高于*，所以需要加括号。pphead的下一个结点为NULL时说明只有一个结点 { free(*pphead); // 直接将*pphead释放并置为空 *pphead = NULL; } else { SLTNode* prev = *pphead; // 尾结点的前一个结点 SLTNode* ptail = *pphead; // 尾结点 while (ptail->next) // 找尾结点 { prev = ptail; // prev指向尾节点当前位置 ptail = ptail->next; // 尾节点指向当前结点的后一个结点 } // 跳出循环代表ptail当前指向的结点是尾节点，释放尾结点并置为空 free(ptail); ptail = NULL; prev->next = NULL; // 再将prev->next指向NULL } }

在test.c中测试尾删

void SListTest02() { SLTNode* plist = NULL; SLTPushBack(&plist,1); SLTPushBack(&plist,2); SLTPushBack(&plist,3); SLTPushBack(&plist,4); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); } int main() { SListTest02(); return 0; }

先创建一个链表并插入数据，然后执行尾删代码并输出链表，结果正确

（2）链表头删

void SLTPopFront(SLTNode** pphead) { assert(pphead && *pphead); SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; }

测试头删

void SListTest02() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); } int main() { SListTest02(); return 0; }

运行程序，结果正确

5.查找

定义一个pcur指针存储当前结点的地址

当pcur不为空时，比较pcur与x的值，如果相等，就返回pcur;如果不想等，pcur就向后移动，直到pcur中存储的data与x相等或pcur为空（链表遍历结束）。如果pcur为空，说明当前链表没有要查找的值，返回NULL

// 查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* pcur = phead; while (pcur) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } return NULL; }

测试查找

void SListTest02() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPrint(plist); SLTNode* find = SLTFind(plist, 3); if (find == NULL) { printf("没有找到!"); } else { printf("找到了!"); } } int main() { SListTest02(); return 0; }

6.指定位置之前插入数据

如果pos和*pphead相等，说明是头插，直接调用头插的方法；如果pos和*pphead不相等，就找到pos的前一个指针，将newnode与pos连接起来，再将pos的前一个指针与newnode连接起来

// 在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead && *pphead); assert(pos); SLTNode* newnode = SLTBuyNode(x); // 若pos == *pphead，说明是头插 if (pos == *pphead) { SLTPushFront(pphead, x); } else { SLTNode* prev = *pphead; while (prev->next != pos) // 当prev->next不等于pos时，prev向后移动，相等时退出循环 { prev = prev->next; } newnode->next = pos; prev->next = newnode; } }

测试

void SListTest02() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPrint(plist); SLTNode* find = SLTFind(plist, 3); SLTInsert(&plist, find, 11); SLTPrint(plist); } int main() { SListTest02(); return 0; }

在3所在的结点前加一个11，编译运行，结果正确

7.在指定位置之后插入数据

首先判断指定位置不为空，然后创建一个新结点，将新结点与pos之后的结点连接起来，再将pos与新结点连接起来

// 在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = SLTBuyNode(x); newnode->next = pos->next; pos->next = newnode; }

测试

void SListTest02() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPrint(plist); SLTNode* find = SLTFind(plist, 3); SLTInsertAfter(find, 11); SLTPrint(plist); } int main() { SListTest02(); return 0; }

在3所在结点后添加一个结点存储11，结果正确

8.删除pos结点

删除pos结点有两种情况：pos结点是头结点或pos结点不是头结点。

当pos结点是头结点时，直接调用头删方法；当pos结点不是头结点时，找到pos的前一个结点，并将pos的前一个结点与pos后一个结点连接起来，再将pos结点释放并置为空即可。

// 删除pos结点 void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead && *pphead); assert(pos); // pos是头结点时，直接调用头删 if (pos == *pphead) { SLTPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } }

测试

void SListTest02() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPrint(plist); SLTNode* find = SLTFind(plist, 3); SLTErase(&plist,find); SLTPrint(plist); } int main() { SListTest02(); return 0; }

删除3所在的结点，结果正确

9.删除pos之后的结点

首先确保pos和pos的下一个结点不为空，然后定义一个新指针del保存pos下一个结点的地址，再将pos与pos的下下个结点连接起来，再将del释放并置为空

// 删除pos之后的结点 void SLTEraseAfter(SLTNode* pos) { assert(pos && pos->next); SLTNode* del = pos->next; pos->next = pos->next->next; free(del); del = NULL; }

测试

void SListTest02() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPrint(plist); SLTNode* find = SLTFind(plist, 3); SLTEraseAfter(find); SLTPrint(plist); } int main() { SListTest02(); return 0; }

将3所在结点的后一个结点删除，结果正确

10.链表销毁

销毁链表要一个一个结点销毁

在销毁第一个结点前，先将第一个结点的下一个结点存储到next中，使用pcur遍历链表，将pcur指向的结点销毁后，再将pcur指向next所指的结点，循环直到pcur指向空，说明链表已经全部销毁

// 销毁链表 void SListDestroy(SLTNode** pphead) { assert(pphead && *pphead); SLTNode* pcur = *pphead; while (pcur) { SLTNode* next = pcur->next; free(pcur); pcur = next; } *pphead = NULL; }

测试

void SListTest02() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPrint(plist); SLTNode* find = SLTFind(plist, 3); SListDestroy(&plist); SLTPrint(plist); } int main() { SListTest02(); return 0; }

将链表销毁，打印出来显示链表为NULL，成功销毁

三、完整代码

SList.h

#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> // 定义结点的结构，并给结点中存储的数据类型和结构体起别名 // 存储的数据和下一个结点的指针 typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; void SLTPrint(SLTNode* phead); // 链表打印 // 链表插入 void SLTPushBack(SLTNode** pphead, SLTDataType x); // 链表尾插 void SLTPushFront(SLTNode** pphead, SLTDataType x); // 链表头插 // 链表删除 void SLTPopBack(SLTNode** pphead); // 链表尾删 void SLTPopFront(SLTNode** pphead);// 链表头删 // 查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x); // 在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); // 在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x); // 删除pos结点 void SLTErase(SLTNode** pphead, SLTNode* pos); // 删除pos之后的结点 void SLTEraseAfter(SLTNode* pos); // 销毁链表 void SListDestroy(SLTNode** pphead);

SList.c

#include"SList.h" // 传入链表的头文件 void SLTPrint(SLTNode* phead) { SLTNode* pcur = phead; // 定义一个pcur存储链表的结点 while (pcur) // 等价于pcur != NULL，用来判断pcur不为空 { printf("%d->", pcur->data); pcur = pcur->next; } printf("NULL\n"); } SLTNode* SLTBuyNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); //申请结点有两种结果：申请成功和申请失败 if (newnode == NULL) // malloc申请失败 { perror("malloc fail！"); // 打印错误信息 exit(1); // 退出程序 } // 程序执行到这里说明申请成功 newnode->data = x; newnode->next = NULL; return newnode; } // 链表插入 void SLTPushBack(SLTNode** pphead, SLTDataType x) // 这里需要用二级指针传入头结点（传址） { assert(pphead); // 确保pphead不为空（无法对NULL进行解引用） // 申请新结点：因为头插和尾插都需要申请结点，所以可以将申请结点写成一个函数 SLTNode* newnode = SLTBuyNode(x); // 链表尾插存在空链表和非空链表两种情况 // 空链表 if (*pphead == NULL) // *pphead代表指向第一个结点的指针，为空表示空链表 { *pphead = newnode; // 直接将phead指向新结点 } else // 非空链表 { // 找尾结点 SLTNode* ptail = *pphead; // 定义一个ptail先指向头结点 while (ptail->next) // 当ptail->next为空时说明ptail是尾节点，所以循环条件是ptail->next != NULL，可以省略成ptail->next { ptail = ptail->next; } //跳出循环说明ptail指向的结点是尾节点，需要将新结点和尾节点连接起来 ptail->next = newnode; // ptail->next指向新结点 } } void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); // 确保pphead不为空 // 头插无需判断是否为空链表 SListNode* newnode = SLTBuyNode(x); // 申请一块新空间用来保存新结点 newnode->next = *pphead; // 将新结点的next指针指向当前的头结点 *pphead = newnode; // 将头指针指向新结点 } // 链表删除 void SLTPopBack(SLTNode** pphead) { assert(pphead && *pphead); // 因为链表删除时链表中必须有元素，所以需要同时判断链表是否为空 // 链表尾删有两种情况：链表中只有一个结点和链表有多个结点 if ((*pphead)->next == NULL) // ->的优先级高于*，所以需要加括号。pphead的下一个结点为NULL时说明只有一个结点 { free(*pphead); // 直接将*pphead释放并置为空 *pphead = NULL; } else { SLTNode* prev = *pphead; // 尾结点的前一个结点 SLTNode* ptail = *pphead; // 尾结点 while (ptail->next) // 找尾结点 { prev = ptail; // prev指向尾节点当前位置 ptail = ptail->next; // 尾节点指向当前结点的后一个结点 } // 跳出循环代表ptail当前指向的结点是尾节点，释放尾结点并置为空 free(ptail); ptail = NULL; prev->next = NULL; // 再将prev->next指向NULL } } void SLTPopFront(SLTNode** pphead) { assert(pphead && *pphead); SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; } // 查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* pcur = phead; while (pcur) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } return NULL; } // 在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead && *pphead); assert(pos); SLTNode* newnode = SLTBuyNode(x); // 若pos == *pphead，说明是头插 if (pos == *pphead) { SLTPushFront(pphead, x); } else { SLTNode* prev = *pphead; while (prev->next != pos) // 当prev->next不等于pos时，prev向后移动，相等时退出循环 { prev = prev->next; } newnode->next = pos; prev->next = newnode; } } // 在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = SLTBuyNode(x); newnode->next = pos->next; pos->next = newnode; } // 删除pos结点 void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead && *pphead); assert(pos); // pos是头结点时，直接调用头删 if (pos == *pphead) { SLTPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } } // 删除pos之后的结点 void SLTEraseAfter(SLTNode* pos) { assert(pos && pos->next); SLTNode* del = pos->next; pos->next = pos->next->next; free(del); del = NULL; } // 销毁链表 void SListDestroy(SLTNode** pphead) { assert(pphead && *pphead); SLTNode* pcur = *pphead; while (pcur) { SLTNode* next = pcur->next; free(pcur); pcur = next; } *pphead = NULL; }

完

http://www.cnnetsun.cn/news/3484474.html

相关文章：

  • LizzieYzy：三步轻松上手，免费AI围棋分析终极指南
  • LUKE与BERT对比：知识嵌入如何提升NLP任务性能？
  • 从源码到实践：深入理解EasyDialog的实现原理
  • openEuler测试工具项目架构解析：理解测试工具的核心设计模式
  • 2024最新fast_obj完全指南：从单头文件到高性能3D模型加载
  • Moonlight Internet Hosting Tool：3步实现零配置远程游戏串流的终极指南
  • 终极音乐下载神器music-dl：5分钟快速上手，免费下载全网音乐
  • 如何5分钟快速恢复QQ空间历史数据：GetQzonehistory终极指南
  • 嵌入式显示系统TV检测与DAC测试模式原理与实践
  • 从技术封锁到存储自由：Synology硬盘兼容性解锁的三次技术革命
  • 终极PWA安装解决方案pwa-install：一站式解决跨浏览器安装难题 [特殊字符]
  • LFM2.5-Embedding-350M-4bit商业应用指南：LFM Open License v1.0条款解读
  • 终极指南：5分钟掌握iFakeLocation iOS虚拟定位工具
  • Windows 搭建 OpenClaw 2.7.9 实操教程，可视化 AI 办公智能体部署流程
  • Verk动态队列管理：如何实时添加和移除作业队列
  • CC32xx I2C总线驱动开发：从协议原理到寄存器配置与实战避坑
  • 终极ntfy部署指南：3分钟搭建你的私有通知服务器
  • 3个核心技巧：深度掌握MTKClient逆向工程实战
  • Tachometer 与 CI/CD 集成：自动化性能测试的 7 个步骤
  • Dante Cloud用户体验测试：界面交互的可用性验证指南
  • 3个步骤让Zotero完美支持中文文献管理：茉莉花插件深度指南
  • AWS Service Operator 入门指南：如何用 kubectl 管理 AWS 资源
  • TI雷达芯片EDMA与ADC缓冲器协同配置实战指南
  • TI 14xx/16xx芯片TPTC MPU配置实战：从原理到代码的内存保护指南
  • MyBot常见问题解答：解决90%用户遇到的启动与运行难题
  • Winget-Install：Windows包管理器的自动化部署解决方案
  • DeepSeek LeetCode 3605. 数组的最小稳定性因子 Python3实现
  • maven_crate实战教程：5分钟搭建企业级Maven镜像仓库
  • LIEF：跨平台二进制格式解析与操作库深度解析
  • OpenClaw工业级落地六大硬核技巧：时间同步、多光谱融合与动力学前馈