单/双链表的传参解析-平芜编程栈

摘要：

一：传递参数的必要性

二：单链表参数

三：双链表参数

四：双链表参数为哨兵位

五：单/双链表的实现差异

摘要：

在链表的学习和实现中，我们会发现链表相关函数都必须进行传参，而单链表，双链表的传参方式却又不同。为什么单链表虽然结构简单，但实现复杂，而双链表虽然结构复杂，但实现简单，此博客就这些问题，进行一定的讲解.......

注：

单链表：单向不带头不循环链表，博客：单链表的实现讲解

双链表：双向带头循环链表，博客：双链表的实现讲解

头结点在正确概念中指的是哨兵位节点，而我们在不带头链表中也会将第一个节点成为头结点，这是一种形象的说法，会让我们更好理解，但是要知道这种说法是不合规的

一：传递参数的必要性

首先我们不从传参方式不同的角度来看，而是从为什么都需要传参的角度来理解！

不管是单链表还是双链表，我们在插入删除相关的函数，都是需要用到头指针的，原因大致可分为两种类型：

1：函数需要遍历

本质是因为函数需要头指针才能进行遍历，比如尾插，则需要从头指针指向的节点向后变量找到尾节点....，头指针（或头节点的地址）是访问整个链表的入口。由于链表的节点在内存中不是连续存储的，而是通过指针链接在一起，因此要访问、查找、插入或删除节点，通常都需要从链表的起始位置开始，沿着next指针（对于双向链表还有prev指针）一步步移动，直到找到目标位置。

2：头指针可能会被改变

在某些函数中不需要遍历链表，但函数内部仍需要头指针，比如头删，尾删，本质是因为删除之后可能导致头结点改变了，从而头指针也要指向更新后的头结点！

二：单链表参数

而单链表是不带头的，没有哨兵位的，则代表头结点是可能更改的，则头指针plist也是可能被修改的，而头指针本身就是一级指针，你调用的函数内部可能会修改头指针本身，则你当然要传递二级指针，也就是&plist作为函数的参数啦~

所以现在我们再回过头来看单链表的SList.c文件：

#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLTDataType; //定义链表结点的结构 typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; //创建新节点 SLTNode* SLTBuyNode(SLTDataType x); //尾插 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 SLTPrint(SLTNode* phead); //销毁链表 void SListDestroy(SLTNode** pphead);

解释：我们会发现但凡参数是二级指针的，则代表该函数可能会影响到plist本身！

①：头删，尾删，头插，尾插；头删不必多说，肯定会影响到plist本身；而尾删时，若为空链表，则也等同于头删，会影响到plist本身；头插会有新节点作为头结点，也会影响到plist本身；而尾插时，若为空链表，则也相当于头插了，会影响到plist本身

②：SLTInsert，在pos位置前插入，若pos为头结点，则等同于头插，所以会影响到plist本身；SLTErase删除pos节点，若pos节点为头结点，则等同于头删吗，所以会影响到plist本身；SListDestory销毁链表，则一定会销毁头结点，所以会影响到plist本身；

③：而SLTFind，SLTEraseAfter，SLTPrint则传递一级指针，也就是实参为plist即可，因为SLTFind查找函数，只负责查找，不可能改变头结点；SLTEraseAfter在pos位置之后插入函数，pos极限就是头结点，所以最多也是在头结点之后插入函数，不可能改变头结点，SLTPrint同理

三：双链表参数

而双链表是带头的，是有哨兵位的，则代表头结点是不可能被更改的！则头指针plist值是固定的，一定是哨兵位节点的地址！所以在所有函数中，我们只需要传递plist本身即可！

所以现在我们再回过头来看双链表的List.c文件：

#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> //单个节点的声明 typedef int LTDataType; typedef struct ListNode { struct ListNode* next; // 指向下一个节点的指针 struct ListNode* prev; // 指向前一个节点的指针 LTDataType data; // 节点存储的数据 }LTNode; // 创建新节点， LTNode* BuyLTNode(LTDataType x); // 初始化 LTNode* LTInit(); ////初始化的另一种写法 //void LTInit(LTNode** pphead) // 打印 void LTPrint(LTNode* phead); // 尾插 void LTPushBack(LTNode* phead, LTDataType x); // 尾删 void LTPopBack(LTNode* phead); // 头插 void LTPushFront(LTNode* phead, LTDataType x); // 头删 void LTPopFront(LTNode* phead); // 获取节点数量 int LTSize(LTNode* phead); // 查找 LTNode* LTFind(LTNode* phead, LTDataType x); // 在pos位置前插入 void LTInsert(LTNode* pos, LTDataType x); // 删除pos位置 void LTErase(LTNode* pos); //销毁 void ListDestroy(LTNode* phead); ////销毁 的另一种写法 //void ListDestroy(LTNode** pphead)

