数据结构 单链表(2)--单链表的实现

1.单链表的实现

实现单链表和实现顺序表步骤一样，小编也是用三个文件编写完成的。分别是一个头文件（.h) , 

一个实现文件(.c)和一个测试文件(.c)。

 下面对这三个文件的代码按照功能模块，函数逻辑等进行详细解释，进一步帮助理解单链表的实

现。

1.1 头文件 (SList.h)

头文件（ 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;//typedef struct SListNode 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);

- 定义单链表的核心结构：通过 typedef 定义数据类型 SLTDataType （此处为 int ）和结点结构

体 SLTNode （包含所要存储的数据data 和指向下一个结点的指针 next ）。

- 声明单链表的所有操作函数：包括打印、增删（头插/尾插/指定位置插）、查改、销毁等接口，

明确函数参数和返回值类型，为 .c 文件的实现和测试文件的调用提供统一接口。这些函数在.c文件

中将会一一介绍。

1.2  实现文件（ SList.c ）

单链表的实现文件（ SList.c ）—— 接口函数具体实现:

 1. 链表打印函数  SLTPrint 

#include"SList.h"
//链表的打印
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

- 功能：遍历并打印链表中所有结点的数据，直观展示链表结构。

- 参数： phead  为链表的头指针（指向第一个结点，若链表为空则为  NULL ）。

- 逻辑：

定义临时指针  pcur  初始化为  phead ，用于遍历链表（避免修改头指针本身）。

循环条件  while (pcur) ：当 pcur 不为 NULL  时，继续遍历（即未到链表末尾）。

循环内：打印当前结点的数据  pcur->data ，格式为  "%d -> " ；然后将  pcur  移动到下一个

结点（ pcur = pcur->next ）。

遍历结束后，打印  "NULL"  表示链表的末尾。

- 示例：若链表为  1 -> 2 -> 3 ，则输出  1 -> 2 -> 3 -> NULL 。

- 时间复杂度： O(n) 

需遍历链表中所有 n 个结点，每个结点的操作（打印、移动指针）为 O(1) ，总耗时与结点

数成正比。

- 空间复杂度： O(1) 

仅使用常数个临时变量（ pcur ），不随输入规模变化。

2. 节点创建函数  SLTbuyNode （内部辅助函数）

SLTNode* SLTbuyNode(SLTDataType x)
{//根据x创建节点SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}

链表中每个结点都是独立申请的（即需要插入数据时才去申请一块结点的空间），我们需要

通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。

所以这个函数的

 - 功能就是 ：创建一个新结点，为后续插入操作提供基础结点（封装结点创建逻辑，避免重

复代码）。

- 参数： x  为新结点要存储的数据。

- 返回值：新创建结点的地址（ SLTNode*  类型）。

- 逻辑：

用 malloc 分配一块 SLTNode 大小的内存（ sizeof(SLTNode) ），返回值赋给  newnode 。

检查内存分配是否成功：若  newnode == NULL （ malloc  失败），用 perror 打印错误信息

（ "malloc fail!" ），并通过  exit(1)  终止程序（避免后续操作访问无效内存）。

初始化新结点： newnode->data = x （设置数据域）， newnode->next = NULL （默认不指

向任何节点）。

返回新结点地址  newnode 。

- 时间复杂度： O(1) 

操作仅涉及内存分配（ malloc 为常数级）和结点初始化，与数据量无关。

- 空间复杂度： O(1) 

仅申请一个结点的内存（属于必要的输出空间，不计入算法额外空间），临时变量为常数

个。

3. 尾插函数  SLTPushBack 

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTbuyNode(x);//链表为空if (*pphead == NULL){*pphead = newnode;}else {//找尾SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptail newnodeptail->next = newnode;}
}

- 功能：在链表的末尾插入一个新结点（存储数据  x ）。

- 参数：

-  pphead ：头指针的地址（SLTNode** 类型），用于修改头指针本身（当链表为空时，头

指针会指向新结点）。

-  x ：要插入的数据。

- 逻辑：

断言  assert(pphead) ：确保 pphead 不为  NULL （避免传入无效地址，导致后续解引用错

误）。

调用 SLTbuyNode(x)  创建新结点，得到 newnode。

分两种情况处理：

1. 链表为空（ *pphead == NULL ）：此时头指针直接指向新结点（ *pphead

= newnode ），新结点成为链表的第一个结点。

