> 作者简介：დ旧言~，目前大一，现在学习Java，c，c++，Python等
> 座右铭：松树千年终是朽，槿花一日自为荣。
> 望小伙伴们点赞👍收藏✨加关注哟💕💕
🌟前言
前面我们已经学习了顺序表和单链表，顺序表可以存储动态的数据，但是一旦元素过少，而又要开辟空间，这样就造成空间的浪费，而单链表以节点为单位存储，不支持随机访问，只能从头到尾遍历访问，为了解决上面两个问题，人们发现了双链表，把一个一个元素以链子的形式存储，可以存储相互的地址，那双链表如何实现呢，今天咱们就实现一下--《双链表》。
🌙主体
咱们从三个方面实现双链表，动态管理，头插头删尾插尾删，增删查改。
在程序中为了实现双链表，需要创建头文件List.h ，创建源文件Test.c，List.c。
🌠动态管理
💤初始化动态双链表
既然实现双链表，初始化动态的双链表必不可少，从两个方面实现初始化动态的双链表。
1.首先我们在List.h定义动态的双链表，省得我们再定义节点（双链表）。
//定义数据类型 typedef int LTDataType; //定义双链表初始化 typedef struct ListNode { //上一个 struct ListNode* next; //下一个 struct ListNode* prev; LTDataType data; }LTNode;
2.对双链表进行初始化
我们要明白，这里不像单链表一样，形成节点就行，还需要初始化。
💦这里采用malloc开辟空间
💦采用预指令判断空间是否开辟完成（没有开辟空间返回-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; } //形成双链表 LTNode* LTInit() { //使头为0 LTNode* phead = BuyLTNode(0); //构成循环 phead->next = phead; phead->prev = phead; return phead; }
💤释放双链表内存
双链表的内存释放与单链表的内存释放有一定的区别，这里我们分开两类，清理与销毁
清理的代码如下：
//清理 void ListClear(LTNode* phead) { //断言 assert(phead); //清理全部数据，保留头结点 LTNode* cur = phead->next; //循环销毁 while (cur != phead) { LTNode* next = cur->next; free(cur); cur = NULL; cur = next; } }
销毁的代码如下：
//销毁 void ListDestory(LTNode** pphead) { //断言 assert(*pphead); //调用清理（函数） ListClear(*pphead); //释放内存 free(*pphead); *pphead = NULL; }
🌠头插头删尾插尾删
💤打印元素
打印元素就太简单了，直接上代码
//打印数据 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* tail = phead->prev; //给添加的元素创建节点 LTNode* newnode = BuyLTNode(x); //新开辟的元素下一个节点指向尾 newnode->prev = tail; //尾的上一个节点指向新的元素 tail->next = newnode; //新元素的上一个节点指向头 newnode->next = phead; //头的下一节点指向新的元素节点 phead->prev = newnode; //本质上与尾插相似 （双向链表在pos的前面进行插入） //LTInsert(phead, x); }
💤尾删（重点）
双链表重在画图，希望小伙伴们能看得懂。
//尾删 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; // 双向链表删除pos位置的结点(本质上与尾删相似) //LTErase(phead->prev); }
💤头插（重点）
博主在这里采用三种方法，希望大家至少学会一种
//头插 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; //方法二 //初始化 LTNode* newnode = BuyLTNode(x); LTNode* first = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode; //方法三 // 双向链表删除pos位置的结点(本质上就是头插) //LTInsert(phead->next, x); }
💤头删（重点）
双链表会自带梢兵位（这个到后期博主会讲）
//头删（重点） void LTPopFront(LTNode* phead) { //断言 assert(phead); //头指向不能为空 assert(phead->next != phead); //找到梢兵位的节点 LTNode* first = phead->next; //找到头后面一个元素 LTNode* second = first->next; //释放内存 free(first); //梢兵位的节点指向头后面一个元素 phead->next = second; //后面一个元素指向梢兵位的节点 second->prev = phead; //双向链表删除pos位置的结点(本质上和头删一样) //LTErase(phead->next); }
🌠增删查改
💤统计双链表元素个数
这个函数还是比较简单的，注意循环的停止条件。
//统计双链表元素个数 int LTSize(LTNode* phead) { //断言 assert(phead); int size = 0; LTNode* cur = phead->next; while (cur != phead) { ++size; cur = cur->next; } return size; }
💤双向链表在pos的前面进行插入
这里大家就看图理解就行啦
// 双向链表在pos的前面进行插入 void LTInsert(LTNode* pos, LTDataType x) { //断言 assert(pos); LTNode* posPrev = pos->prev; //为插入的元素开辟空间 LTNode* newnode = BuyLTNode(x); posPrev->next = newnode; newnode->prev = posPrev; newnode->next = pos; pos->prev = newnode; }
💤双向链表删除pos位置的结点
这里大家就看图理解就行啦
// 双向链表删除pos位置的结点 void LTErase(LTNode* pos) { //断言 assert(pos); LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; //释放内存 free(pos); posPrev->next = posNext; posNext->prev = posPrev; }
🌙代码总结
🌠主函数
//包含文件 #include"List.h" void TestList1() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPrint(plist); LTPushFront(plist, 10); LTPushBack(plist, 10); LTPrint(plist); } void TestList2() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPrint(plist); LTPopBack(plist); //LTPopFront(plist); LTPrint(plist); //LTPopFront(plist); //LTPopFront(plist); //LTPopFront(plist); //LTPopFront(plist); LTPrint(plist); } //void TestList3() //{ // LTNode* plist = LTInit(); // LTPushBack(plist, 1); // LTPushBack(plist, 2); // LTPushBack(plist, 3); // LTPushBack(plist, 4); // LTPushBack(plist, 5); // LTPrint(plist); // // LTPushFront(plist, 10); // LTPushFront(plist, 20); // LTPushFront(plist, 30); // LTPushFront(plist, 40); // LTPrint(plist); //} // //void TestList4() //{ // LTNode* plist = LTInit(); // LTPushBack(plist, 1); // LTPushBack(plist, 2); // LTPushBack(plist, 3); // LTPushBack(plist, 4); // LTPushBack(plist, 5); // LTPrint(plist); // // LTPopFront(plist); // LTPrint(plist); // // LTPopBack(plist); // LTPrint(plist); //} int main() { TestList1(); return 0; }
🌠List.h头文件
//包含头文件 #include<stdio.h> #include<assert.h> #include<stdlib.h> //定义数据类型 typedef int LTDataType; //定义双链表初始化 typedef struct ListNode { //上一个 struct ListNode* next; //下一个 struct ListNode* prev; 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); //统计双链表元素个数 int LTSize(LTNode* phead); // 双向链表查找（在双链表中不合适） LTNode* LTFind(LTNode* phead, LTDataType x); // 双向链表在pos的前面进行插入 void LTInsert(LTNode* pos, LTDataType x); // 双向链表删除pos位置的结点 void LTErase(LTNode* pos); //清理 void ListClear(LTNode* phead); //销毁 void ListDestory(LTNode** pphead);
🌠List.c源文件
//包含文件 #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() { //使头为0 LTNode* phead = BuyLTNode(0); //构成循环 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* tail = phead->prev; //给添加的元素创建节点 LTNode* newnode = BuyLTNode(x); //新开辟的元素下一个节点指向尾 newnode->prev = tail; //尾的上一个节点指向新的元素 tail->next = newnode; //新元素的上一个节点指向头 newnode->next = phead; //头的下一节点指向新的元素节点 phead->prev = newnode; //本质上与尾插相似 （双向链表在pos的前面进行插入） //LTInsert(phead, x); } //尾删 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; // 双向链表删除pos位置的结点(本质上与尾删相似) //LTErase(phead->prev); } //头插 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; //方法二 //初始化 LTNode* newnode = BuyLTNode(x); LTNode* first = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode; //方法三 // 双向链表删除pos位置的结点(本质上就是头插) //LTInsert(phead->next, x); } //头删（重点） void LTPopFront(LTNode* phead) { //断言 assert(phead); //头指向不能为空 assert(phead->next != phead); //找到梢兵位的节点 LTNode* first = phead->next; //找到头后面一个元素 LTNode* second = first->next; //释放内存 free(first); //梢兵位的节点指向头后面一个元素 phead->next = second; //后面一个元素指向梢兵位的节点 second->prev = phead; //双向链表删除pos位置的结点(本质上和头删一样) //LTErase(phead->next); } //统计双链表元素个数 int LTSize(LTNode* phead) { //断言 assert(phead); int size = 0; LTNode* cur = phead->next; while (cur != phead) { ++size; cur = cur->next; } return size; } // 双向链表在pos的前面进行插入 void LTInsert(LTNode* pos, LTDataType x) { //断言 assert(pos); LTNode* posPrev = pos->prev; //为插入的元素开辟空间 LTNode* newnode = BuyLTNode(x); posPrev->next = newnode; newnode->prev = posPrev; newnode->next = pos; pos->prev = 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 ListClear(LTNode* phead) { //断言 assert(phead); //清理全部数据，保留头结点 LTNode* cur = phead->next; //循环销毁 while (cur != phead) { LTNode* next = cur->next; free(cur); cur = NULL; cur = next; } } //销毁 void ListDestory(LTNode** pphead) { //断言 assert(*pphead); //调用清理（函数） ListClear(*pphead); //释放内存 free(*pphead); *pphead = NULL; }
🌟结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小说手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
