数据结构——带头双向循环链表（c语言实现）

1.单链表和双向链表对比

2.双向链表实现

2.1 创建新节点

2.2 链表初始化

2.3 尾插

2.4 头插

2.5 尾删

2.6 头删

2.7 查找

2.8 指定位置后插入数据

2.9 删除指定节点

2.10 销毁链表

2.11 打印链表

前言：

我们在前几期详细地讲解了不带头单向不循环链表（单链表），使用它的底层代码实现了一个简单的通讯录项目，也介绍了链表分为八种，但是其中最常用的只有两种：（1）不带头单向不循环链表，（2）带头双向循环链表，今天我们要讲解的就是第二种带头双向循环链表

1.单链表和双向链表对比

在介绍双向链表之前，我们先来对比一下单链表和双向链表的区别。

这是单链表：

这是双向链表：

双向链表的特点是每相邻两个节点都相互连接，每个节点都有三个部分，包括data，next，prev，其中data负责存放数据，next负责存放后一个节点的地址，prev负责存放前一个节点的地址，最后一个节点和头节点（哨兵位）相互连接，形成了一个循环双向链表，那么什么是哨兵位呢，哨兵位就是双向链表的头节点，它不存放有效数据，只存放第一个有序数据的节点的地址和最后一个有序数据节点的地址。

那么它们的区别是什么呢？

1. 无头单向非循环链表： 结构简单 ，一般不会单独用来存数据。实际中更多是作为 其他数据结构的子结 构，如哈希桶、图的邻接表等等。另外这种结构在 笔试面试 中出现很多。

2. 带头双向循环链表： 结构最复杂 ，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

2.双向链表实现

介绍完了双向链表的区别我们接下来就要着手开始用代码实现双向链表了。由于代码可能较多，我们将双向链表的代码分成了三个文件，分别是List.h,List.c和tste.c文件：

在list.h文件中，我们要包含我们会用到的头文件，其他文件只要包含List.h文件就可以使用这些头文件了：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

双向链表的实现也是在此文件中，由于我们不知道将来使用链表会存放什么样的数据，所以我们使用typedef对这个数据的类型改名，我们实现链表使用的是int类型，所以我们对int改名：

typedef int ListNodeData;

链表中的next和prev链表是用来存放节点地址的，所以它们为指针类型，而为了方便使用，我们将链表使用typedf改名，下面是双向链表实现：

typedef struct ListNode
{ListNodeData data;struct ListNode* prev;struct ListNode* next;}LTNode;

2.1 创建新节点

创建新节点我们使用malloc从堆申请一块LTNode类型大小的内存，它的data类型用来存放将来要插入的数据，prev和next指针在创建这个节点时先让它指向自己，如果要创建新节点，就调用这个函数，它会返回一个指向这块空间的指针：

LTNode* LTBuyNode(ListNodeData x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = newnode;newnode->prev = newnode;return newnode;}//创建一个新节点

2.2 链表初始化

在最初创建一个链表时，它的内部为空，什么也没有，我们初始化应该此链表让它至少有一个哨兵位：

void LTInit(LTNode** pphead)
{assert(pphead);*pphead = LTBuyNode(-1);}//初始化

2.3 尾插

尾插操作应该先创建一个新节点，插入顺序为：先让新节点的prev指针指向最后一个节点，然后让新节点的next指针指向哨兵位实现循环，以上的两步都不会影响旧节点，接下来就是让最后一个节点的next指针指向这个新节点，然后让哨兵位的prev指针指向新节点完成尾插：

具体实现代码为：

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

2.4 头插

头插操作并不是将新节点放在哨兵位之前，而是将新节点放在第一个有效数据节点之前，所以我们应该将新节点放在哨兵位的后面。先创建一个新节点，让新节点的prev指针指向哨兵位，让它的next指针指向哨兵位的next指向的节点，以上两步不会影响任何节点，做完这两步后，先让哨兵位后面那个节点的prev指针指向新节点，然后让哨兵位的next指针指向新节点，这两步不能调换顺序，否则会找不到哨兵位后面那个节点，下面是代码实现：

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

2.5 尾删

执行删除操作之前我们应该先判断这个链表除哨兵位之外有没有其他节点，如果没有，就无法删除，而尾删操作也比较简单，只需要让尾节点的前一个节点的next指针指向哨兵位，然后让哨兵位的prev指针指向位尾节点，以上过程需要创建一个新变量，否则无法找到我们要删除的节点，接着释放掉尾节点后置空就可以了：

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

画图演示：

2.6 头删

头删操作与尾删类似，如果没有两个及以上节点的话无法执行删除操作，头删要删除的是哨兵位后面那个节点，所以我们先创建一个指针存放我们要删除节点的地址，将哨兵位的next指针指向我们要删除节点的下一个节点，然后将我们要删除节点的下一个节点的prev指针指向哨兵位，完成这些操作后释放我们要删除的节点然后置空：

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

