【数据结构】双向链表 超详细 （含：何时用一级指针或二级指针；指针域的指针是否要释放） |
您所在的位置：网站首页 › 为什么参数要使用指向指针的指针执行操作 › 【数据结构】双向链表 超详细 （含：何时用一级指针或二级指针；指针域的指针是否要释放） |
【数据结构】双向链表 超详细 （含：何时用一级指针或二级指针；指针域的指针是否要释放）
|
目录 一、简介 二. 双链表的实现 1.准备工作及其注意事项 1.1 先创建三个文件 1.2 注意事项：帮助高效记忆 1.3 关于什么时候 用 一级指针接收，什么时候用 二级指针接收？ 1.4 释放节点时，要将节点地址 置为NULL，难道 节点内部的 指针域的指针 就不用置为 NULL吗？ 2.双链表的基本功能接口 2.1 初始化哨兵位 2.2 链表的创建新节点接口 2.3 打印 3. 插入 接口 3.1 尾插法 3.2 头插法 3.3 在 pos 位置之后插入数据 4. 查找 5.删除 接口 5.1 尾删法 5.2 头删法 5.3 删除 pos 位置的数据 6. 销毁链表 接口 6.1 二级指针版 6.2 一级指针版 7. 总代码概览 List.h List.c test.c 三. 顺序表和双向链表的优缺点分析
单向链表在解决那些需要大量查找前趋节点的问题时，效率较为低下，因为单向链表适合“从前往后”查找，并不适合“从后往前”查找。 （若想要看 单链表，可以点击跳转：【数据结构】单向链表实现 超详细） 如果要提高链表的查找效率，那 双向链表（双链表）无疑是首选。 双向链表：即为 字面上的意思是“双向”的链表，如下图所示。
解释这三个文件的作用 1、头文件List.h 是来声明接口函数，定义链表，将几个公共用到的库函数集合起来 2、源文件List.c 是用来具体实现接口 3、源文件test.c 用于接口的测试工作 ，即具体的使用场景 1.2 注意事项：帮助高效记忆1. 传递指针，都要断言 不能为 NULL ，指针不能为空：assert(phead); 2. 存在 关系到 前趋节点prev 或 后继节点next 的 情况， 可以 直接定义变量 Prev = .... Next = .... 便于 理清思路，不易乱 3. 所有的 删除接口 都需要 断言链表不能只有 哨兵位： assert(phead->next != phead); 4. 尾删法: 记得双链表的找尾 不像 单链表需要循环去找尾！！ptail = phead->prev; 5. 初始化创建头节点：推荐使用 调用 创建节点接口 的 方法 5. 销毁接口：推荐使用 传一级指针的方法 1.3 关于什么时候 用 一级指针接收，什么时候用 二级指针接收？（不看水话，可以直接 看下面 总结 部分）（有点水话，实在不明白思路的可以看一下详细解说的 ”水话“） 在 单向链表 中，有一个指向 第一个节点的指针 plist，由于 头插法等操作，可能会改变 第一个节点，则 plist 要对应进行 更新，而 要想直接改变一个变量（plist是指针变量）的值，需要传地址，plist 的 &plist 是 一级指针的地址，就要用 二级指针 来接收 在 双向链表 中，存在 头节点 head ，即 哨兵位，哨兵是 不用进行 改变本身这个节点的 地址的！！ 那就有铁铁要问了，不是还要改变 头节点 head（ 哨兵位 ） 的指向，要指向 第一个 节点 或 尾节点 吗？ 回答：因为 我们 要改变的 是 双链表节点 结构 中 的 结构体成员变量：prev 和 next ，改变 结构体的成员变量 只需要利用 结构体指针 p->prev = .... 或 p->next = .... 就达到 修改 双链表节点指向 问题了，而你本身并不需要改变 一个节点的地址 p 总结总结：修改 双链表节点 的指向，是通过 修改节点结构体内部的 两个成员变量 来实现的，只需要用到 结构体指针（即该节点的地址 p），找到 两个成员变量，即可完成修改，因而传递 一级指针就好，不用像 单链表那样还要 传递 一级指针的 地址 1.4 释放节点时，要将节点地址 置为NULL，难道 节点内部的 指针域的指针 就不用置为 NULL吗？ 回答：不用 因为节点的空间已经还给操作系统了 那个指针域的指针所占据的空间也还回去了 操作系统后续分配内存就会把那块空间覆盖掉 就不会又啥影响 2.双链表的基本功能接口 2.1 初始化哨兵位初始化哨兵位 第一种方法：传入 指针，进行"加工" 成 哨兵位 // 初始化一个哨兵位： void LTInit(LTNode** pphead) { *pphead = (LTNode*)malloc(sizeof(LTNode)); // 开辟空间是否成功的判断：一般malloc不会失败，失败证明内存不够了，写下面的证明算是好习惯，不写一般没问题 if (*pphead == NULL) { perror("malloc fail!"); exit(1); } (*pphead)->data = -1; (*pphead)->next = (*pphead)->prev = *pphead; // 哨兵位初识化，两个指针都指向自己 }初始化哨兵位第二种方法：直接一个函数生成一个哨兵位，返回哨兵位就好，不用传指针 LTNode* LTInit() { LTNode* phead = (LTNode*)malloc(sizeof(LTNode)); // 开辟空间是否成功的判断 if (phead == NULL) { perror("malloc fail!"); exit(1); } phead->data = -1; // data 随便定，反正哨兵位data无效 phead->next = phead->prev = phead; return phead; }初始化哨兵位 第二种方法的2.0 版本：因为哨兵位的初始化 和 2.2 创建新新节点的方法一样，可以合并调用 LTNode* LTInit_2() { LTNode* phead = LTCreatNode(-1); return phead; } 2.2 链表的创建新节点接口 // 创建新节点 LTNode* LTCreatNode(LTDataType x) { LTNode* newNode = (LTNode*)malloc(sizeof (LTNode)); if (newNode == NULL) { perror("malloc fail!"); exit(1); } newNode->data = x; newNode->prev = newNode->next = newNode; // 都是 指向自己 return newNode; } 2.3 打印双链表的打印 和 单链表打印一样，都需要循环，但是结束条件不一样 单链表以 pcur = NULL 为结束条件，双链表是 一种循环链表，头尾相连，不会有 pcur = NULL 的情况 正解：既然 哨兵位无有效数据，同时 循环一轮 还是 回到头（哨兵位），干脆：while (pcur != phead) void LTPrint(LTNode* phead) { assert(phead);// 哨兵位不能为空 LTNode* pcur = phead->next; while (pcur != phead) { printf("%d -> ", pcur->data); pcur = pcur->next; } printf("\n"); } 3. 插入 接口前言： // 不需要改变哨兵位，则不需要传二级指针 // 如果需要修改哨兵位的话，则传二级指针 3.1 尾插法
双链表的 尾插法 双向链表尾插需不需要找尾的操作 ? 不需要 ：ptail = head->prev; 注意这个 等价关系，便于理解下面的代码 尾插法 也称作 在哨兵位之前插入节点/最后一个有效节点之后插入数据 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead);// 哨兵位不能为空 LTNode* newNode = LTCreatNode(x); LTNode* ptail = phead->prev; // 三者关系：phead->prev(即ptail) newNode phead // 处理顺序：先 newNode， 再 phead->prev(即ptail) ，最后 phead：否则会乱套 // 先 newNode newNode->next = phead; newNode->prev = ptail; // 就是 phead->prev // 再尾节点 ptail = head->prev ; ptail -> next = head-> prev -> next; ptail->next = newNode; // 最后头节点 phead->prev = newNode; } 3.2 头插法双链表的 头插法 注意：头插 是在第一个有效位置进行插入，不是在哨兵位 前面，由于 双链表的循环成环状的特性，若在哨兵位前面，就是尾插了
在 pos 位置之后插入数据：要配合 4.查找 接口实现 和 头插法思路一样：只是将 哨兵的带头作用 换成了 pos pos 是通过 4.查找 的接口找的 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); // 先创建新节点 LTNode* newNode = LTCreatNode(x); // 关系三个节点：pos newNode pos->next // 先处理newNode，后 pos->next ， 最后 pos // 注意三者的执行顺序 不能换！！ LTNode* Next = pos->next; // 这里将 pos 的下一个节点(pos->next) 命名成 Next （避免和 next 混淆） newNode->next = Next; newNode->prev = pos; Next->prev = newNode; pos->next = newNode; } 4. 查找 LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); // 下面是遍历 双链表的模板操作 LTNode* pcur = phead->next; while (pcur != phead) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } return NULL; } 5.删除 接口 5.1 尾删法// 思路：让 倒数第二个 节点 next 指向 head ，head 指向 倒数第二个节点，最后 free 掉 ptail // 尾节点前一个节点：ptail->prev = phead->prev->prev // 尾节点：ptail = phead->prev // "尾节点前一个节点" 指向 head哨兵位：ptail->prev->next = phead; // head哨兵位 指向 "尾节点前一个节点" ：phead->prev = ptail->prev; // 最后 free 掉 ptail
// 被删除的 第一个有效节点：pFirst = phead->next; // 下一个节点 pSecond = pFirst->next; // 先 下一个节点 指向 head ： pSecond->prev = phead; // 后 head 指向 下一个节点 ：phead->next = pSecond; // 注意：因为对于循环链表来说， 第一个节点的下个节点 也可以是 哨兵位，所以 只存在一个有效节点，也是可以直接删除第一个节点的、
删除 pos 位置的数据：要配合 4.查找 接口实现 void LTErase(LTNode* pos) { assert(pos); // 关系三个节点： pos->prev pos pos->next LTNode* Prev = pos->prev; // pos 的前一个 LTNode* Next = pos->next; // pos 的下一个 Next->prev = Prev; Prev->next = Next; free(pos); pos = NULL; } 6. 销毁链表 接口更推荐 一级指针版：手动置为NULL 为了保持 接口的一致性：不然前面接口都是 一级指针，到这里突然 二级指针，当程序交给用户时，会增加记忆的成本 6.1 二级指针版// 思路：先将 有效节点删除，后删除哨兵位 // 删除有效节点, 要将下个节点保存起来，不然找不到 // 注意：这里 最后需要 改变 哨兵位 为NULL ，因而要传递地址，用二级指针接收 // 否则，传值 只会影响 形参，哨兵位 需要手动 置为NULL void LTDestory(LTNode** pphead) { assert(pphead);// 指针本身不能为 空 assert(*pphead); // 哨兵位 不能为 空 LTNode* pcur = (*pphead)->next; // *pphead = phead 即哨兵位 ;还有记得 加括号 while (pcur != *pphead) { LTNode* next = pcur->next; free(pcur); pcur = next; } // 最后删除 哨兵位 free(*pphead); *pphead = NULL; } 6.2 一级指针版// 双链表的 销毁：一级指针版：哨兵位 需要 手动额外 置为空 void LTDestory(LTNode* phead) { assert(phead);// 哨兵位 不能为 空 LTNode* pcur = (phead)->next; // *pphead = phead 即哨兵位 ;还有记得 加括号 while (pcur != phead) { LTNode* next = pcur->next; free(pcur); pcur = next; } // 最后释放掉 形参的指针：这里不是释放 哨兵位 free(phead); phead = NULL; } 7. 总代码概览 List.h #pragma once #include #include #include // 创建新节点 typedef int LTDataType; typedef struct LTistNode { LTDataType data; struct LTistNode* prev; struct LTistNode* next; }LTNode; // 创建新节点 LTNode* LTCreatNode(LTDataType x); // 初始化：生成哨兵位 LTNode* LTInit(); // 打印函数 void LTPrint(LTNode* phead); // 尾插法 void LTPushBack(LTNode* phead, LTDataType x); // 头插法 void LTPushFront(LTNode* phead, LTDataType x); // 在 pos 之后插入数据 void LTInsert(LTNode* pos, LTDataType x); // 尾删法 void LTPopBack(LTNode* phead); // 头删法 void LTPopFront(LTNode* phead); // 删除 pos 位置节点 void LTErase(LTNode* pos); // 查找 LTNode* LTFind(LTNode* phead, LTDataType x); // 销毁 void LTDestory(LTNode* phead); List.c #include"List.h" // 创建新节点 LTNode* LTCreatNode(LTDataType x) { LTNode* newNode = (LTNode*)malloc(sizeof(LTNode)); if (newNode == NULL) { perror("malloc fail!"); exit(1); } newNode->data = x; newNode->prev = newNode->next = newNode; return newNode; } // 初始化：生成哨兵位 LTNode* LTInit() { LTNode* head = LTCreatNode(-1); return head; } // 打印函数 void LTPrint(LTNode* phead) { assert(phead); LTNode* pcur = phead->next; while (pcur != phead) { printf("%d -> ", pcur->data); pcur = pcur->next; } printf("\n"); } // 尾插法 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); // 创建新节点 LTNode* newNode = LTCreatNode(x); LTNode* ptail = phead->prev; // 三者关系：ptail newNode phead newNode->next = phead; newNode->prev = ptail; ptail->next = newNode; phead->prev = newNode; } // 头插法 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); // 创建新节点 LTNode* newNode = LTCreatNode(x); // 三者关系：phead newNode phead->next (定为Next); LTNode* Next = phead->next; // 这里就是定义了个变量，便于梳理 newNode->next = Next; newNode->prev = phead; Next->prev = newNode; phead->next = newNode; } // 查找 LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* pcur = phead->next; while (pcur != phead) { if (pcur->data == x) return pcur; pcur = pcur->next; } return NULL; } // 在 pos 之后插入数据：头插法实现逻辑一样 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); // 创建新节点 LTNode* newNode = LTCreatNode(x); // 三者关系：pos newNode pso->next (定为Next); LTNode* Next = pos->next; newNode->next = Next; newNode->prev = pos; Next->prev = newNode; pos->next = newNode; } // 尾删法:记得双链表的找尾 不像 单链表需要循环去找尾 void LTPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead);// 链表不能只有 哨兵位 （删除的接口 都要断言这条） // 三者关系：ptail->prev ptail head LTNode* ptail = phead->prev; ptail->prev->next = phead; phead->prev = ptail->prev; free(ptail); ptail = NULL; } // 头删法 void LTPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); // 链表不能只有 哨兵位 （删除的接口 都要断言这条） // 三者关系：phead phead->next phead->next->next(命名为pSecond) LTNode* pFirst = phead->next; // 要被删除的 第一个节点 一定要先保存下来！！ LTNode* pSecond = pFirst->next; pSecond->prev = phead; phead->next = pSecond; free(pFirst); pFirst = NULL; } // 删除 pos 位置节点 void LTErase(LTNode* pos) { assert(pos); // 关系三个节点：pos->prev pos pos->next LTNode* Prev = pos->prev; // pos 的前一个 LTNode* Next = pos->next; // pos 的下一个 Next->prev = Prev; Prev->next = Next; free(pos); pos = NULL; } // 销毁 void LTDestory(LTNode* phead) { assert(phead); // 先全部删除有效节点，后删除头节点 LTNode* pcur = phead->next; while (pcur != phead) { LTNode* Next = pcur->next; free(pcur); pcur = Next; } // 最后释放掉 形参的指针：这里不是释放 哨兵位 free(phead); phead = NULL; } test.c #include"List.h" void LTTest() { // 创建哨兵位 LTNode* head = LTInit(); // 这里直接用 head 代表哨兵位：更直观一点，和 前面讲解用的 plist 是一样的 // 尾插法 LTPushBack(head, 1); LTPushBack(head, 2); LTPushBack(head, 3); LTPushBack(head, 4); // 1 -> 2 -> 3 -> 4 -> printf("测试尾插："); LTPrint(head); // 头插法 LTPushFront(head, 5); LTPushFront(head, 6);// 6 -> 5 -> 1 -> 2 -> 3 -> 4 -> printf("测试头插："); LTPrint(head); // 查找 //LTFind(head, 1); // 在 pos 之后插入数据：头插法实现逻辑一样 LTNode* FindRet1 = LTFind(head, 1); LTInsert(FindRet1, 100); LTNode* FindRet2 = LTFind(head, 2); LTInsert(FindRet2, 200); // 6 -> 5 -> 1 -> 100 -> 2 -> 200 -> 3 -> 4 -> printf("测试pos 之后插入："); LTPrint(head); // 头删法 LTPopFront(head); LTPopFront(head); // 1 -> 100 -> 2 -> 200 -> 3 -> 4 -> printf("测试头删："); LTPrint(head); // 尾删法:记得双链表的找尾 不像 单链表需要循环去找尾 LTPopBack(head); LTPopBack(head); // 1 -> 100 -> 2 -> 200 -> printf("测试尾删："); LTPrint(head); // 删除 pos 位置节点 LTNode* FindRet3 = LTFind(head, 1); LTErase(FindRet3); // 100 -> 2 -> 200 -> printf("测试删除 pos 位置节点："); LTPrint(head); // 双链表的 销毁：这里就不演示销毁了 //LTDesTroy(head); //head= NULL; //哨兵位 需要手动 置为NULL } int main() { LTTest(); return 0; } 三. 顺序表和双向链表的优缺点分析不同点 顺序表 链表（单链表） 存储空间上 物理上⼀定连续 逻辑上连续，但物理上不⼀定连续 随机访问 支持O(1) 不支持：O(N) 任意位置插⼊或者删除元素 可能需要搬移元素，效率低O(N) 只需修改指针指向 插入 动态顺序表，空间不够时需要扩容 没有容量的概念 应用场景 元素高效存储+频繁访问 任意位置插⼊和删除频繁 完。 若上述文章有什么错误，欢迎各位大佬及时指出，我们共同进步！ |
【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |