一.前言
如果有友友看了我上一篇文章：数据结构——单链表，那么本篇的双链表会让你感到非常的安逸~无压力学会。码字不易，希望大家多多支持我呀！（三连＋关注，你是我滴神！）
二.双链表的基本结构
两两组合下链表一共有八种结构：而我们本文的重点就是带头双向循环链表。
虽然有这么多的链表结构，但我们在实际中用得最多的还是以下两种：
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 带头双向循环链表：结构最复杂，一般用在单独存储数据结构。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们用代码实现了就知道了。
三.准备阶段
3.1 空间函数
//空间函数 LTNode* BuyLTNode(LTDataType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->data = x; node->next = NULL; node->prev = NULL; return node; }
3.2 初始化函数
这里得用到二级指针了，要想改变plist（LTNode*)类型的指针，初始化函数就得用到（LTNode**）去接收，但我们可以换个思路，既然我们在不用到二级指针的情况下phead只是plist的临时拷贝，那么我们也可以让初始化函数的返回类型发生变化，这样也可以达到改变plist的作用。把初始化函数赋值给plist即可。
//初始化函数 LTNode* LTInit() { //创造一个新节点，该节点是双向循环节点 LTNode*phead = BuyLTNode(-1); phead->next = phead; phead->prev = phead; return phead; //最后只要把这个我们人工初始化好的节点赋值给plist就好了 }
3.3 打印函数
cur指向哨兵位phead的后面一位节点，这样方便打印。
//打印函数 void LTPrint(LTNode* phead) { assert(phead); printf("phead<=>"); LTNode* cur = phead->next; while (cur != phead) { printf("%d<=>", cur->data); cur = cur->next; } printf("\n"); }
四.链表的实现
先来个开胃小菜：
4.1 尾插函数（可以让我们直观认识到该结构的妙用）
不同于单链表（有节点要找尾，没节点插入第一个），在双链表中只需要把4个指针都标明好就行，方便又易懂，不用担心是否为空链表。最后出了作用域tail和newnode就会销毁，而新节点是由malloc在堆上申请的，所以还在。
另外还有一点，这样不需要用到二级指针，因为我们有带头节点，这样phead是永远指向它的。
void LTPushBack(LTNode* phead, LTDataType x) { assert(phead);//这里肯定要断言一下的，因为就算是初始化也会有作为头部的哨兵位。 LTNode* newnode = BuyLTNode(x); LTNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
4.2 尾删函数
要实现尾插我们得注意两点：
- 找到指向尾节点前一个节点的指针
- 单链表为空时不能再进行尾删
//尾删函数 void LTPopBack(LTNode* phead) { assert(phead);//避免phead初始化没完成而导致出错 assert(phead->next!=phead);//当删除到没有节点时，不能再继续尾删 LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; free(tail); tailPrev->next = phead; phead->prev = tailPrev; }
大家应该逐渐发现双链表的优势所在了吧，基本上不用像单链表一样考虑到特殊情况然后去修改代码，单链表需要条件判断的问题，双链表都可以应对~
4.3 头插函数
头插也不需要用到二级指针，因为我们要改变的并非phead本身（phead只需要指向哨兵就行），而是改变phead指向的结构体（改变哨兵节点的指向）。
注意别这么改，虽然最后可以通过各种前驱指针找到d1，但代价太大了。
所以我们需要标记首节点（d1)的指向，让每次头插时都能找到原先作为头节点的指针。这里需要注意的是有先后顺序，先让新节点与首节点d1(phead->next指向)相互链接再让它与哨兵节点链接，这样可以避免d1节点地址的丢失。
//头插函数 void PushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyLTNode(x); newnode->next = phead->next; phead->next->prev = newnode; phead->next = newnode; newnode->prev = phead; }
测试一下：
void TestList2() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPushFront(plist, 10); LTPrint(plist); }
但我建议换另一种写法，上面这种写法容易出错。
定义好一个first的指针，这样顺序怎么搞都不会玩脱。
//头插函数 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyLTNode(x); LTNode* first = phead->next; first->prev = newnode; newnode->next = first; phead->next = newnode; newnode->prev = newnode; }
4.4 头删函数
上图是基本思路，我们定义指针的时候不要吝啬，出手阔气一点系统不会在意这点内存滴~
就算是只剩下一个节点，照样拿捏~
测试一下：
void TestList3() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPopFront(plist); LTPrint(plist); }
//头删函数 void LTPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* first = phead->next; LTNode* second = first->next; phead->next = second; second->prev = phead; free(first); }
4.5 pos之前插入x函数
简简单单~
//pos之前插入x void LTInsert(LTNode* phead,LTNode* pos, LTDataType x) { assert(phead); LTNode* newnode = BuyLTNode(x); LTNode* posPrev = pos->prev; newnode->prev = posPrev; newnode->next = pos; pos->prev = newnode; posPrev->next = newnode; }
其实我们可以发现写好了Insert函数再搭配的Find函数（更直观）就相当于写好了头插尾插了~
4.6 在pos位置删除函数
//删除pos位置的值 void LTErase(LTNode* pos) { assert(pos); LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; free(pos); posPrev->next = posNext; posNext->prev = posPrev; }
该函数也可以复用，起到头删，尾删的作用~
4.7 查找函数
//寻找函数 LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur!=phead) { if (cur->data == x) { return cur; } else { cur = cur->next; } } return NULL; }
可以与Insert函数搭配使用~
void TestList4() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPopFront(plist); LTPrint(plist); int x = 0; scanf("%d", &x); LTNode* pos = LTFind(plist, x); if (pos) { LTInsert(plist, pos, 6); } LTPrint(plist); }
4.8 销毁函数
//销毁函数 void LTDestort(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); }
不需要置空 ，里面的形参不会影响到外面的实参。既然里面不用置空，那我们就让外面用的置空就行了。
void TestList4() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPopFront(plist); LTPrint(plist); int x = 0; scanf("%d", &x); LTNode* pos = LTFind(plist, x); if (pos) { LTInsert(plist, pos, 6); } LTPrint(plist); LTDestory(plist); plist = NULL; }
五.全部代码
//List.h #pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int LTDataType; typedef struct ListNode { struct ListNode* prev; struct ListNode* next; LTDataType data; }LTNode; //空间函数 LTNode* BuyLTNode(LTDataType x); //初始化函数、 LTNode* LTInit(); //打印函数 void LTPrint(LTNode* phead); //尾插函数 void LTPushBack(LTNode* phead, LTDataType x); //尾删函数 void LTPopBack(LTNode* phead); //头插函数 void LTPushFront(LTNode* phead, LTDataType x); //头删函数 void LTPopFront(LTNode* phead); //寻找函数 LTNode* LTFind(LTNode* phead, LTDataType x); //pos之前插入x void LTInsert(LTNode* phead,LTNode* pos, LTDataType x); //删除pos位置的值 void LTErase(LTNode* pos); //销毁函数 void LTDestort(LTNode* phead);
————————————————————————————————————————
//List.c #define _CRT_SECURE_NO_WARNINGS 1 #include "List.h" //空间函数 LTNode* BuyLTNode(LTDataType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->data = x; node->next = NULL; node->prev = NULL; return node; } //初始化函数 LTNode* LTInit() { LTNode* phead = BuyLTNode(-1); phead->next = phead; phead->prev = phead; return phead; } //打印函数 void LTPrint(LTNode* phead) { assert(phead); printf("phead<=>"); LTNode* cur = phead->next; while (cur != phead) { printf("%d<=>", cur->data); cur = cur->next; } printf("\n"); } //尾插函数 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead);//这里肯定要断言一下的，因为就算是初始化也会有作为头部的哨兵位。 LTNode* newnode = BuyLTNode(x); LTNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; } //尾删函数 void LTPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; free(tail); tailPrev->next = phead; phead->prev = tailPrev; } 头插函数 //void LTPushFront(LTNode* phead, LTDataType x) //{ // assert(phead); // LTNode* newnode = BuyLTNode(x); // newnode->next = phead->next; // phead->next->prev = newnode; // phead->next = newnode; // newnode->prev = phead; //} //头插函数 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyLTNode(x); LTNode* first = phead->next; first->prev = newnode; newnode->next = first; phead->next = newnode; newnode->prev = newnode; } //头删函数 void LTPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* first = phead->next; LTNode* second = first->next; phead->next = second; second->prev = phead; free(first); } //寻找函数 LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur!=phead) { if (cur->data == x) { return cur; } else { cur = cur->next; } } return NULL; } //pos之前插入x void LTInsert(LTNode* phead,LTNode* pos, LTDataType x) { assert(phead); LTNode* newnode = BuyLTNode(x); LTNode* posPrev = pos->prev; newnode->prev = posPrev; newnode->next = pos; pos->prev = newnode; posPrev->next = newnode; } //删除pos位置的值 void LTErase(LTNode* pos) { assert(pos); LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; free(pos); posPrev->next = posNext; posNext->prev = posPrev; } //销毁函数 void LTDestort(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); }
————————————————————————————————————————
//Test.c #define _CRT_SECURE_NO_WARNINGS 1 #include "List.h" void TestList1() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist); } void TestList2() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPushFront(plist, 10); LTPrint(plist); } void TestList3() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPopFront(plist); LTPrint(plist); } void TestList4() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPopFront(plist); LTPrint(plist); int x = 0; scanf("%d", &x); LTNode* pos = LTFind(plist, x); if (pos) { LTInsert(plist, pos, 6); } LTPrint(plist); } int main() { //TestList1(); //TestList2(); //TestList3(); TestList4(); return 0; }
六.结语
双链表是不是非常轻松呢~不像我们学单链表那时候草木皆兵，啥都要判断一下，双链表突出的就是一个结构稳定，安逸的很~最后感谢大家的观看，友友们能够学习到新的知识是额滴荣幸，期待我们下次相见~