2.7 查找

如果我们要查找一个节点，应该先判断链表是否为空，然后将我们要查找的节点的数据与链表中节点的数据一一对比，如果数据内容相同，说明找到了，将这个节点返回，如果循环一圈还没有找到，说明链表中不存在这样的节点，返回应一个空指针：

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

2.8 指定位置后插入数据

我们可以先调用查找函数，然后调用它返回的节点，试着在它的后面插入数据，而它的操作与头插非常相像，只是将哨兵位改成了我们指定的节点：

void LTInsertAfter(LTNode* phead, LTNode* pop, ListNodeData x)
{assert(phead&&pop);LTNode* newnode = LTBuyNode(x);newnode->prev = pop;newnode->next = pop->next;pop->next->prev = newnode;pop->next = newnode;
}//指定节点后插入数据

2.9 删除指定节点

删除节点我们需要先判断链表中是否有两个及以上节点，否则无法删除，删除指定节操作我们先将指定节点的前一个节点的next指向我们指定节点的下一个节点，然后将指定节点的下一个节点的prev指针指向指定节点的前一个节点，这个过程不需要创建中间变量，因为我们有指定节点的地址：

void LTErase(LTNode* phead, LTNode* pop)
{assert(phead && phead->next);pop->next->prev = pop->prev;pop->prev->next = pop->next;free(pop);pop = NULL;}//指定删除节点

2.10 销毁链表

我们链表的每一个节点都是使用malloc函数手动在堆上申请的，需要我们手动释放：

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

2.11 打印链表

指行这么多插入删除操作我们如果测试的话就使用这个函数打印出来，而打印函数只需要循环打印这个链表一次就可以了：

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

接下来我们使用这个函数来测试一下我们的方法：

可以看到我们的方法都没有问题，那么这期的双向链表就到此结束啦，我将代码放在下面，感兴趣的小伙伴可以试试哦。

List.h :

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int ListNodeData;
typedef struct ListNode
{ListNodeData data;struct ListNode* prev;struct ListNode* next;}LTNode;LTNode* LTFind(LTNode* phead, ListNodeData x);//查找void LTInit(LTNode** pphead);//初始化void LTPushBack(LTNode* phead, ListNodeData x);
//尾插void LTPrint(LTNode* phead);//打印链表void LTPushFront(LTNode* phead, ListNodeData x);
//头插void LTPopBack(LTNode* phead);//尾删void LTPopFront(LTNode* phead);//头删void LTInsertAfter(LTNode* phead, LTNode* pop, ListNodeData x);
//指定节点后删除void LTErase(LTNode* phead, LTNode* pop);
//指定位置删除void LTDestroy(LTNode* phead);
//销毁链表

List.c :

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"LTNode* LTBuyNode(ListNodeData x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = newnode;newnode->prev = newnode;return newnode;}//创建一个新节点LTNode* LTFind(LTNode* phead, ListNodeData x)
{assert(phead && phead->next);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//查找函数void LTInit(LTNode** pphead)
{assert(pphead);*pphead = LTBuyNode(-1);}//初始化void LTPushBack(LTNode* phead, ListNodeData 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, ListNodeData 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&&phead->next);LTNode* del = phead->prev;del->prev->next = del->next;del->next->prev = del->prev;free(del);del = NULL;}//尾删void LTPopFront(LTNode* phead)
{assert(phead && phead->next);LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}//头删void LTInsertAfter(LTNode* phead, LTNode* pop, ListNodeData x)
{assert(phead&&pop);LTNode* newnode = LTBuyNode(x);newnode->prev = pop;newnode->next = pop->next;pop->next->prev = newnode;pop->next = newnode;
}//指定节点后插入数据void LTErase(LTNode* phead, LTNode* pop)
{assert(phead && phead->next);pop->next->prev = pop->prev;pop->prev->next = pop->next;free(pop);pop = NULL;}//指定删除节点void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");}//打印void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}}//销毁链表

test.c :

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void test01()
{LTNode* plist = NULL;LTInit(&plist);printf("尾插\n");LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPrint(plist);printf("头插\n");LTPushFront(plist, 0);LTPrint(plist);/*printf("尾删\n");LTPopBack(plist);LTPopBack(plist);LTPrint(plist);*/printf("头删\n");LTPopFront(plist);LTPopFront(plist);LTPrint(plist);printf("在3后面插入数据:\n");LTNode* Find = LTFind(plist, 3);/*if (Find == NULL){printf("找不到！\n");}else{printf("找到了\n");}*/LTInsertAfter(plist, Find, 56);LTPrint(plist);printf("删除指定节点3：\n");LTErase(plist, Find);LTPrint(plist);printf("销毁链表\n");LTDestroy(plist);plist = NULL;}int main()
{test01();return 0;
}