---

关于双向链表

首先链表有8种基本分法

其中在笔者之前文章种详细介绍的 单链表 是不带头单项不循环链表
而今天笔者要介绍的就是 带头双向循环链表 双向链表

我们可以把链表理解为下图

所以我们双向链表的结构往往是这样的

即

typedef int LTDataType;
//定义双向链表节点的结构
typedef struct ListNode
{int data;struct ListNode* next;struct ListNode* prev;
}LTNode;

---

双向链表的初始化

第一步我们需要进行双向链表的初始化，双向链表的初始化需要注意的一个问题是，传进去的参数是一级指针还是二级指针，这本应该后面大致写完了再讨论，但是这里提前说了

在笔者后面的方法中，例如尾插，头插，尾删，头删等都是用一级指针，这是因为双向链表有一个好处，我们存在一个哨兵位，这个节点是初始化时创立的，不需要改变，同时有存储着前后节点的地址，只需要通过成员名调用即可，这里呈现一下会出现的方法参数

//打印
void LTPrint(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);

笔者这里据大多数关于双向链表的地址传参都是一级指针，这在一定程度上，保证了接口的一致性，为后来调用双向链表数据结构者降低了理解成本，这也就是我们在设计程序时需要注意的一点

笔者这里通过二级指针传参和无传参的方法各创建了一个初始化方法
大家可以看到两种方法连语句都基本一致，但是后者明显会比前者好，因为在以后不论是我们还是其他人通过一览所有的方法名后，不需要刻意去记初始化需要传参二级指针，直接空着使用就行了

//申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc newnode");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;//指向自己return newnode;
}//初始化1
void LTInit(LTNode** pphead)
{//该双向链表创建一个哨兵位*pphead = LTBuyNode(-1);
}
//初始化2
LTNode* newLTInit()
{return LTBuyNode(-1);
}

---

双向链表的打印

双向链表的打印比单链表好理解太多了，
因为存在一个无意义的 哨兵位 用来记录开头，链接末尾，
所以只需要新创建一个新的节点用来帮忙定位当前位置，如果这个节点的值跟 哨兵位 一样，便退出

代码如下

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

---

双向链表方法调用 - 尾删为例

大家可以先看一下下图，我们在双向链表的末尾放上新节点

为了保证双向链表在使用时不发生意外，
我们先将 newnode 的 prev 和 next 对接好 d3 和 头节点phead
这样做只是给新的节点的前后向确定好，不影响原来的双向链表

再将 d3 的 next 对准 newnode，
phead 的 prev 对准 newnode

下面代码呈现

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

---

双向链表的查找 - 指定位置之后插入为例

指定位置之后插入，除了插入这个重要点，就是指定位置这个大头了，那么我们该如何实现找到指定位置呢

同样因为 哨兵位 的存在，我们新定义节点来一个一个对比下去，知道等于 哨兵位 为止，代表整个双向链表中都没有这个要查找的数据

即

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

既然知道如何找到指定位置，那么接下来就是插入了，
我们通过指定位置的节点信息，按照前面尾插的方法就行了，也是很简单的

//在pos之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

---

双向链表结束 - 链表的销毁

因为我们前面有提到为保证接口的一致性我们同意设定为一级指针，但这样我们能做的就是将除 哨兵位 以外的节点全部置为空，但是外部所创建的节点，即我们一开始所初始化的点无法在内部置为空，所以出去后仍然需要置为空

即

//销毁
void LTDestory(LTNode* phead)
{assert(phead);LTNode* pcur = phead;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;pcur = NULL;//这点无所谓，跳出方法，就会为空
}

这是内部的销毁，出去后，在置为空一次，即

LTDestory(plist);
plist = NULL;

---

小结及整体代码实现

有一说一，双向链表真的很好理解，而且写方法时，往往不用循环就能很容易解出来，比单链表和数组方便许多，大家如果想要自己实现双向链表，尽量没完成一次方法时，调试检验一下，方便找到错误

下面为大家展现一下笔者的代码

“List.h”

#pragma once#define _CRT_SECURE_NO_WARNINGS  1
#pragma warning(disable:6031)#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;
//定义双向链表节点的结构
typedef struct ListNode
{int data;struct ListNode* next;struct ListNode* prev;
}LTNode;//声明双向链表中提供的方法
//尽量都用一级指针，降低调用方的理解成本，保持接口的一致性
//初始化
//void LTInit(LTNode** pphead);
LTNode* newLTInit();//打印
void LTPrint(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);

“List.c”

#include"List.h"//申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc newnode");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;//指向自己return newnode;
}//初始化
void LTInit(LTNode** pphead)
{//该双向链表创建一个哨兵位*pphead = LTBuyNode(-1);
}LTNode* newLTInit()
{return LTBuyNode(-1);
}//销毁
void LTDestory(LTNode* phead)
{assert(phead);LTNode* pcur = phead;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;pcur = NULL;//这点无所谓，跳出方法，就会为空
}//打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->",pcur->data);pcur = pcur->next;}printf("\n");
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead;newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;
}//尾删
void LTPopBack(LTNode* phead)
{//链表必须有效且不为空assert(phead && phead->next != phead);phead->prev->prev->next = phead;phead->prev = phead->prev->prev;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);phead->next->next->prev = phead;phead->next = phead->next->next;
}//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x)return pcur;pcur = pcur->next;}return NULL;
}//在pos之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}
//在pos之前插入数据
void LTInsertAfter(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos;newnode->prev = pos->prev;pos->prev->next = newnode;pos->prev = newnode;
}
//删除pos节点
void LTErase(LTNode* pos)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

测试文件就不展示了，没有什么参考价值，能够独自理解并写出上述方法名，一个简简单单的调试自然不在话下