作者：几冬雪来

时间：2023年3月14日

内容：数据结构双向链表讲解

目录

前言： 

双向链表： 

​编辑

1.创建文件：

2.创建结构体： 

3.初始状态： 

实现初始化：

4.尾插： 

5.尾删: 

6.头插： 

7.在pos位置之前插入一个值：

8.在pos之前删除一个值： 

9.代码：

结尾：

前言： 

在之前我们学习了链表的知识，并写了不少有关链表的题目，这让我们对链表有一些了解。但是在以前我们曾说过，链表有八大种类，以往我们的知识和刷题都是建立在单向链表的基础上。而今天我们要学习的是八大链表种类中另一个具有代表性的——双向链表。 

双向链表： 

单向链表和双向链表是我们链表重要的点，它们两人有各种的优点所在，类似双向链表对比起单向链表，最明显的优势就是它可以重后向前进行遍历，这是单向链表所不能做到的。

1.创建文件：

这里写双向链表代码的格式和我们书写单向链表代码的差不多。一开始我们依旧创建三个文件，一个.h文件，两个.c文件。

2.创建结构体： 

在这里，双向链表定义的结构体和单向链表的有一些不同，比如我们的双向链表在结构体中定义了两个指针，而单向链表则只定义了一个。 

那么为什么双向链表定义两个指针呢？这从它的名字中可以看出。

我们双向链表一个结点要求可以指向它前一个结点和后一个结点，因此我们的结构体中需要两个指针来进行这种操作。 

3.初始状态： 

为了实现我们以后代码的头删头插等一系列，我们的带头双向链表的初始状态应该是什么样的呢？

既然是带头双向链表，那么一开始我们就会给链表创建一块哨兵位的头结点。 

这里单单只是一个指针是不够的，我们还需要这一块头结点的指向。有人提议说将哨兵位的next和prev都指向空。

但是如果我们将链表的初始状态定义成这个样子的话，那带头的双向链表中的循环就没办法体现出来了。那么要体现循环的初始状态是怎么样的？

这里最简单的方式就是让哨兵位的prev和next都指向自己，这样就可以构成一个循环的结构了。 

循环：

1.尾next指向哨兵位的头

2.哨兵位的头的prev指向尾

由此我们就可以得出这样的一个结论。 

实现初始化：

那么这里我们该怎么实现代码的初始化？

首先就是要传递我们的指针。 

接下来要创建一个哨兵位的头结点，这里我们也给哨兵位的头结点一个值。

这里我们并没有让自己指向自己是因为这仅仅是初始化而已。下来就是让其体现循环的特性，将其正式的初始化。

但是在这里有一个问题，那就是形参和实参的问题。因为要改变结点，也就是改变指针，因此在.h文件中我们需要传二级指针。

二级指针的麻烦程度大家有目共睹，那么这里可以怎么样修改吗？

这里我们可以要求返回值。

4.尾插： 

在讲双向链表的尾插的时候，我们先来回忆一下单向链表是如果进行尾插的。

单向链表尾插的话，首先要先遍历一遍链表找到尾结点，然后让尾结点的next指向我们要插入的值，我们要插入的值的next置空。

那如果是我们的带头双向链表尾插又是怎么样的呢？

要实现带头双向链表的尾插，我们不需要先遍历一遍链表找到尾结点，在这个链表中我们能直接通过找头结点是prev，也就是类似头结点的前一个结点的位置来找到我们的尾结点，然后再对尾结点的指针进行一系列修改即可。

在这里我们先创建一个新结点newnode，里面存放我们要插入的值，然后确定尾结点的位置，接下来就是指针的互换了。 

指针互换中，我们先将原尾结点的next指向我们新创建的结点newnode，newnode的前一个指向原尾结点，newnode的next指向头结点，头结点的prev指向newnode。这样就可以实现我们的尾插操作了。

它与我们的单向链表进行尾插的操作进行比较，我们带头双向链表明显要简单得多，而且如果链表为空的话，我们的单向链表第一个值为赋值，这要进行分类讨论。而带头双向链表则没有这个问题，因为哪怕指针为空，我们的带头双向链表中有哨兵位的头结点。链表即使为空，里面也是有数据的。

有因为我们的phead不能为空，因此一开始还要对phead进行断言操作。

接下来就给我们的代码一些值让其打印出来看看结果。 

依旧上来先对其断言。但是带头双向链表是一个循环结构，我们应该在哪里停止打印是一个问题，如果稍有不慎就会死循环。

在打印这里，我们创建一个指针cur，并且让它指向哨兵位的next，接下来是循环如果cur != cur，这个时候就打印该结点的值，并让cur向下走。

注：这里结束标志是cur不为phead，而不是尾结点的next，如果为尾结点的next最后一个值不会被打印。 

从结果也可以看出打印成功了。 

