C/C++数据结构 — 单链表_c++单链表

​ 🎁个人主页：工藤新一¹

​ 🔍系列专栏：C++面向对象（类和对象篇）

​ 🌟心中的天空之城，终会照亮我前方的路

​ 🎉欢迎大家点赞👍评论📝收藏⭐文章

文章目录

• 单链表
• • 一、对于顺序表的思考
  • 二、单链表
  • • 2.1概念与结构
    • 2.2节点
    • 2.3链表结构的创建
    • • 2.3.1值传递与地址传递的讨论
    • 2.4尾插
    • • 2.4.1值传递
      • 2.4.2**指针也是一个变量**
      • 2.4.3指针与二级指针的关系
    • 2.5头插 + 尾删 + 头删
    • 2.6*查找
    • 2.7在指定位置插入元素
    • • 2.7.1在指定位置前插入元素
      • 2.7.2在指定位置后插入元素
    • 2.8删除操作
    • • 2.8.1删除指定节点
      • 2.8.2删除指定节点后的节点
    • 2.9销毁链表
  • 3链表实现

单链表

一、对于顺序表的思考

• 尾插时间复杂度：O(1)；中间/头部的插入或删除，时间复杂度：O(N)
• 增容需要申请新空间，拷贝旧数据，释放旧空间，这势必会遭成不小的消耗
• 增容一般是呈2倍的增长，势必会有一定空间的浪费

---

思考，如何解决一下问题：

• 头插时间复杂度是否可以变为O(1)
• 是否可以省去增容操作就可以存储数据？并且不会浪费空间？

---

链表：不存在空间浪费的情况

顺序表 更适尾部的插入/删除：O（1）

链表 更适合头部的插入/删除：O（1）

---

二、单链表

• 基于以上思考，我们便有了 链表 的概念
• 单链表对头部操作的时间复杂度：O（1）
• 顺序表对尾部操作的时间复杂度：O（1）

2.1概念与结构

• 单链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含两部分：数据域和指针域。

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

• 逻辑结构：线性的

• 物理结构：非线性的（严谨一点：不一定…，因为系统有可能会随机申请到一块连续的内存）（链表由一个一个的节点组成，每个节点所向操作系统申请的空间都是独立的）>

---

2.2节点

• 链表是由一系列节点（车厢）组成的，其中节点包括：数据域（存储当前节点的数据）、指针域（存储下一节点的地址），同时每个节点也都是一个独立的空间
• 删除指定位置后的节点，时间复杂度：O（1）

---

2.3链表结构的创建

• SList.h文件

#pragma once#include#include#include#includetypedef int SLDataType;//将存储数据（data）的类型都变为SLDataType，方便替换//定义链表的结构 -- 结点的结构（结点：数据域 + 指针域）typedef struct SListNode{SLDataType data;//存储的数据，数据域 struct SListNode* next;//指向下一个结点，指针域}SLTNode;--->结构体指针/*typedef int SLTDateType;typedef struct SListNode{ SLTDateType data; struct SListNode* next; SListNode(int val) : data(val), next(nullptr) {}}SLTNode;*///链表的输出void SLTPrint(SLTNode* phead);//头节点

• test.cpp 链表结点的定义

#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;//定义车头，plist指向 node1 SLTPrint(plist);//调用 SLTPrint 输出链表}int main(){test01();return 0;}

• SList.cpp文件，链表的输出实现

#include\"SList.h\"void SLTPrint(SLTNode* phead)//phead 存储的值就是地址(值传递){ SLTNode* pcur = phead;//使 phead 始终指向头结点，方便再次遍历时，可以始终从左至右进行遍历循环 while(pcur)//pcur != NULL; { printf(\"%d -> \", pcur->data); pcur = pcur->next; } printf(\"NULL\\n\");}

---

2.3.1值传递与地址传递的讨论

---

2.4尾插

• 申请节点 – 调用 BuyNode 方法 .cpp

C //通过 BuyNode 方法创建新节点SLTNode* SLTBuyNode(SLDataType x){//根据 x 创建节点SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL){perror(\"malloc fail!\");exit(1);}newnode->data = x;//为新节点初始化数据域newnode->next = NULL;//初始化指针域return newnode;//返回是申请好的 newnode} 