2. 链表非空：需先找到链表的尾结点（最后一个节点，其 next 为  NULL ）：

定义 ptail 初始化为  *pphead （从头节点开始）。

循环 while (ptail->next) ：当  ptail->next  不为 NULL 时，移动 ptail 到下一个节点（ ptail =

ptail->next ），直到 ptail->next == NULL ( ptail  即为尾结点）。

将尾结点的  next  指向新结点（ ptail->next = newnode ），新节点成为新的尾结点。

示例：原链表  1 -> 2 ，尾插 3 后变为  1 -> 2 -> 3

- 时间复杂度： O(n) 

最坏情况（链表非空）需遍历到尾结点，遍历次数为 n （ n 为结点数），插入操作本身

为 O(1) 。

(对比顺序表尾插：顺序表尾插在容量足够时为 O(1) ，但扩容时为 O(n) ；链表尾插无扩容问

题，但始终需遍历找尾）

- 空间复杂度： O(1) 

仅使用常数个临时变量（ newnode 、 ptail ）。

4. 头插函数  SLTPushFront 

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTbuyNode(x);//newnode *ppheadnewnode->next = *pphead;*pphead = newnode;
}

- 功能：在链表的头部插入一个新结点（存储数据  x ），新节点成为新的头结点。

- 参数：

-  pphead ：头指针的地址（用于修改头指针）。

-  x ：要插入的数据。

- 逻辑：

断言  assert(pphead) ：确保  pphead  有效。

调用  SLTbuyNode(x)  创建新节点 newnode 。

- 关键操作：

- 让新结点的 next 指向原头节点（ newnode->next = *pphead ），确保原链表不丢失。

- 让头指针指向新节点（ *pphead = newnode ），新结点成为新的头结点。

- 示例：原链表  1 -> 2 ，头插  0  后变为  0 -> 1 -> 2 。

- 注意：无论链表是否为空（ *pphead  为  NULL  或有效结点），逻辑均适用（空链表时

 newnode->next = NULL ，仍正确）。

- 时间复杂度： O(1) 

无需遍历，直接修改新结点和头指针的指向，操作次数为常数。

(对比顺序表头插：顺序表头插需移动所有元素，为 O(n) ；链表头插是链表的核心优势操

作）

- 空间复杂度： O(1) 

仅使用常数个临时变量（ newnode ）。

5. 尾删函数  SLTPopBack 

//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);//只有一个结点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else {SLTNode* prev = NULL;SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}//prev ptailprev->next = NULL;free(ptail);ptail = NULL;}
}

- 功能：删除链表的最后一个结点（尾结点）。

- 参数： pphead  为头指针的地址（需修改头指针当链表只剩一个结点时）。

- 逻辑：

断言  assert(pphead && *pphead) ：确保  pphead  有效，且链表非空（ *pphead !=

NULL ，避免删除空链表）。

- 分两种情况处理：

1.链表只有一个结点（ (*pphead)->next == NULL ）：

- 直接释放头结点  free(*pphead) 。

- 将头指针置为  NULL （ *pphead = NULL ），链表变为空。

2.链表有多个节点：

- 定义两个指针：prev（记录尾结点的前一个节点，初始为  NULL ）和  ptail （记录当前尾

节点，初始为  *pphead ）。

- 循环  while (ptail->next) ：移动 prev 和  ptail ，直到  ptail  指向尾结点（ ptail->next ==

NULL ），此时  prev  指向尾节点的前一个结点。

- 操作：将  prev->next  置为  NULL （断开与尾结点的连接），释放  ptail （ free(ptail) ），

并将  ptail  置为  NULL （避免野指针）。

- 示例：原链表  1 -> 2 -> 3 ，尾删后变为  1 -> 2 -> NULL 。

- 时间复杂度： O(n) 

最坏情况（多结点链表）需遍历到尾结点的前一个结点（ prev ），遍历次数为 n-1 ，删除操

作本身为 O(1) 。

（对比顺序表尾删：顺序表尾删为 O(1) ，无需遍历；链表尾删因无法直接获取前节点，效率

较低）

- 空间复杂度： O(1) 

仅使用常数个临时变量（ prev 、 ptail ）。

6. 头删函数  SLTPopFront 

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

- 功能：删除链表的第一个结点（头结点）。

- 参数： pphead  为头指针的地址。

- 逻辑：

断言  assert(pphead && *pphead) ：确保  pphead  有效且链表非空。

定义  next  指针：记录头结点的下一个结点（ (*pphead)->next ，即原第二个结点）。

释放头结点（ free(*pphead) ）。

将头指针更新为 next（ *pphead = next ），原第二个节点成为新的头结点（若原链表只有

一个结点， next  为  NULL ，链表变为空）。

- 示例：原链表  1 -> 2 -> 3 ，头删后变为  2 -> 3 -> NULL 。

- 时间复杂度： O(1) 

无需遍历，直接释放头结点并更新头指针，操作次数为常数。

（对比顺序表头删：顺序表头删需移动所有元素，为 O(n) ；链表头删是优势操作）

- 空间复杂度： O(1) 

仅使用常数个临时变量（ next ）。

7. 查找函数  SLTFind 

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

- 功能：在链表中查找第一个数据为  x  的结点，返回该结点的地址；若未找到，返回

 NULL 。

- 参数：

phead ：头指针（遍历的起点）。

x ：要查找的数据。

返回值：找到的节点地址（ SLTNode* ），或  NULL （未找到）。

- 逻辑：

- 定义 pcur 初始化为  phead ，用于遍历链表。

- 循环  while (pcur) ：遍历所有结点。

- 若  pcur->data == x ：找到目标节点，返回  pcur 。

- 否则： pcur = pcur->next ，继续遍历下一个节点。

- 循环结束（ pcur == NULL ）：未找到目标，返回  NULL 。

- 示例：链表  1 -> 2 -> 3  中查找  2 ，返回指向  2  的节点地址；查找  4 ，返回  NULL 。

- 时间复杂度： O(n) 

最坏情况（查找最后一个结点或未找到）需遍历所有 n 个结点，比较次数为 n 。

（与顺序表查找相同：均需线性遍历，无随机访问优势）

- 空间复杂度： O(1) 

仅使用常数个临时变量（ pcur ）。

8. 指定位置前插入函数  SLTInsert 

//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && pos);//当pos指向第一个结点，是头插if (pos == *pphead){SLTPushFront(pphead, x);}else {SLTNode* newnode = SLTbuyNode(x);//找pos的前一个结点SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev--> newnode--> posprev->next = newnode;newnode->next = pos;}
}

