双向链表的概念
双向链表的全称是带头双向循环链表，它可以在任意位置进行时间复杂度为0(1)的插入删除数据，并且可以按照需求申请释放和开辟空间，但他也有复杂的实现方式，这是它如此好用的代价.
节点的定义
对于双向链表的节点构造和单链表有点小区别，它有结点值，前驱指针，后继指针，来看节点的定义：
//结点定义 LTNode* LTBuyNode(LTDatatype x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = newnode->prev = newnode; return newnode; }
初始时结点的前驱和后继指针指向自己，然后返回结点的指针.
双向链表的初始化
由于双向链表带哨兵位，所以初始化要创建一个哨兵位，哨兵位的值是-1，因为他的值不需要修改，所以我们让哨兵位初始化为-1，(当然其他值也可以，因为我们不需要哨兵位的值，这个传什么数都不影响）然后返回哨兵位的结点.
//初始化 LTNode* LTInit() { LTNode* phead = LTBuyNode(-1); return phead; }
头插
代码注释很详尽.
//头插 void LTPushFront(LTNode* phead, LTDatatype x) { assert(phead); LTNode* newnode = LTBuyNode(x); newnode->next = phead->next;//改变插入结点的后继指向 newnode->prev = phead;//改变插入节点的前驱指向 phead->next->prev = newnode;//改变原来哨兵位的下一个节点的前驱指向 phead->next = newnode; //改变头结点的后继指向 }
如果我们把倒数后两行的代码换一下位置，会发生什么呢？
phead->next = newnode; phead->next->prev = newnode;
我们先改变头节点的后继指向，但是我们原来头节点的后继指向就找不到了，这个地方就出现问题了，原来插入一个节点需要改变四个指针的指向，但是我们只改变了三个指针，第四个指针找不到了，所以指针的改变顺序也是要注意的，确保当前指针指向的改变不会影响其他指针.
尾插
尾插的顺序也要注意.
//尾插 void LTPushBack(LTNode* phead, LTDatatype x) { assert(phead); LTNode* newnode = LTBuyNode(x); newnode->next = phead; //改变插入结点的后继指向 newnode->prev = phead->prev; //改变插入节点的前驱指向 phead->prev->next = newnode; //改变原来尾节点的后继指向 phead->prev = newnode; //改变头结点的前驱指向 }
头删
头删先找到要删除的头节点，然后通过该头节点找到新的头节点，然后改变新头结点的前驱和后继指针的指向，最后free要删除的头节点，记得free后置为空哟.
//头删 void LTPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* del = phead->next;//找到头节点 LTNode* next = del->next;//找到头结点的下一个，作为新的头结点 next->prev = phead;//将新头结点的前驱指向哨兵位 phead->next = next;//将哨兵位的后继指向新的头结点 free(del); del = NULL;//释放掉del后记得值空，当然在这个地方del不置空也不影响 //但是还养成好习惯 }
尾删
//尾删 void LTPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* del = phead->prev;//找到尾节点 LTNode* prev = del->prev;//找到尾结点的前一个，作为新的尾结点 prev->next = phead;//将新尾结点的后继指向哨兵位 phead->prev = prev;//将哨兵位的前驱指向新的尾结点 free(del); del = NULL; }
指定位置插入
//在Pos位置之后插入数据 void LTInsert(LTNode* pos, LTDatatype x) { assert(pos); LTNode* newnode = LTBuyNode(x); newnode->next = pos->next; newnode->prev = pos; pos->next->prev = newnode; pos->next = newnode; }
指定位置删除
改变pos下一个结点的前驱指针，然后改变pos上一个结点的后继指针
//删除pos位置的数据 void LTErase(LTNode* pos) { assert(pos); pos->next->prev = pos->prev; pos->prev->next = pos->next; free(pos); pos = NULL; }
查找
查找链表不能为空呀，记得要断言
//查找 LTNode* LTFind(LTNode* phead, LTDatatype x) { assert(phead); assert(phead->next != phead); LTNode* pcur = phead->next; while (pcur != phead) { if (pcur->data == x) return pcur; pcur = pcur->next; } return NULL; }
链表打印
//打印 void LTPrint(LTNode* phead) { assert(phead); LTNode* pcur = phead->next; while (pcur != phead) { printf("%d ", pcur->data); pcur = pcur->next; } printf("\n"); }
销毁链表
//销毁链表 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; }
总结
双向链表的增删查改比较复杂，要改变四个指针的指向，注意指针改变的先后顺序，代码注释很清楚了，可以配合画图理解，注意细节，理清思路，废话（有bug不要慌，听首歌慢慢找，最重要的是认真仔细，想清楚自己每写一行代码的意思）
一起加油吧！！！
附完整代码
//List.h #pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int LTDatatype; typedef struct ListNode { LTDatatype data; struct ListNode* next; struct ListNode* prev; }LTNode; //结点定义 LTNode* LTBuyNode(LTDatatype x); //初始化 LTNode* LTInit(); //尾插 void LTPushBack(LTNode* phead, LTDatatype x); //头插 void LTPushFront(LTNode* phead, LTDatatype x); //尾删 void LTPopBack(LTNode* phead); //头删 void LTPopFront(LTNode* phead); //在Pos位置之后插入数据 void LTInsert(LTNode* pos, LTDatatype x); //删除pos位置的数据 void LTErase(LTNode* pos); //打印 void LTPrint(LTNode* phead); //查找 LTNode* LTFind(LTNode* phead, LTDatatype x); //销毁链表 void LTDestory(LTNode* phead);
//List.c #include"List.h" //结点定义 LTNode* LTBuyNode(LTDatatype x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = newnode->prev = newnode; return newnode; } //初始化 LTNode* LTInit() { LTNode* phead = LTBuyNode(-1); return phead; } //尾插需要四步 void LTPushBack(LTNode* phead, LTDatatype x) { assert(phead); LTNode* newnode = LTBuyNode(x); newnode->next = phead; //改变插入结点的后继指向 newnode->prev = phead->prev; //改变插入节点的前驱指向 phead->prev->next = newnode; //改变原来尾节点的后继指向 phead->prev = newnode; //改变头结点的前驱指向 } //头插需要四步 void LTPushFront(LTNode* phead, LTDatatype x) { assert(phead); LTNode* newnode = LTBuyNode(x); newnode->next = phead->next;//改变插入结点的后继指向 newnode->prev = phead;//改变插入节点的前驱指向 phead->next->prev = newnode;//改变原来哨兵位的下一个节点的前驱指向 phead->next = newnode; //改变头结点的后继指向 } //尾删 void LTPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* del = phead->prev;//找到尾节点 LTNode* prev = del->prev;//找到尾结点的前一个，作为新的尾结点 prev->next = phead;//将新尾结点的后继指向哨兵位 phead->prev = prev;//将哨兵位的前驱指向新的尾结点 free(del); del = NULL; } //头删 void LTPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* del = phead->next;//找到头节点 LTNode* next = del->next;//找到头结点的下一个，作为新的头结点 next->prev = phead;//将新头结点的前驱指向哨兵位 phead->next = next;//将哨兵位的后继指向新的头结点 free(del); del = NULL; } //在Pos位置之后插入数据 void LTInsert(LTNode* pos, LTDatatype x) { assert(pos); LTNode* newnode = LTBuyNode(x); newnode->next = pos->next; newnode->prev = pos; pos->next->prev = newnode; pos->next = newnode; } //删除pos位置的数据 void LTErase(LTNode* pos) { assert(pos); pos->next->prev = pos->prev; pos->prev->next = pos->next; free(pos); pos = NULL; } //打印 void LTPrint(LTNode* phead) { assert(phead); LTNode* pcur = phead->next; while (pcur != phead) { printf("%d ", pcur->data); pcur = pcur->next; } printf("\n"); } //查找 LTNode* LTFind(LTNode* phead, LTDatatype x) { assert(phead); assert(phead->next != phead); LTNode* pcur = phead->next; while (pcur != phead) { if (pcur->data == x) return pcur; pcur = pcur->next; } return 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" int main() { LTNode* p1= LTInit(); //LTInit(&p1); LTPushBack(p1, 1); LTPushBack(p1, 2); LTPushBack(p1, 3); LTPushBack(p1, 4); LTPushBack(p1, 5); LTPushFront(p1, 100); LTPushFront(p1, 200); LTPushFront(p1, 300); LTPushFront(p1, 400); LTPushFront(p1, 500); LTNode* plist = LTFind(p1, 300); LTInsert(plist,600); LTErase(plist); /*LTPopBack(p1); LTPopBack(p1); LTPopBack(p1); LTPopFront(p1); LTPopFront(p1); LTPopFront(p1);*/ LTPrint(p1); LTDestory(p1); return 0; }
