数据结构与算法（四）——双向链表&双向循环链表
在前面两篇文章中，我们了解了单向链表和单项循环链表如下图：
此时，比如我已经获取到了C节点，那么我想要获取到C节点的前一个节点，就需要再次遍历该链表，且时间复杂度是O(n)。那么有没有一个好的方案可以便捷地获取到C的前一个节点呢，答案是使用双向链表。
双向链表的节点结构如下：
一般而言，单向链表、单向循环链表、双向链表、双向循环链表都会带有头节点，这样的话，设计起来就会比较方便。本篇文章中，我对双向链表和双向循环链表的讲解都是建立在链表有头结点的基础之上的。需要指出的是，我在上篇文章中，讲解单项循环链表的时候，是没有使用头结点的，但是之所以未使用头结点，就是为了给大家展示不使用头结点会是多么麻烦。
一、双向链表
1，双向链表的创建
逻辑如下:
1，新增一个双向链表节点，前驱后继均设为空，并将该新节点设置为链表的头结点
2，新建一个临时节点变量temp，来记录当前链表中的最后一个节点
3，循环添加节点，在每一个循环体中
（1）新增节点，并将其前驱后继设为空
（2）将新节点的前驱设为temp
（3）将temp的后继设为新节点
（4）将temp更新为新节点
代码如下：
#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
// 元素值的类型
#define ElementType int
// 操作的状态
typedef enum : int {
Success,
Error,
} Status;
// 双向链表的节点
typedef struct Node {
struct Node *prior; // 前驱
ElementType data; // 数值域
struct Node *next; // 后继
}Node;
// 链表的类型
typedef struct Node * LinkedList;
// 1，创建双向链表
/*
1，新增一个双向链表节点，前驱后继均设为空，并将该新节点设置为链表的头结点
2，新建一个临时节点变量temp，来记录当前链表中的最后一个节点
3，循环添加节点，在每一个循环体中
（1）新增节点，并将其前驱后继设为空
（2）将新节点的前驱设为temp
（3）将temp的后继设为新节点
（4）将temp更新为新节点
*/
Status createLinkedList(LinkedList *list) {
// 新建一个节点，并将该节点设置为头结点
LinkedList headNode = malloc(sizeof(Node));
if (!headNode) {
return Error;
}
headNode->prior = NULL;
headNode->data = -1;
headNode->next = NULL;
*list = headNode;
//记录链表中的最后一个节点
LinkedList tailNode = *list;
//向链表中循环加入节点
for (int i = 1; i <= 10; i++) {
// 新建一个节点
LinkedList node = malloc(sizeof(Node));
if (!node) {
return Error;
}
node->prior = NULL;
node->data = i;
node->next = NULL;
// 将新节点的前驱设置为当前的尾结点
node->prior = tailNode;
// 将当前尾结点的后继设置为新节点
tailNode->next = node;
// 更新当前的尾结点
tailNode = node;
}
return Success;
}2，双向链表的打印
思路如下：
自首元结点开始循环遍历，而不是自头结点开始打印。
当遍历到最后一个节点的时候跳出循环，通过后继是否为NULl来判断是否是最后一个节点。
代码如下：
// 2，打印双向链表
/*
自首元结点开始循环遍历，而不是自头结点开始打印。
当遍历到最后一个节点的时候跳出循环，通过后继是否为NULl来判断是否是最后一个节点。
*/
Status printLinkedList(LinkedList list) {
LinkedList tempNode = list->next;
if (!tempNode) {
printf("当前的双向循环链表为空");
return Error;
}
printf("当前的双向循环链表：\n");
while (tempNode) {
printf("%d\n", tempNode->data);
tempNode = tempNode->next;
}
return Success;
}3，向双向链表的指定位置上插入元素
逻辑如下：
1，新建节点，并将新节点的前驱后继均设置为NULL
2，遍历找到插入位置前面的那个节点，以下称为前驱节点
3，根据前驱节点找到后继节点
4，设置新节点的前驱为前驱节点
5，如果后继节点不为空，则设置后继节点的前驱为新节点
6，设置新节点的后继为后继节点
7，设置前驱节点的后继为新节点
代码如下：
// 3，往双向链表中插入元素
/*
1，新建节点，并将新节点的前驱后继均设置为NULL
2，遍历找到插入位置前面的那个节点，以下称为前驱节点
3，根据前驱节点找到后继节点
4，设置新节点的前驱为前驱节点
5，如果后继节点不为空，则设置后继节点的前驱为新节点
6，设置新节点的后继为后继节点
7，设置前驱节点的后继为新节点
*/
Status insertElement(LinkedList *list, int index, ElementType element) {
// 新建节点
LinkedList node = malloc(sizeof(Node));
if (!node) {
return Error;
}
node->data = element;
node->prior = NULL;
node->next = NULL;
//找到插入位置之前的那个节点（如果插入位置超出链表长度，则直接插入到链表尾部）
LinkedList priorNode = *list;
for (int i = 1; i < index && priorNode->next; i++, priorNode = priorNode->next);
// 设置新节点的前驱为前驱结点
node->prior = priorNode;
// 找到插入位置之前的那个节点的下一个节点
LinkedList nextNode = priorNode->next;
// 如果插入位置不是尾结点，则设置插入位置后面那一个节点的前驱为新节点
if (nextNode) {
nextNode->prior = node;
}
// 设置新节点的后继为后继节点
node->next = nextNode;
// 设置前驱结点的后继为新节点
priorNode->next = node;
return Success;
}4，删除双向链表指定位置上的节点
这里额外说明一下，我们之前讲了4种逻辑结构和2种物理结构，不管是集合结构、线性结构、树结构还是图结构，这些逻辑结构最终都是通过顺序结构或者链式结构这两种物理结构中的一种存储在内存中的。
逻辑如下：
1，找到该位置上的节点，如果节点不存在，则直接返回错误
2，分别使用三个变量来记录待删除位置的节点，以及其前驱结点和后继节点
3，判断后继节点是否存在，如果后继节点不存在，则直接将前驱节点的后继设置为NUll，然后free待删除节点
4，如果后继节点存在
（1）设置后继节点的前驱为前驱节点
（2）设置前驱结点的后继为后继节点
（3）free待删除节点
代码如下：
// 4，删除双向链表指定位置上的节点
/*
1，找到该位置上的节点，如果节点不存在，则直接返回错误
2，分别使用三个变量来记录待删除位置的节点，以及其前驱结点和后继节点
3，判断后继节点是否存在，如果后继节点不存在，则直接将前驱节点的后继设置为NUll，然后free待删除节点
4，如果后继节点存在
（1）设置后继节点的前驱为前驱节点
（2）设置前驱结点的后继为后继节点
（3）free待删除节点
*/
Status deleteElementAtIndex(LinkedList *list, int index, ElementType *deletedElement) {
// 如果链表为空，则直接报错
if (!(*list)) {
return Error;
}
// 校验坐标的有效性
if (index < 1) {
return Error;
}
// 找到待删除的节点
LinkedList toDeleteNode = *list;
int i = 1;
while (i <= index && toDeleteNode) {
toDeleteNode = toDeleteNode->next;
i++;
}
//确保待删除节点存在
if (!toDeleteNode) {
return Error;
}
// 找到前驱与后继节点
LinkedList priorNode = toDeleteNode->prior;
LinkedList nextNode = toDeleteNode->next;
if (!nextNode) {
// 如果后继节点不存在，则直接将前驱节点的后继置为NULL
priorNode->next = NULL;
} else {
//如果前驱后继都存在
priorNode->next = nextNode;
nextNode->prior = priorNode;
}
*deletedElement = toDeleteNode->data;
free(toDeleteNode);
return Success;
}5，删除双向链表中指定的元素
逻辑如下：
1，找到该元素所在的节点，如果节点不存在，则直接返回错误
2，分别使用三个变量来记录待删除位置的节点，以及其前驱结点和后继节点
3，判断后继节点是否存在，如果后继节点不存在，则直接将前驱节点的后继设置为NUll，然后free待删除节点
4，如果后继节点存在
（1）设置后继节点的前驱为前驱节点
（2）设置前驱结点的后继为后继节点
（3）free待删除节点
代码如下：
// 5，删除双向链表中的指定元素
/*
1，找到该元素所在的节点，如果节点不存在，则直接返回错误
2，分别使用三个变量来记录待删除位置的节点，以及其前驱结点和后继节点
3，判断后继节点是否存在，如果后继节点不存在，则直接将前驱节点的后继设置为NUll，然后free待删除节点
4，如果后继节点存在
（1）设置后继节点的前驱为前驱节点
（2）设置前驱结点的后继为后继节点
（3）free待删除节点
*/
Status deleteValue(LinkedList *list, ElementType value) {
if (*list == NULL) {
return Error;
}
// 找到待删除节点
LinkedList toDeleteNode = (*list)->next; // 自首元节点开始
while (toDeleteNode && toDeleteNode->data != value) {
toDeleteNode = toDeleteNode->next;
}
// 如果待删除节点不存在，则直接返回错误
if (!toDeleteNode) {
return Error;
}
// 记录待删除节点的前驱和后继
LinkedList priorNode = toDeleteNode->prior;
LinkedList nextNode = toDeleteNode->next;
// 如果后继节点不存在，则直接将前驱的Next置为空
if (!nextNode) {
priorNode->next = NULL;
free(toDeleteNode);
return Success;
}
//如果后继节点存在
priorNode->next = nextNode;
nextNode->prior = priorNode;
free(toDeleteNode);
return Success;
}6，在双向链表中查找元素的坐标
逻辑如下：
遍历循环，匹配给定的元素值；
如果没有找到，则返回-1
代码如下：
// 6，在双向链表中查找元素的坐标
/*
遍历循环，匹配给定的元素值；
如果没有找到，则返回-1
*/
int checkValue(LinkedList list, ElementType value) {
LinkedList tempNode = list->next;
// 寻找对应的节点
int index;
for (index = 1; tempNode && tempNode->data != value; index++, tempNode = tempNode->next);
// 如果对应的节点不存在，则直接返回-1
if (!tempNode) {
return -1;
}
// 如果对应的节点存在，则直接返回节点坐标
return index;
}7，在双向链表中更新节点
代码如下：
// 7，在双向链表中更新节点
Status updateLinkedList(LinkedList *list, int index, ElementType newElement) {
// 如果链表为空，则直接报错
if (!(*list)) {
return Error;
}
//找到指定坐标下的节点
LinkedList node = (*list)->next;
for (int i = 1; i < index && node; i++, node = node->next);
// 如果节点不存在则报错
if (!node) {
return Error;
}
// 如果节点存在，则更新其值
node->data = newElement;
return Success;
}二、双向循环链表
我们这里的双向循环链表是有头结点的，这样的话，进行增删改查的操作就都很方便。
双向链表：头结点的前驱为NUll，尾结点的后继为Null。
双向循环链表：头结点的前驱是尾结点，尾结点的后继是头结点。
以上是二者的唯一区别。
1，双向循环链表的初始化
逻辑如下：
1，创建一个节点，并将该节点的前驱和后继均设置为其自身
2，将新节点设置为链表的头结点
3，使用一个临时变量来记录当前链表中的最后一个节点
4，循环往链表中新增节点
（1）新建一个节点
（2）将新节点的后继设置为头结点
（3）将头节点的前驱设置为新节点
（3）将新节点的前驱设置为临时节点变量（尾结点）
（4）将尾结点的后继设置为新节点
（5）更新临时变量的指向为新节点
代码如下：
// 1，双向循环链表的初始化
/*
1，创建一个节点，并将该节点的前驱和后继均设置为其自身
2，将新节点设置为链表的头结点
3，使用一个临时变量来记录当前链表中的最后一个节点
4，循环往链表中新增节点
（1）新建一个节点
（2）将新节点的后继设置为头结点
（3）将头节点的前驱设置为新节点
（3）将新节点的前驱设置为临时节点变量（尾结点）
（4）将尾结点的后继设置为新节点
（5）更新临时变量的指向为新节点
*/
Status createLinkedList(LinkedList *list) {
// 新建一个节点，并将该节点设置为链表的头结点
LinkedList headNode = malloc(sizeof(Node));
if (!headNode) {
return Error;
}
headNode->data = -1;
headNode->prior = headNode;
headNode->next = headNode;
*list = headNode;
// 通过一个临时变量来记录链表当前的尾结点
LinkedList tailNode = *list;
// 循环新增节点
for (int i = 0; i < 10; i++) {
// 新建节点，并插入到链表尾部
LinkedList node = malloc(sizeof(Node));
if (!node) {
return Error;
}
node->data = i;
node->prior = tailNode;
tailNode->next = node;
node->next = *list;
(*list)->prior = node;
// 更新链表尾结点临时变量
tailNode = node;
}
return Success;
}2，遍历打印双向循环链表
代码如下：
Status printLinkedList(LinkedList list) {
if (!(list)) {
printf("该链表不存在");
return Error;
}
LinkedList tempNode = (list)->next;
if (!tempNode) {
printf("该链表为空");
return Error;
}
printf("链表信息如下:\n");
do {
printf("%d\n", tempNode->data);
tempNode = tempNode->next;
} while (tempNode != list);
return Success;
}3，往双向循环链表中插入元素
逻辑如下：
1，循环遍历找到插入位置的上一个元素，以下称之为前驱结点
2，如果没有找到，则返回错误
3，如果找到了，则根据前驱结点，找到后继节点
4，新建一个节点，并设置其值
5，设置新节点的前驱为前驱结点，后继为后继节点
6，设置前驱结点的后继为新节点，设置后继节点的前驱为新节点
代码如下：
// 3，往双向循环链表中插入元素
/*
1，循环遍历找到插入位置的上一个元素，以下称之为前驱结点
2，如果没有找到，则返回错误
3，如果找到了，则根据前驱结点，找到后继节点
4，新建一个节点，并设置其值
5，设置新节点的前驱为前驱结点，后继为后继节点
6，设置前驱结点的后继为新节点，设置后继节点的前驱为新节点
*/
Status insert(LinkedList *list, int index, ElementType element) {
// 如果链表本身就不存在，则报错
if (!(*list)) {
return Error;
}
// 校验坐标的合法性
if (index < 1) {
return Error;
}
// 找到待插入位置前面的那一个节点
LinkedList priorNode = *list; // 初始节点设置为头结点
for (int i = 1; i < index && priorNode->next != *list; i++, priorNode = priorNode->next);
// 找到当前插入位置的节点
LinkedList nextNode = priorNode->next;
// 新建节点并设置其值、前驱、后继
LinkedList node = malloc(sizeof(Node));
if (!node) {
return Error;
}
node->data = element;
node->prior = priorNode;
node->next = nextNode;
//更新前驱结点的后继，以及后继节点的前驱
priorNode->next = node;
nextNode->prior = node;
return Success;
}4，删除双向循环链表中的指定节点
逻辑如下：
1，找到指定位置上的节点
2，如果没有找到，则报错
3，找到待删除节点的前驱和后继
4，将前驱结点的后继设置为后继节点，将后继节点的前驱设置为前驱结点
5，free待删除节点
代码如下：
// 4，删除双向循环链表中某个位置上的节点
/*
1，找到指定位置上的节点
2，如果没有找到，则报错
3，找到待删除节点的前驱和后继
4，将前驱结点的后继设置为后继节点，将后继节点的前驱设置为前驱结点
5，free待删除节点
*/
Status deleteElement(LinkedList *list, int toDeleteIndex, ElementType *toDeleteElement) {
// 如果链表不存在，则直接报错
if (!(*list)) {
return Error;
}
// 检验坐标正确性
if (toDeleteIndex < 1) {
return Error;
}
// 寻找待删除的节点
LinkedList toDeleteNode = (*list)->next; // 自首元节点开始遍历
int i;
for (i = 1; i < toDeleteIndex && toDeleteNode->next != *list; i++, toDeleteNode = toDeleteNode->next);
// 如果待删除位置超过了链表长度，则报错
if (toDeleteNode->next == *list && i < toDeleteIndex) {
return Error;
}
// 找到待删除节点的前驱和后继
LinkedList priorNode = toDeleteNode->prior;
LinkedList nextNode = toDeleteNode->next;
// 设置前驱结点的后继为后继节点，设置后继节点的前驱为前驱结点
priorNode->next = nextNode;
nextNode->prior = priorNode;
// 记录删除节点的值
(*toDeleteElement) = toDeleteNode->data;
// free待删除节点
free(toDeleteNode);
return Success;
}以上。