- 功能：在指定结点 pos 的前面插入一个新结点（存储数据  x ）。

- 参数：

pphead ：头指针的地址（可能需要修改头指针，如 pos 是头结点时）

pos ：指定结点的地址（必须是链表中已存在的结点）。

x ：要插入的数据。

- 逻辑：

断言  assert(pphead && pos) ：确保 pphead 有效，且  pos  不为  NULL （避免插入位置

无效）。

- 分两种情况处理：

1.pos  是头结点（ pos == *pphead ）：此时插入操作等价于头插，直接调用

 SLTPushFront(pphead, x) （复用头插逻辑）。

2.pos  不是头节点：

- 调用  SLTbuyNode(x)  创建新结点  newnode 。

- 查找 pos 的前一个结点  prev ：定义 prev 初始化为  *pphead ，循环  while (prev->next

!= pos)  移动  prev ，直到  prev->next == pos （ prev  指向  pos  的前一个结点）。

- 插入操作： prev->next = newnode （ prev  指向新结点）， newnode->next = pos （新节

点指向  pos ），完成插入。

- 示例：链表  1 -> 3 -> 4  中，在  pos （指向  3 ）前插入  2 ，结果为  1 -> 2 -> 3 -> 4 。

- 时间复杂度： O(n) 

最坏情况（ pos 为尾结点）需遍历找到 pos 的前一个结点（ prev ），遍历次数为 n-1 ，插

入操作本身为 O(1) 。

（对比顺序表指定位置插入：顺序表需移动后续元素，为 O(n) ；两者时间复杂度相同，但链

表无需移动元素，实际效率更高）

- 空间复杂度： O(1) 

仅使用常数个临时变量（ newnode 、 prev ）。

9. 指定位置后插入函数  SLTInsertAfter 

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

- 功能：在指定节点 pos 的后面插入一个新结点（存储数据  x ）。

- 参数：

pos ：指定结点的地址（必须有效，且链表非空）。

x ：要插入的数据。

- 逻辑：

断言  assert(pos) ：确保  pos  不为  NULL （避免插入位置无效）。

调用  SLTbuyNode(x)  创建新节点  newnode 。

- 插入操作（关键：先连后断，避免链表断裂）：