5.尾删: 

如果是尾删的话，我们的单链表要进行很多的步骤。

首先要判断，如果链表中只有一个结点的话，我们只需要将其释放即可。

要是多个结点，我们则要找到尾结点的上一个结点，将其置空。

双向链表又是怎么样操作的呢？这里的操作方法类似我们头结点的方法。

 一开始增加一个函数来判断我们的链表是否为空。

 这里如果链表为空就返回false，相反则返回true，接下来就是头删的代码书写了。

起始就是断言，第一个断言是表示链表有无传错，第二个断言则是链表是否为空。下来还是先确定我们的尾结点的位置，然后再通过尾结点找到尾结点的上一个结点的位置。再下来，让头结点的prev指向tailPrev，让tailPrev的next指向头，最后将原尾结点释放并置空即可。 

这样一来我们的尾删的代码也成功的实现了。

6.头插： 

讲解完了尾插和尾删操作，接下来就是头插和头删的操作了。那么我们这里先讲解头插的操作。

在双向链表中，头插的操作和尾插的操作大差不差，但是在头插里面有一些我们要注意的坑存在。

那在头插操作中有什么坑存在？我们画一张图来看看。

在这里要注意的坑就是指针替换的顺序。这里我们必须要先让新结点的指针先处理哨兵位的下一个结点，因为如果我们先处理哨兵位和新结点的指针的话，原哨兵位的与下一个结点的链接会断掉。

那我们的代码要怎么写？

开始还是对我们的指针进行断言操作，然后另创建一个指针来放我们要插入的值。接下来就是先处理phead->next和新结点之间的关系。而后再处理哨兵位与newnode间的指针链接。处理方法和尾插操作差不多，我们这里直接看代码。

如果你写代码的时候经常忘记要加入顺序的话，这里我们还有一种方法去处理这个问题。 

那就是创建一个新结点，将我们的phead->next进行一个保存，防止丢失，这样我们就可以不按顺序写代码了。 我们也可以将它打印出来看看结果。

7.在pos位置之前插入一个值：

除开头插和尾插，我们这里还有中间插入的方法，那么在pos之前插入一个值又是这么做的？

这里我们就需要将pos前一个结点也给一个指针来保存。接下来就是我们的写代码的环节了，代码要怎么书写？ 

这里先对pos进行我们的断言操作，接下来给pos前一个指针prev的命名，然后就是我们创建的值的指针。我们人pos前一个指针prev->next指向newnode，让newnode->prev指向prev，然后再对pos和newnode之间的指针进行修改即可。 

和单向链表的中间插入的代码相同，这个代码也可以用于代替我们的头插和尾插的程序。 

8.在pos之前删除一个值： 

既然了解了如何在pos之前插入一个值，那么如何在pos之前前删除一个值我们应该也是可以写出来的。

首先是思路部分。

在这里我们找到pos的前一个和前前一个结点，并对其命名，而后进行修改让posprevprev的next指向pos，pos的prev指向posprevprev。最后将posprev释放即可。

我们的代码就大概如下所示，同样的这个代码也可以用来代替头删和尾删的代码。 

9.代码：

那么老规矩在最后的时候我们将代码承上。

Lish.h文件

#pragma once
#include 
#include 
#include 
#include typedef int LTDataType;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;void LTPrint(LTNode* phead);LTNode* LTInit();bool LTEmpty(LTNode* phead);void LTDestroy(LTNode* phead);void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead); void LTInsert(LTNode* pos,LTDataType x);
void LTErase(LTNode* pos);

Lish.c文件

#include "Lish.h"LTNode* BuyListNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");return NULL;}node->next = NULL;node->prev = NULL;node->data = x;return node;
}LTNode* LTInit()
{LTNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){printf("%d <=> ", cur->data);cur = cur->next;}
}bool LTEmpty(LTNode* phead)
{return phead->next == phead;
}void LTPopBack(LTNode* phead)
{assert(phead);assert(LTEmpty(phead));LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;tailPrev->next = phead;phead->prev = tailPrev;free(tail);tail = NULL;
}void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);/*newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;*/LTNode* first = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;
}void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* prev = pos->prev;LTNode* newnode = BuyListNode(x);prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posprevprev = pos->prev->prev;posprevprev->next = pos;pos->prev = posprevprev;free(posprev);posprev = NULL;
}

test.c文件 

#include "Lish.h"void TestList1()
{LTNode* plist = LTInit();/*LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);printf("\n");LTPopBack(plist);LTPopBack(plist);LTPrint(plist);printf("\n");*/LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);
}int main()
{TestList1();return 0;
}

结尾：

到这里，带头双向链表的基础部分我们就有个大概的了解了，同时也有一部分的带头双向链表的内容我们虽然现在没有说到，但是以后是会讲解的。最后希望这篇博客能为大家带来帮助。