数据结构之双向链表

1.双向链表的概念

        双向链表是对单链表的一种改进数据结构。在单链表里，每个节点仅包含一个指向后继节点的指针域；而双向链表在此基础上，为每个节点额外设置了一个指向前驱节点的指针域。

        双向链表和单链表的显著区别在于节点的访问方式。在单链表中，若要访问某个节点的前驱节点，只能从链表的头节点开始，按照顺序依次遍历，直至找到目标节点的前驱，过程相对繁琐。但双向链表则不同，它的每个节点都能凭借自身的指针域，直接、便捷地访问其前驱节点和后继节点，无需从头节点开始按顺序逐个查找，大大提高了数据访问的灵活性和效率。

2.双向链表的结构与特点

双向链表的每个节点由三个部分组成

  (1)存储当前节点的数据---data

  (2)前驱指针---prev

  (3)后驱指针---next

带头双向循环链表具有以下显著特点：

头结点（哨兵位）的存在

        该链表设置了头结点作为哨兵位。这个特殊的头结点不存储实际的数据，却在链表的操作中扮演着至关重要的角色。它就像是链表的“守护者”，使得链表无论在何种操作下，都能保持一种稳定的结构。

链表永不为空

        得益于头结点的存在，带头双向循环链表在逻辑上永远不会为空。即使链表中没有存储有效数据的节点，头结点依然存在，保证了链表结构的完整性。这一特性避免了在处理空链表时复杂的边界条件判断，简化了代码逻辑，降低了编程难度。

无需二级指针

        在对链表进行插入、删除等操作时，通常不需要使用二级指针。由于头结点始终存在，我们可以直接通过头结点来操作链表，避免了使用二级指针传递地址的复杂性。这不仅让代码更加简洁易懂，还减少了因指针操作不当而引发错误的可能性。

节点访问的高效性

        在带头双向循环链表中，任意一个节点都可以方便地找到它的上一个节点和下一个节点。每个节点不仅有指向下一个节点的指针，还有指向前一个节点的指针，并且链表首尾相连形成循环。这种结构使得我们可以从任意一个节点出发，沿着指针的方向快速访问到其相邻节点，大大提高了数据的访问效率和操作的灵活性。

整体结构：

//定义双向链表中节点的结构typedef int LTDataType;typedef struct ListNode{struct ListNode* next; //后继节点struct ListNode* prev; //前驱节点LTDataType data; //当前节点的数据}LTNode;

3.双链表的总接口

//初始化链表LTNode* LTInit();//打印链表void LTPrint(LTNode* phead);//判断是否为空bool LTEmpty(LTNode* phead);//尾插void LTPushBack(LTNode* phead, LTDataType x);//头插void LTPushFront(LTNode* phead, LTDataType x);//尾删void LTPopBack(LTNode* phead);//头删void LTPopFront(LTNode* phead);//查找LTNode* LTFind(LTNode* phead, LTDataType x);// 在pos之前插入void LTInsert(LTNode* pos, LTDataType x);//在pos之后插入void LTInsertAfter(LTNode* pos,LTDataType x);// 删除pos位置的值void LTErase(LTNode* pos);//销毁void LTDestroy(LTNode* phead);

3.1初始化链表

3.1.1创建节点

当我们需要插入元素是，只需要创建节点，然后直接把值存入，两个指针置为空，返回该节点的地址就可

//创建节点LTNode* BuyLTNode(LTDataType x){LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//判断节点创建是否成功，避免野指针的出现if (newnode == NULL){perror(\"malloc fail\");return NULL;}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;}

3.1.2初始化链表

        我们可以采用一种灵活高效的策略。首先，创建一个哨兵位节点。这个哨兵位节点就如同一个稳固的“基石”，我们让它自成一个循环链表，形成一个初始的、稳定的结构框架。

        当后续有数据添加需求时，我们可采用尾插法来添加新数据。尾插法就像是在已有的队伍末尾依次加入新成员，操作简单且有序。借助这种方式，数据的添加变得极为自由，只要有需要，随时都能进行添加操作，无需提前规划复杂的添加流程。

        更为重要的是，采用这种方式无需我们为存储容量问题而烦恼。不像传统的一些存储方式需要频繁地进行扩容操作，过程繁琐且可能会造成资源的浪费。在这里，我们只需要根据实际的数据量不断开辟新的内存空间，真正做到了“用多少，开多少”，极大地提高了内存资源的使用效率，避免了不必要的资源闲置与浪费。