-  newnode->next = pos->next ：新节点指向 pos 原来的下一个节点。

-  pos->next = newnode ： pos  指向新结点，完成插入。

- 示例：链表  1 -> 2 -> 4  中，在  pos （指向  2 ）后插入  3 ，结果为  1 -> 2 -> 3 -> 4 。

- 优势：无需查找 pos 的前一个节点，时间复杂度为  O(1) （比 SLTInsert 高效）。

- 时间复杂度： O(1) 

无需遍历，直接修改指针连接，操作次数为常数（已知 pos 的情况下）。

（顺序表无“指定位置后插入”的特殊优化，仍需移动元素，为 O(n) ；链表此操作是优势）

- 空间复杂度： O(1) 

仅使用常数个临时变量（ newnode ）。

10. 删除指定位置节点函数  SLTErase 

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

- 功能：删除链表中指定的结点  pos 。

- 参数：

pphead ：头指针的地址（可能需要修改头指针，如 pos 是头结点时）。

pos ：要删除的结点地址（必须是链表中已存在的结点）。

- 逻辑：

断言  assert(pphead && pos) ：确保  pphead  有效，且  pos  不为  NULL 。

- 分两种情况处理：

1. pos 是头结点（ pos == *pphead ）：等价于头删，直接调用  SLTPopFront(pphead) （复

用头删逻辑）。

2. pos 不是头结点：

- 查找 pos 的前一个结点 prev ：定义  prev  初始化为  *pphead ，循环  while (prev->next

!= pos)  移动  prev ，直到  prev->next == pos 。

- 操作： prev->next = pos->next （ prev  直接指向  pos  的下一个结点，断开与  pos  的

连接）。

- 释放  pos  结点（ free(pos) ），并将  pos  置为  NULL （避免野指针）。

- 示例：链表  1 -> 2 -> 3  中删除  pos （指向  2 ），结果为  1 -> 3 -> NULL 。

- 时间复杂度： O(n) 

最坏情况（ pos 为尾节点）需遍历找到 pos 的前一个结点（ prev ），遍历次数为 n-1 ，删

除操作本身为 O(1) 。

（对比顺序表指定位置删除：顺序表需移动后续元素，为 O(n) ；链表无需移动元素，效率更

优）

- 空间复杂度： O(1) 

仅使用常数个临时变量（ prev ）。

11. 删除指定位置后节点函数  SLTEraseAfter 

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

- 功能：删除指定节点 pos 后面的那个结点（即  pos->next  指向的节点）。

- 参数 : pos 为指定结点的地址（ pos  后面必须有节点可删）。

- 逻辑：

断言  assert(pos && pos->next) ：确保  pos  有效，且  pos  后面有结点（ pos->next !=

NULL ，避免删除空位置）。

- 定义 del 指针：指向要删除的结点（ pos->next ）。

- 操作：pos->next = del->next （ pos  直接指向  del  的下一个节点，断开与 del 的连

接）。

- 释放 del 节点（ free(del) ），并将  del  置为  NULL （避免野指针）。

- 示例：链表  1 -> 2 -> 3 -> 4  中， pos  指向  2 ，删除后变为  1 -> 2 -> 4 -> NULL 。

- 优势：无需查找前一个节点，时间复杂度为  O(1) 。 

- 时间复杂度： O(1) 

无需遍历，直接修改指针连接，操作次数为常数（已知 pos 的情况下）。

（顺序表无此优化，删除指定位置后元素仍需移动后续元素，为 O(n) ；链表此操作是优势）

- 空间复杂度： O(1) 

仅使用常数个临时变量（ del ）。

12. 销毁链表函数  SListDestroy 

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

- 功能：释放链表中所有节点的内存，避免内存泄漏，最终使链表变为空。

- 参数 pphead 为头指针的地址（用于将头指针置空）。

- 逻辑：

- 定义  pcur  初始化为  *pphead （从头结点开始遍历）。

- 循环  while (pcur) ：遍历所有结点。

- 定义 next 指针：记录 pcur 的下一个结点（ pcur->next ，避免释放  pcur  后丢失后续结

点地址）。

