#yyds干货盘点#算法开启小码农双链表血脉 _链表

业无高卑志当坚，男儿有求安得闲？这篇文章主要讲述#yyds干货盘点#算法开启小码农双链表血脉相关的知识，希望能为你提供帮助。
双链表双链表结构图

文章图片

双链表节点

typedef int LTDataType; //C++中的双链表是用list表示的typedef struct ListNodeLTDataType data; struct ListNode* next; struct ListNode* prev; LTNode;

双链表初始化函数ListInit

文章图片

//双链表初始化函数 LTNode* ListNodeInit()//创建一个双链表哨兵位头结点不存储有效数据循环 LTNode* phead = (LTNode*)malloc(sizeof(LTNode)); phead-> next = phead; phead-> prev = phead; return phead;

文章图片

双链表尾插函数ListPushBack

文章图片

//双链表尾插函数 void ListNodePushBack(LTNode* phead, LTDataType x)assert(phead); //实际上phead永远也不可能是NULL LTNode* tail = phead-> prev; LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); newnode-> data = https://www.songbingjia.com/android/x; tail-> next = newnode; newnode-> prev = tail; newnode-> next = phead; phead-> prev = newnode;

双链表打印函数ListPrint

文章图片

//双链表打印函数 void ListPrint(LTNode* phead)assert(phead); LTNode* cur = phead-> next; while (cur != phead)printf("%d ", cur-> data); cur = cur-> next; printf("\\n");

双链表尾删函数ListPopBack

文章图片

//双链表尾删函数 void ListPopBack(LTNode* phead)assert(phead & & phead-> next != phead); LTNode* tail = phead-> prev; LTNode* cur = phead-> prev; tail = tail-> prev; tail-> next = phead; phead-> prev = tail; free(cur);

双链表头插函数ListPushFront

文章图片

//双链表头插函数 void ListPushFront(LTNode* phead, LTDataType x)assert(phead); LTNode* next = phead-> next; //在next和phead中间插一个节点 /*LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); newnode-> data = https://www.songbingjia.com/android/x; */ LTNode* newnode = BuyListNode(x); newnode-> next = next; next-> prev = newnode; phead-> next = newnode;

==既然我们头插尾插都遇到了添加节点，所以我们把添加节点的部分抽离出来重新封装一下==
获得双链表节点函数BuyListNode

文章图片

//获得双链表节点函数 LTNode* BuyListNode(LTDataType x)LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); newnode-> data = https://www.songbingjia.com/android/x; newnode-> next = NULL; newnode-> prev = NULL; return newnode;

双链表头删函数ListPopFront

文章图片

//双链表头删函数 void ListPopFront(LTNode* phead)assert(phead & & phead-> next != phead); LTNode* next = phead-> next; phead-> next = next-> next; next-> next-> prev = phead; free(next);

双链表查找函数ListFind
==这个一般是和插入，删除配合使用==

//双链表查找函数 LTNode* ListFind(LTNode* phead, LTDataType x)assert(phead); LTNode* cur = phead-> next; while (cur != phead)if (cur-> data =https://www.songbingjia.com/android/= x) return cur; cur = cur-> next; return NULL;

双链表插入函数ListInsert（pos之前插入因为c++中就是之前插入的）

文章图片

//双链表插入函数 void ListInsert(LTNode* pos, LTDataType x)assert(pos); LTNode* newnode = BuyListNode(x); LTNode* posprev = pos-> prev; newnode-> data = https://www.songbingjia.com/android/x; pos-> prev = newnode; newnode-> next = pos; newnode-> prev = posprev; posprev-> next = newnode;

双链表删除函数ListErase（删除pos）
【#yyds干货盘点#算法开启小码农双链表血脉】

文章图片

//双链表删除函数 void ListErase(LTNode* pos)assert(pos & & pos-> next); LTNode* posnext = pos-> next; LTNode* posprev = pos-> prev; posnext-> prev = posprev; posprev-> next = posnext; free(pos);

双链表销毁函数ListDestroy(实际上我在这里写报错了，前面一个函数有bug，但是找到了)

//双链表销毁函数 void ListDestroy(LTNode* phead)assert(phead); LTNode* tail = phead-> prev; while (tail != phead)LTNode* tailprev = tail-> next; free(tail); tail = tailprev; free(phead); phead = NULL;

代码 DoubleList.h