解释：我们会发现所有函数参数都是一级指针，实参为plist，本质是因为所有的函数都不会影响到plist的值，其永远指向哨兵位！但是仅有ListDestroy销毁函数也会影响到plist本身！

Q：销毁函数是肯定也会把哨兵位进行销毁的，所以plist最后值为NULL，那为什么这里还能传递一级指针呢？

A：

①：首先传递一级指针，代表phead的值和plist的值一模一样，此时若是更改phead的值则无法影响到plist本身，但是销毁函数不更改phead的值，而是直接free(phead)，因为phead的值和plist的值是一致的，所以free(phead)就等同于在main函数中free(plist)，而我们唯一需要善后的地方吗，在于我们在main函数中ListDestroy函数之后，还需手动的将plist置为NULL！因为你在销毁函数中将phead置为NULL，是影响不到plist的！

②：其次，我们如果不想保持所有接口参数的一致性，不保持都为一级指针。则我们可以将销毁函数的参数设置为二级指针，这样我们就可以在ListDestroy内部对(*pphead)置NULL了

四：双链表参数为哨兵位

❓️：那既然双链表的函数是不会影响到头结点的，则不会影响到头指针的值的，我们也知道传递头指针是为了遍历链表，那为什么不传递头结点本身呢？函数接收到头结点本身，不也可以通过头结点的成员变量next和prev变量链表吗？为什么还非要传递指针呢？

💡：传递哨兵位节点本身，是一定不对的！

缺陷1：形参的开销

如果你直接传递一个结构体变量，函数形参，则完整地拷贝一份整个结构体到函数的栈空间里，一个节点就是data和两个指针，节点一多，开销太大！

缺陷2：无法更改哨兵位的指向

传递结构体本身，函数得到的是哨兵节点的副本。这个副本虽然和哨兵位的data，next，prev到一模一样，你也能通过prev和next前后遍历，但是你再怎么，你也是一个副本节点，你虽然什么都和哨兵位一样，但是你的地址和哨兵位不一样！这就代表你如果修改副本的next和prev，虽然可以修改，但是影响不到哨兵位节点的next和prev的一丝一毫！这意味着头插头删等操作都无法进行！

如图：

缺陷3：

如图可得，如果你从副本节点开始遍历，则你再也回不到你的副本节点了，副本通过next就会进入到双链表中，而因为没有节点的指针指向这个副本，所以无法回到副本！这意味这如果你采取传递结构体本身的方式，则你的函数一般会使用到判断副本结构体的指针来进行循环，则一定死循环！

五：单/双链表的实现差异

为什么单链表虽然结构简单，但实现复杂，而双链表虽然结构复杂，但实现简单，其实本质就是空间换时间，在设计上，双链表更复杂，占用的空间更多，但是在实现和效率是，双链表更优秀

写单链表最头疼的就是处理“头节点”和“尾节点”的空指针问题。

单链表：
如果你要删除的是最后一个节点，或者在第一个节点前插入，你需要写大量的if (prev == NULL)之类的判断，否则程序就会因为空指针崩溃。

双链表：
由于有prev指针，有哨兵头节点，整个链表变成了一个完美的闭环。头节点的prev指向尾节点，尾节点的next指向头节点。这时候，所有的节点都是“中间节点”，没有任何特殊的边界情况需要处理。你的代码只需要写一套通用的逻辑，就能处理所有情况。

总结
单链表结构简单：每个节点只存一个next，省内存，结构图看起来清爽。
单链表实现复杂：因为信息量少（不知道前驱是谁），导致代码必须通过复杂的遍历和大量的if-else来弥补信息的缺失。
双链表结构复杂：多了哨兵位，每个节点多了一个prev指针，内存开销变大，结构图看起来乱糟糟。
双链表实现简单：因为信息量足（左右邻居都知道），代码逻辑变得非常直接、暴力且统一，大大降低了写出 Bug 的概率。
但只要理解了双链表的结构，实现起来更简单了，效率也飙升了，所以在实际的工程开发中，大家往往更偏爱双链表，因为开发和维护的便利性远比省那几个字节的内存重要的多！