- 释放当前节点  pcur( free(pcur) ）。

- 将  pcur  移动到下一个结点（ pcur = next ）。

- 循环结束后：将头指针置为  NULL （ *pphead = NULL ），确保链表为空。

- 注意：销毁后必须将头指针置空，否则头指针会成为野指针（指向已释放的内存）。

- 时间复杂度： O(n) 

需遍历所有 n 个结点并释放内存，每个结点的操作（记录下一个节点、释放当前节点）

为 O(1) ，总耗时与节点数成正比。

- 空间复杂度： O(1) 

仅使用常数个临时变量（ pcur 、 next ）。

12. 总结:

SList.c  中的函数通过指针操作实现了单链表的完整功能，核心逻辑围绕 节点的创建、指针的移动

与连接、内存的释放 展开，同时通过断言处理边界情况（如空链表、单节点链表），确保操作的

安全性。各函数分工明确，相互配合（如插入函数调用  SLTbuyNode ，特殊位置插入复用头插/头

删逻辑），体现了代码复用的思想。

13. 补充内容(二级指针):

在单链表的代码中，函数参数使用二级指针，核心原因是需要在函数内部修改链表的头指针（或其

他指针变量本身的指向）。单链表的头指针是整个链表的“入口”，很多操作（如创建、插入、删除

头节点等）需要改变头指针的指向，此时必须通过二级指针实现。

具体场景说明（结合单链表操作）

1. 创建链表（初始化头指针）:

创建链表时，若函数内部需要为头指针分配第一个节点的地址，并让外部的头指针指向它，必须用

二级指针。

示例：

 
typedef struct Node {int data;struct Node *next;
} Node;// 创建链表（头结点），需修改外部头指针的指向
void createList(Node **head, int data) {*head = (Node*)malloc(sizeof(Node)); // 为外部头指针分配结点(*head)->data = data;(*head)->next = NULL;
}int main() {Node *head = NULL;createList(&head, 10); // 传递头指针的地址（二级指针）// 此时head已指向第一个结点return 0;
}

- 若用一级指针：函数内的 head 只是外部指针的副本，分配内存后外部 head 仍为 NULL ，无法

关联新结点。
 
2. 头插法插入结点（修改头指针）

头插法是在链表头部插入新结点，新结点会成为新的头结点，此时需要修改原头指针的指向，必须

用二级指针。

示例：

// 头插法：新结点成为新头，需修改原头指针
void insertAtHead(Node **head, int data) {Node *newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = *head; // 新节点指向原头结点*head = newNode;       // 原头指针改为指向新结点
}int main() {Node *head = NULL;insertAtHead(&head, 10); // 第一次插入：head指向新结点insertAtHead(&head, 20); // 第二次插入：head指向新的头结点（20）// 链表变为：20 -> 10 -> NULLreturn 0;
}

3. 删除头结点（修改头指针）

删除头结点后，原头指针需要指向原头结点的下一个结点（即新的头结点），此时需用二级指针修

改头指针的指向。

示例：

// 删除头结点，需更新头指针为原头结点的next
void deleteHead(Node **head) {if (*head == NULL) return; // 空链表无需删除Node *temp = *head;       // 暂存原头结点*head = (*head)->next;    // 头指针指向原头结点的下一个free(temp);               // 释放原头结点内存
}int main() {Node *head = NULL;// 假设已插入结点：20 -> 10 -> NULLdeleteHead(&head); // 传递头指针地址// 此时head指向10，链表变为：10 -> NULLreturn 0;
}

4. 销毁链表（释放所有结点并置空头指针）

销毁链表时，不仅要释放所有结点的内存，还要将外部的头指针置为 NULL （避免野指针），需

通过二级指针修改头指针本身。

示例：

// 销毁链表，释放所有结点并置空头指针
void destroyList(Node **head) {Node *current = *head;while (current != NULL) {Node *temp = current;current = current->next;free(temp);}*head = NULL; // 将外部头指针置为NULL
}int main() {Node *head = NULL;// 假设链表已存在destroyList(&head); // 传递头指针地址// 此时head为NULL，避免野指针return 0;
}

不需要二级指针的情况:

如果操作不涉及修改头指针本身的指向（仅修改节点内容或操作非头结点的指针），则用一级指针

即可。

例如：

- 向链表中间/尾部插入结点（只需修改前驱结点的 next 指针，不影响头指针）；
- 遍历链表（仅访问结点内容，不修改指针指向）；
- 修改结点的数据（通过一级指针访问 data 字段）。

总结:

单链表中二级指针的使用，本质是为了在函数内部修改头指针（或其他关键指针）的指向。由于C

语言的“值传递”特性，若要修改指针变量本身（而非它指向的内容），必须通过二级指针间接操

作。

14. 补充内容(复杂度总结):

总结：单链表与顺序表的复杂度对比核心差异:

单链表的优势在于头部操作和已知前驱/后继的插入删除，时间复杂度为 O(1) ；劣势是尾部操作和

查找前驱需遍历，时间复杂度为 O(n) （顺序表通过下标随机访问可弥补此劣势）。

1.3 测试文件（test.c  ）

#include"SList.h"void test01()
{SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;node2->data = 2;node3->data = 3;node4->data = 4;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;SLTNode* plist = node1;SLTPrint(plist);
}void test02()
{//创建空链表SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);//SLTPushFront(&plist, 1);//SLTPushFront(&plist, 2);//SLTPushFront(&plist, 3);//SLTPushFront(&plist, 4);//SLTPrint(plist);//SLTPushFront(NULL, 4);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);////SLTPopBack(&plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);////SLTPopFront(&plist);SLTNode* find = SLTFind(plist, 4);//if (find)//{//	printf("找到了！\n");//}//else {//	printf("未找到！\n");//}//SLTInsert(&plist, find, 100);//1 2 3 100 4 //SLTInsertAfter(find, 100);//1 100 2 3 4//SLTErase(&plist, find);//SLTEraseAfter(find);//1 3 4//SLTPrint(plist);SListDestroy(&plist);
}int main()
{test01();test02();return 0;
}

-  test01 ：手动创建4个结点并串联成链表，测试打印功能。

-  test02 ：测试尾插、头插、尾删、头删、查找、插入、删除等接口，验证基本功能的正确性，最

后调用 SListDestroy 销毁链表。

好了，关于单链表实现的代码的所有内容已经讲解完毕。小编下来把完整版代码留给大家。

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;//typedef struct SListNode 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;while (pcur){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("NULL\n");
}SLTNode* SLTbuyNode(SLTDataType x)
{//根据x创建节点SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTbuyNode(x);//链表为空if (*pphead == NULL){*pphead = newnode;}else {//找尾SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptail newnodeptail->next = newnode;}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTbuyNode(x);//newnode *ppheadnewnode->next = *pphead;*pphead = newnode;
}
//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);//只有一个结点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else {SLTNode* prev = NULL;SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}//prev ptailprev->next = NULL;free(ptail);ptail = 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 && pos);//当pos指向第一个结点，是头插if (pos == *pphead){SLTPushFront(pphead, x);}else {SLTNode* newnode = SLTbuyNode(x);//找pos的前一个结点SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev--> newnode--> posprev->next = newnode;newnode->next = pos;}
}
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTbuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;pos->next = newnode;
}//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && pos);//pos就是头结点if (pos == *pphead){SLTPopFront(pphead);}else {SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}
}
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);//pos del del->nextSLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}//销毁链表
void SListDestroy(SLTNode** pphead)
{SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

test.c文件:

#include"SList.h"void test01()
{SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;node2->data = 2;node3->data = 3;node4->data = 4;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;SLTNode* plist = node1;SLTPrint(plist);
}void test02()
{//创建空链表SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);//SLTPushFront(&plist, 1);//SLTPushFront(&plist, 2);//SLTPushFront(&plist, 3);//SLTPushFront(&plist, 4);//SLTPrint(plist);//SLTPushFront(NULL, 4);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);////SLTPopBack(&plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);////SLTPopFront(&plist);SLTNode* find = SLTFind(plist, 4);//if (find)//{//	printf("找到了！\n");//}//else {//	printf("未找到！\n");//}//SLTInsert(&plist, find, 100);//1 2 3 100 4 //SLTInsertAfter(find, 100);//1 100 2 3 4//SLTErase(&plist, find);//SLTEraseAfter(find);//1 3 4//SLTPrint(plist);SListDestroy(&plist);
}int main()
{test01();test02();return 0;
}

以上便是单链表实现的所有代码。对于小编而言，我感觉还是有一定的难度。如果小编有写的不对

的地方，也希望大家能够在评论区纠正。小编写完才发现写了17000多个字，是小编写过最长的一

篇博客了。难免会出现小错误，如果出现了也请大家多多谅解。如果在某些地方有更好的方法，也

希望大家分享给小编。小编非常开心，也非常欢迎能够和大家交流。最后如果您能看到这，说明您

也是一位非常善于求学的人。也非常感谢您的观看。谢谢大家！