//初始化链表LTNode* LTInit(){//创建一个哨兵位LTNode*phead = BuyLTNode(-1);phead->next = phead;phead->prev = phead;return phead;}

3.2打印链表

我们从哨兵位的下一位开始打印，直到cur的下一位是phead打印完成

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

3.3尾插

我们只需要将tail->next连接到newnode上，再将newnode->prev连接到tail上，最后phead的prev和newnode的next连接即可

//尾插void LTPushBack(LTNode* phead, LTDataType x){assert(phead);LTNode* tail = phead->prev;LTNode* newnode = BuyLTNode(x);tail->next = newnode;newnode->prev = tail;phead->prev = newnode;newnode->next = phead;}

3.4头插

头插就是将哨兵位和头一个节点断开，再进行和尾插类似的工作，特别注意我们要先保存好数据再进行相关操作，避免数据丢失。

//头插void LTPushFront(LTNode* phead, LTDataType x){assert(phead);LTNode* first = phead->next;LTNode* newnode = BuyLTNode(x);phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;}

3.5尾删

尾删我们要先找到tail的前一个节点tailprev,然后将尾节点直接释放掉即可。

特别注意：哨兵位不能删除

//尾删void LTPopBack(LTNode* phead){assert(phead);assert(phead->next);LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;free(tail);phead->prev = tailprev;tailprev->prev = phead;}

3.6头删

头删就是将哨兵位的后一位删除，同样哨兵位不能为空

//头删void LTPopFront(LTNode* phead){assert(phead);assert(phead->next);LTNode* first = phead->next;LTNode* firstnext = first->next;free(first);first = NULL;phead->next = firstnext;firstnext->prev = phead;}

3.7判断是否为空

判断是否为空这里我们可以加上这个函数，如果phead下一个等于phead，说明链表为空只剩下哨兵位自己， 那么此时我们就不能继续删除了，这里我们可以用这个函数直接替换掉上面的断言

bool LTEmpty(LTNode* phead){assert(phead);return phead->next == phead;}

3.8查找

因为在循环链表中没有NULL,我们在查找过程中没有添加限制条件的话链表会无限循环，那么我们用phead作为条件，读取数据从第一位开始读，当读到phead表示已经把所有数据都遍历了一遍

//查找LTNode* LTFind(LTNode* phead, LTDataType x){assert(phead);LTNode* cur = phead->next;while (cur->next != phead){if (cur == x)return cur;cur=cur->next;}return NULL;}

3.9在pos插入数据（之前，之后，pos位）

我们通过pos->prev找到posprev的位置，然后将newnode与pos和1posprev联系起来即可

// 在pos之前插入void LTInsert(LTNode* pos, LTDataType x){assert(pos);LTNode* posprev = pos->prev;LTNode* newnode = BuyLTNode(x);newnode->prev = posprev;posprev->next = newnode;newnode->next = pos;pos->prev = newnode;}

同理可得其他两种情况

// 在pos之后插入void LTInsert(LTNode* pos, LTDataType x){assert(pos);LTNode* posnext = pos->next;LTNode* newnode = BuyLTNode(x);newnode->prev = pos;pos->next = newnode;newnode->next = posnext;posnext->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;}

3.10销毁

我们将链表的所有数值的清空

//销毁void LTDestroy(LTNode* phead){assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);}

4.总结

至此，我们不难发现，无论是头插、头删操作，尾插、尾删操作，还是在指定的 `pos` 位置进行的相关操作，它们背后所遵循的原理实际上是相通的。本质上，头插、头删以及尾插、尾删操作都可以看作是 `pos` 位置操作的特殊情形。

以头插为例，它其实就是在链表头部这个特定的 `pos` 位置插入元素；头删则是删除链表头部这个 `pos` 位置的元素。同理，尾插是在链表尾部的 `pos` 位置插入元素，尾删则是删除尾部 `pos` 位置的元素。

基于这样的发现，我们完全有能力对现有的代码进行简化。通过将这些看似不同的操作归纳统一，提取出它们的共性部分，我们能够让代码的结构更加简洁清晰，减少冗余代码，提高代码的可维护性和可读性。如此一来，后续无论是对代码进行功能扩展还是故障排查，都会变得更加轻松高效。

void LTPushBack(LTNode* phead, LTDataType x){assert(phead); LTInsert(phead, x);} void LTPushFront(LTNode* phead, LTDataType x){LTInsert(phead->next, x);} void LTPopBack(LTNode* phead){assert(phead);assert(!LTEmpty(phead));LTErase(phead->prev);} void LTPopFront(LTNode* phead){assert(phead);assert(!LTEmpty(phead)); LTErase(phead->next); }