• 尾插.cpp

C void SLTPushBack(SLTNode* phead, SLDataType x){ SLTNode* newnode = SLTBuyNode(x); if(phead == NULL)//链表为空 { phead = newnode;//那么newnode就是头节点 } //链表不为空 else{ SLTNode* ptail = phead; while(ptail->next) { ptail = ptail->next; } //找到了尾节点 ptail->next = newnode; }}

• 创建链表.test

Cvoid test02(){//创建空链表SLTNode* plist = NULL;SLTPrint(plist); SLTPushBack(plist, 1);SLTPrint(plist);}

• 输出结果

---

调试结果：

在调试窗口中，我们发现，newnode正确的调用 BuyNode函数（正确被初始化），但代码调用结束后，plist并未发生任何变化，无法读取 data、next 数据，因此，这就发生了非常常见的问题：“形参是实参的一份临时拷贝，值传递 - 形参无法影响实参”

---

方法一：一级指针引用

---

方法二：二级指针

---

方法三：返回指针

---

2.4.1值传递

---

• 得出结论

因此，我们便明白了问题所在 —— 值传递，形参只是实参的一份临时拷贝，形参无法改变实参

---

2.4.2指针也是一个变量

---

2.4.3指针与二级指针的关系

• 二级指针接收一级指针的地址

Ctest.cpp SLTPushBack(&plist, 1);//使用二级指针来接收一级指针的地址SList.h void SLTPushBack(SLTNode** pphead, SLDataType x);SList.cpp void SLTPushBack(SLTNode** pphead, SLDataType x){}

C SList.cpp void SLTPushBack(SLTNode** pphead, SLDataType x){SLTNode* newnode = SLTBuyNode(x);//直接调用 BuyNode 方法 //对二级指针 --->(解引用)---> 一级指针if (*pphead == NULL){*pphead = newnode;}else {SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}}

---

• 调试

C void test02(){//创建空链表SLTNode* plist = NULL; //为使形参改变实参，因此需要地址传递SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);}

---

2.5头插 + 尾删 + 头删

• .cpp文件

C//头插 - 使形参可改变实参(因此，需要地址传递)void SLTFrontBack(SLTNode** pphead, SLDataType x){assert(pphead);SLTNode* newnode = SLTBuyNode(x); newnode->next = *pphead;*pphead = newnode;}//尾删 - 使形参可改变实参(因此，需要地址传递)void SLTPopBack(SLTNode** pphead){//pphead传参、*pphead链表首节点不能为空assert(pphead && *pphead);//-> 的优先级 > * 操作if ((*pphead)->next == NULL)//当节点只有 1 个时{ //直接释放头结点的地址free(*pphead);*pphead = NULL;}else {SLTNode* prev = NULL;//前驱节点SLTNode* ptail = *pphead;while (ptail->next){//使前驱节点指向当前节点prev = ptail;//使当前节点指向下一个节点ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}}//头删void SLTPopFront(SLTNode** pphead){assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);//释放（*pphead）所指向的数据*pphead = next;//使（*pphead）指向 next 节点}void SLTFrontPop(SLTNode** pphead){ // 空链表 if(!*pphead) return; SLTNode* pcur = *pphead; *pphead = (*pphead)->next; delete pcur;}

---

2.6*查找

• test.cpp

C void test02(){ int position = -1;//地址传递:&position，使形参改变实参SLTNode* find = SLTFind(plist, 10, &position);//id = 0 开始if (find) {printf(\"找到了!位置：%d\\n\", position);printf(\"节点数据：%d\\n\", find->data);}else {printf(\"未找到！\\n\");}}

---

• SList.cpp

C //查找SLTNode* SLTFind(SLTNode* phead, SLDataType x, int* position){SLTNode* pcur = phead;int pos = 0; // 用于记录当前节点的位置while (pcur){if (pcur->data == x){ *position = pos; return pcur;}pcur = pcur->next;pos++;}return NULL;}

---

2.7在指定位置插入元素

2.7.1在指定位置前插入元素

时间复杂度：O（N）

• test.cpp

C SLTInsert(&plist, find, 100);SLTPrint(plist);

---

• SList.cpp
• 空指针异常

C //指定位置前插入数据void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x){assert(pphead && pos);SLTNode* prev = *pphead;SLTNode* newnode = SLTBuyNode(x);//如果 pos 刚好指向头结点，就会出现 \"空指针异常\"//因此处理 当 pos 指向头结点 - 直接头插if (pos == *pphead){SLTPushFront(pphead, x);}else {while (prev->next != pos){prev = prev->next;}//prev--> newnode--> pos //前驱节点的后继指针指向newnode节点prev->next = newnode;newnode->next = pos;}} 

---

2.7.2在指定位置后插入元素

时间复杂度：O（1）

• 在指定位置后插入元素，是没有空指针异常的

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

---

2.8删除操作

2.8.1删除指定节点

时间复杂度：O（N）

• 处理空指针异常

C //删除 pos 位置上的节点void SLTErase(SLTNode** pphead, SLTNode* pos){assert(pphead && pos);SLTNode* prev = *pphead;//处理 \"空指针\" 异常 - pos 是首节点if (pos == *pphead){SLTPopFront(pphead);}else {while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}}

---

2.8.2删除指定节点后的节点

时间复杂度：O（1）

Cvoid SLTEraseAfter(SLTNode* pos) {//保证 pos->next 不为空，避免 free(NULL) 操作 - 断言报错assert(pos && pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;}

---

2.9销毁链表

• 前面我们有提到过，顺序表、链表的底层是数组，所以有过 free(ps -> arr) 操作（因为数组的存储结构是连续的，因此free(ps -> arr) 会将数组中所以的数据都释放掉）
• 但链表中，其每个节点都是独立申请的，释放其中某一节点，不会影响其他节点正常运行

C //销毁链表 pphead - 指向链表节点的起始地址void SListDestory(SLTNode** pphead){assert(pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* dest = pcur->next;//存储下一个要释放的目标free(pcur);//释放的是 pcur 所指向的数据pcur = dest;}*pphead = NULL;//避免 *pphead 成为野指针，手动置空}

---

3链表实现

• SList.h

#pragma once#include#include#include#includetypedef int SLDataType;//将存储的数据类型都变为SLDataType，方便替换//定义链表的结构 -- 结点的结构（结点：数据域 + 指针域）typedef struct SListNode{SLDataType data;//存储的数据，数据域struct SListNode* next;//指向下一个结点，指针域}SLTNode;//链表的输出 void SLTPrint(SLTNode* phead);//头节点//尾插void SLTPushBack(SLTNode** pphead, SLDataType x);//头插void SLTPushFront(SLTNode** pphead, SLDataType x);//尾删void SLTPopBack(SLTNode** pphead);void SLTPopFront(SLTNode** pphead);SLTNode* SLTFind(SLTNode* phead, SLDataType x, int* position);//指定位置前插入数据void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x);//指定位置后插入数据void SLTInsertAfter(SLTNode* pos, SLDataType x);//删除 pos 位置上的节点void SLTErase(SLTNode** pphead, SLTNode* pos);//删除 pos 位置后的节点void SLTEraseAfter(SLTNode* pos);//销毁链表 pphead - 指向链表节点的起始地址void SListDestory(SLTNode** pphead);

---

• SList.test

#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, 10);SLTPushFront(&plist, 20);SLTPushFront(&plist, 30);SLTPushFront(&plist, 40);SLTPrint(plist);//为使形参改变实参，因此需要地址传递SLTPopBack(&plist);SLTPopBack(&plist);SLTPopBack(&plist);SLTPrint(plist);int position = -1;//地址传递:&position，使形参改变实参SLTNode* find = SLTFind(plist, 40, &position);//id = 0 开始if (find) {printf(\"找到了!位置：%d\\n\", position);printf(\"节点数据：%d\\n\", find->data);}else {printf(\"未找到！\\n\");}//此时，find = 0;SLTInsert(&plist, find, 100);SLTPrint(plist);//此时，find = 1;(查找40)SLTErase(&plist, find);SLTPrint(plist);SListDestory(&plist);}int main(){//test01();test02();return 0;}

---

• SList.cpp

#include\"SList.h\"void SLTPrint(SLTNode* phead){SLTNode* pcur = phead;while (pcur){printf(\"%d -> \", pcur->data);pcur = pcur->next;}printf(\"NULL\\n\");}//申请节点 - 调用 BuyNode方法SLTNode* SLTBuyNode(SLDataType 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, SLDataType x){assert(pphead);SLTNode* newnode = SLTBuyNode(x);//直接调用 BuyNode 方法//链表为空if (*pphead == NULL){*pphead = newnode;}/*注意区分：如果链表为空（phead == NULL），访问 phead->next 会导致未定义行为（如段错误）。因此，不能直接使用：if(phead->next == NULL)因为 phead 所存储的本就是一段地址，phead->next是指所存储的下一节点的地址因此，会有 phead 本身就为空的情况*/ else {//找尾节点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}}//头插 - 使形参可改变实参(因此，需要地址传递)void SLTPushFront(SLTNode** pphead, SLDataType x){assert(pphead);SLTNode* newnode = SLTBuyNode(x); newnode->next = *pphead;*pphead = newnode;}//尾删 - 使形参可改变实参(因此，需要地址传递)void SLTPopBack(SLTNode** pphead){//pphead传参、*pphead链表首节点不能为空assert(pphead && *pphead);//-> 的优先级 > * 操作if ((*pphead)->next == NULL)//当节点只有 1{free(*pphead);*pphead = NULL;}else {SLTNode* prev = NULL;//前驱节点SLTNode* ptail = *pphead;while (ptail->next){//使前驱节点指向当前节点prev = ptail;//使当前节点指向下一个节点ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}}//头删void SLTPopFront(SLTNode** pphead){assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);//释放（*pphead）所指向的数据*pphead = next;//使（*pphead）指向 next 节点}//查找SLTNode* SLTFind(SLTNode* phead, SLDataType x, int* position){SLTNode* pcur = phead;int pos = 0; // 用于记录当前节点的位置while (pcur){if (pcur->data == x){ *position = pos; return pcur;}pcur = pcur->next;pos++;}return NULL;}//指定位置前插入数据void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x){assert(pphead && pos);SLTNode* prev = *pphead;SLTNode* newnode = SLTBuyNode(x);//如果 pos 刚好指向头结点，就会出现 \"空指针异常\"//因此处理 当 pos 指向头结点 - 直接头插if (pos == *pphead){SLTPushFront(pphead, x);}else {while (prev->next != pos){prev = prev->next;}//prev--> newnode--> pos//前驱节点的后继指针指向newnode节点prev->next = newnode;newnode->next = pos;}} //在指定位置后插入数据void SLTInsertAfter(SLTNode* pos, SLDataType x){assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode; }//删除 pos 位置上的节点void SLTErase(SLTNode** pphead, SLTNode* pos){assert(pphead && pos);SLTNode* prev = *pphead;//处理 \"空指针\" 异常 - pos 是首节点if (pos == *pphead){SLTPopFront(pphead);}else {while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}}void SLTEraseAfter(SLTNode* pos) {//保证 pos->next 不为空，避免 free(NULL) 操作 - 断言报错assert(pos && pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;}//销毁链表 pphead - 指向链表节点的起始地址void SListDestory(SLTNode** pphead){assert(pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* dest = pcur->next;//存储下一个要释放的目标free(pcur);//释放的是 pcur 所指向的数据pcur = dest;}*pphead = NULL;//避免 *pphead 成为野指针，手动置空}

• 由此，我们便可发现，单链表对头部操作的时间复杂度：O（1）
• 而顺序表对尾部操作的时间复杂度：O（1）

---

---

---

---

---

防范悬垂指针：

---

---

---

---

---

---

---

---

---

---

---

删除链表中的指定元素

---

翻转链表

---

---

🌟 各位看官好，我是工藤新一¹呀~

🌈 愿各位心中所想，终有所致！