#pragma once #include< stdio.h> #include< assert.h> #include< stdlib.h> typedef int LTDataType; //C++中的双链表是用list表示的typedef struct ListNodeLTDataType data; struct ListNode* next; struct ListNode* prev; LTNode; //双链表初始化函数 extern LTNode* ListInit(); //双链表销毁函数 extern void ListDestroy(LTNode* phead); //双链表尾插函数 extern void ListPushBack(LTNode* phead, LTDataType x); //双链表打印函数 extern void ListPrint(LTNode* phead); //双链表尾删函数 extern void ListPopBack(LTNode* phead); //获得双链表节点函数 extern LTNode* BuyListNode(LTDataType x); //双链表头插函数 extern void ListPushFront(LTNode* phead, LTDataType x); //双链表头删函数 extern void ListPopFront(LTNode* phead); //双链表查找函数 extern LTNode* ListFind(LTNode* phead, LTDataType x); //双链表插入函数 extern void ListInsert(LTNode* pos, LTDataType x); //双链表删除函数 extern void ListErase(LTNode* pos);

DoubleList.c

#define _CRT_SECURE_NO_WARNINGS 1#include "DoubleList.h"//双链表初始化函数 LTNode* ListInit()//创建一个双链表哨兵位头结点不存储有效数据循环 LTNode* phead = (LTNode*)malloc(sizeof(LTNode)); phead-> next = phead; phead-> prev = phead; return phead; //获得双链表节点函数 LTNode* BuyListNode(LTDataType x)LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); newnode-> data = https://www.songbingjia.com/android/x; newnode-> next = NULL; newnode-> prev = NULL; return newnode; //双链表尾插函数 void ListPushBack(LTNode* phead, LTDataType x)assert(phead); //实际上phead永远也不可能是NULL LTNode* tail = phead-> prev; /*LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); newnode-> data = x; */ LTNode* newnode = BuyListNode(x); tail-> next = newnode; newnode-> prev = tail; newnode-> next = phead; phead-> prev = newnode; //双链表打印函数 void ListPrint(LTNode* phead)assert(phead); LTNode* cur = phead-> next; while (cur != phead)printf("%d ", cur-> data); cur = cur-> next; printf("\\n"); //双链表尾删函数 void ListPopBack(LTNode* phead)assert(phead & & phead-> next != phead); LTNode* tail = phead-> prev; LTNode* cur = phead-> prev; tail = tail-> prev; tail-> next = phead; phead-> prev = tail; free(cur); //双链表头插函数 void ListPushFront(LTNode* phead, LTDataType x)assert(phead); LTNode* next = phead-> next; //在next和phead中间插一个节点 /*LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); newnode-> data = https://www.songbingjia.com/android/x; */ LTNode* newnode = BuyListNode(x); newnode-> next = next; next-> prev = newnode; phead-> next = newnode; //双链表头删函数 void ListPopFront(LTNode* phead)assert(phead & & phead-> next != phead); LTNode* next = phead-> next; phead-> next = next-> next; next-> next-> prev = phead; free(next); //双链表查找函数 LTNode* ListFind(LTNode* phead, LTDataType x)assert(phead); LTNode* cur = phead-> next; while (cur != phead)if (cur-> data == x) return cur; cur = cur-> next; return NULL; //双链表插入函数 void ListInsert(LTNode* pos, LTDataType x)assert(pos); LTNode* newnode = BuyListNode(x); LTNode* posprev = pos-> prev; newnode-> data = x; pos-> prev = newnode; newnode-> next = pos; newnode-> prev = posprev; posprev-> next = newnode; //双链表删除函数 void ListErase(LTNode* pos)assert(pos & & pos-> next); LTNode* posnext = pos-> next; LTNode* posprev = pos-> prev; posnext-> prev = posprev; posprev-> next = posnext; free(pos); //双链表销毁函数 void ListDestroy(LTNode* phead)assert(phead); LTNode* tail = phead-> prev; while (tail != phead)LTNode* tailprev = tail-> next; free(tail); tail = tailprev; free(phead); phead = NULL;

test.c

#define _CRT_SECURE_NO_WARNINGS 1 #include "DoubleList.h" void TestList1()LTNode* plist = ListInit(); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPrint(plist); ListPopBack(plist); ListPopBack(plist); ListPopBack(plist); ListPopBack(plist); ListPrint(plist); ListPushFront(plist, 10); ListPushFront(plist, 20); ListPushFront(plist, 30); ListPrint(plist); LTNode* p1 = ListFind(plist, 10); if (p1)ListInsert(p1, 100); ListPrint(plist); LTNode* p2 = ListFind(plist, 20); if (p2)ListErase(p2); ListPrint(plist); ListDestroy(plist); plist = NULL; int main()TestList1(); return 0;