5.完整代码

//List.h#pragma once#include#include#include#include//定义双向链表中节点的结构typedef int LTDataType;typedef struct ListNode{struct ListNode* next; //后继节点struct ListNode* prev; //前驱节点LTDataType data; //当前节点的数据}LTNode;//初始化链表LTNode* LTInit();//打印链表void LTPrint(LTNode* phead);//判断是否为空bool LTEmpty(LTNode* phead);//尾插void LTPushBack(LTNode* phead, LTDataType x);//头插void LTPushFront(LTNode* phead, LTDataType x);//尾删void LTPopBack(LTNode* phead);//头删void LTPopFront(LTNode* phead);//查找LTNode* LTFind(LTNode* phead, LTDataType x);// 在pos之前插入void LTInsert(LTNode* pos, LTDataType x);// 在pos之后插入void LTInsertAfter(LTNode* pos, LTDataType x);// 删除pos位置的值void LTErase(LTNode* pos);//销毁void LTDestroy(LTNode* phead);

//Test.c#include\"List.h\"void TestList1(){LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);}void TestList2(){LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);}void TestList3(){LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTNode* pos = LTFind(plist, 3);if (pos){LTInsert(pos, 30);}LTPrint(plist);LTDestroy(plist);plist = NULL;}int main() {TestList1();TestList2();TestList3();return 0;}

//List.c#include\"List.h\"//创建节点LTNode* BuyLTNode(LTDataType x){LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//判断节点创建是否成功，避免野指针的出现if (newnode == NULL){perror(\"malloc fail\");return NULL;}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;}//初始化链表LTNode* LTInit(){//创建一个哨兵位LTNode*phead = BuyLTNode(-1);phead->next = phead;phead->prev = phead;return phead;}//打印链表void LTPrint(LTNode* phead){assert(phead);LTNode* cur = phead->next;printf(\"phead\");while (cur != phead){printf(\"%d\", cur->data);cur=cur->next;}printf(\"\\n\");}//判断是否为空这里我们可以加上这个函数，如果phead下一个等于phead，说明链表为空只剩下哨兵位自己，// 那么此时我们就不能继续删除了，这里我们可以用这个函数直接替换掉上面的断言bool LTEmpty(LTNode* phead){assert(phead);return phead->next == phead;}//尾插void LTPushBack(LTNode* phead, LTDataType x){assert(phead);LTNode* tail = phead->prev;LTNode* newnode = BuyLTNode(x);tail->next = newnode;newnode->prev = tail;phead->prev = newnode;newnode->next = phead;}//头插void LTPushFront(LTNode* phead, LTDataType x){assert(phead);LTNode* first = phead->next;LTNode* newnode = BuyLTNode(x);phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;}//尾删void LTPopBack(LTNode* phead){assert(phead);assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;free(tail);phead->prev = tailprev;tailprev->next = phead;}//头删void LTPopFront(LTNode* phead){assert(phead);assert(phead->next != phead);LTNode* first = phead->next;LTNode* firstnext = first->next;free(first);phead->next = firstnext;firstnext->prev = phead;}//查找LTNode* LTFind(LTNode* phead, LTDataType x){assert(phead);LTNode* cur = phead->next;while (cur->next != phead){if (cur == x)return cur;cur=cur->next;}return NULL;}// 在pos之前插入void LTInsert(LTNode* pos, LTDataType x){assert(pos);LTNode* posprev = pos->prev;LTNode* newnode = BuyLTNode(x);newnode->prev = posprev;posprev->next = newnode;newnode->next = pos;pos->prev = newnode;}// 在pos之后插入void LTInsertAfter(LTNode* pos, LTDataType x){assert(pos);LTNode* posnext = pos->next;LTNode* newnode = BuyLTNode(x);newnode->prev = pos;pos->next = newnode;newnode->next = posnext;posnext->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 LTDestroy(LTNode* phead){assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);}////代码简化//void LTPushBack(LTNode* phead, LTDataType x)//{//assert(phead);////LTInsert(phead, x);//}//////void LTPushFront(LTNode* phead, LTDataType x)//{//LTInsert(phead->next, x);//}////void LTPopBack(LTNode* phead)//{//assert(phead);//assert(!LTEmpty(phead));//LTErase(phead->prev);//}//////void LTPopFront(LTNode* phead)//{//assert(phead);//assert(!LTEmpty(phead));////LTErase(phead->next);////}