数据结构：双向链表（带头循环）网站首页 技术交流

在前面我们了解过单向链表（无头非循环）之后发现单向链表虽然是结构最简单的链表，但是写起来是比较麻烦的，在之前我们提到过链表一共有八种结构，那么都是哪八种结构呢？

链表的分类：

1.带头和不带头。

2.单向和双向。

3.循环和非循环。

这几种结构进行排列组合一共就是有八种链表结构，但是这么多的链表结构我们最常用的只有两种：

1.单向无头非循环链表：

2. 双向带头循环链表：

如果单纯的通过比较两种链表的复杂程度的话单向无头非循环链表就比双向带头循环链表简便好多，但是呢双向带头循环链表的实现代码是比单向无头非循环链表要简单许多，因为双向带头循环链表的结构设计的非常厉害，许多操作可以直接进行，不需要做一些铺垫，那么话不多说，我们直接开始实现双向带头循环链表：

1.双向链表的认识

双向带头循环链表中有一个哨兵位的头结点，这个哨兵位的头结点是不存放任何数据的，接下来的每一结点（包含哨兵位）中都有两个指针，一个指向前面，一个指向后面，还有一个变量用来存放有效数据，在最后的一个结点的next指针会指向这个链表的头结点，而头结点的prev是指向最后的尾结点的。

当只有一个头结点的时候，这个头结点的prev和next都是指向自己的，这样来构成一个循环结构。

2.链表的实现

实现双向带头循环链表的步骤和单向链表的步骤是一样的，它们都是具备增删查改的功能。

在进行插入，删除的时候需不需要使用二级指针的传参？答案是不需要的，因为带头双向循环链表是有一个哨兵位的头结点，这时我们进行插入、删除时改变的是结构体的成员，使用结构体的指针就可以了。

注：小编提供的这种双向链表的写法仅代表个人意见。

2.1链表的创建

链表的实现还是和顺序表的实现一样分模块来写，当然也是可以在一个源文件中完成的，我们这里创建两个源文件：Test.c和List.c，再创建一个头文件：List.h,这里的文件命名不做要求，表示的有意义就行。同样的我们在Test.c中实现基本逻辑，在Lits.c中实现顺序表的细节，在List.h中进行函数声明和头文件包含等，话不多说，我们直接开始：

头文件：List.h
#pragma once

//                     带头双向循环链表 

#include <stdio.h>

typedef int LTDataType;

typedef struct ListNode
{
	struct ListNode* prev;   //指向前一个结点
	struct ListNode* next;   //指向后一个结点
	LTDataType data;         //存放数据
}LTNode;

2.2结点的创建

链表的结点是malloc动态开辟出来的，所以我们按需申请按需释放，所以为了后面的方便，我们可以直接分装一个函数专门用来创建链表的结点，双向链表的结点的创建于单链表不同的是还需要有一个指向前一个结点的指针：

头文件：List.h
//创建结点
LTNode* BuyLTNode(LTDataType x);
源文件：List.c
//创建结点
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));  //动态开辟结点
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->data = x;

	return newnode;
}

2.3初始化链表

在单向链表中我们讲过是不需要进行初始化的，但是在双向带头循环链表中有一个哨兵位的头结点，并且刚创建的链表只有一个哨兵位，所以为了达到循环，我们需要将它的prev和next都指向它自己：

头文件：List.h
//初始化链表
LTNode* LTInit();
源文件：Lits.c
//初始化
LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);  //哨兵位在这里是不存储任何有效数据，
                                    //所以传给它什么值都可以
	//实现循环，指向自己
	phead->next = phead;       
	phead->prev = phead;

	return phead;
}
源文件：Test.c
#include "List.h"

void LTNodeTest1()
{
	LTNode* plist = LTInit();  //哨兵位的头结点
}

int main()
{

	LTNodeTest1();
	
	return 0;
}

2.4从尾部插入数据

从尾部插入数据首先得找到尾，那么这时就用到了头指针的prev，prev指向的就是尾，然后将要插入的结点链接在链表中。需要将尾结点的next指向要插入的结点，将新插入的结点的prev指向尾结点，然后让头结点的prev指向要插入的结点，再将要插入的结点的next指向头，这样子就大功告成了。

有多个结点：

只有一个结点：

头文件：List.h
//尾插
void LTPushBack(LTNode* phead, LTDataType x); 
源文件：List.c
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);  //创建要插入的结点

	//找尾
	LTNode* tail = phead->prev;   

	//进行链接
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

2.5从头部插入数据

从头部插入数据就更加简单了，就是将一个新结点直接插入到哨兵位的后面，这里还要注意，如果你不保存哨兵位的下一个结点，插入时对对于指针指向的改变就要有顺序，先让原来的头结点后面的结点的prev指向新的结点，然后再让头结点的next指向新节点，但是如果将头结点后面的结点存起来就跟顺序没有关系，小编推荐大家使用存起来的方法，因为这样也不容易出错，当然了，还是按照个人喜好：

有多个结点：

只有一个结点：

头文件：List.h
//头插
void LTPushFront(LTNode* phead, LTDataType x);
源文件：List.c
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	//保存结点，方便使用
	LTNode* first = phead->next;  

	//创建要插入的结点
	LTNode* newhead = BuyLTNode(x);

	//链接新的结点
	phead->next = newhead;
	newhead->prev = phead;

	newhead->next = first;
	first->prev = newhead;
}

2.6打印链表

在之前的打印单向链表中我们使用链表何时为空来作为判断标志，但是在双向链表中可不敢再用这个条件作为判断依据，应该以哨兵位的头结点作为判断依据，创建一个指向头指针后面的结点的指针用来迭代遍历链表，当这个指针不为头指针时就继续遍历，当等于头指针的时候就表示遍历一遍已经结束了，所以在这里我们需要停止：

头文件：List.h
//打印
void LTPrint(LTNode* phead);
源文件：List.c
//打印
void LTPrint(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;  //头结点后面的结点
	printf("phead<==>");
	//遍历
	while (cur!= phead)   
	{
		printf("%d<==>", cur->data);
		//迭代
		cur = cur->next;
	}
	printf("
");
}
当写好了打印函数我们可以将我们前面写的尾插和头插来测试一下：

源文件：Test.c
void LTNodeTest1()
{
	LTNode* plist = LTInit();  //哨兵位的头结点

	//头插
	LTPushFront(plist, 2);
	LTPushFront(plist, 1);

	//尾插
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);

	//打印
	LTPrint(plist);
}

int main()
{
	LTNodeTest1();
	return 0;
}

2.7从尾部删除数据

从尾部删除数据首先要找尾结点，再找到尾结点的前一个结点，然后将尾的前一个结点和头结点链接，再将尾结点释放，但是这里要注意如果只有一个头结点时是不能删除的，所以需要再加上对链表的头结点的判断：

只有头结点时就不能再删除了，因此当head的next是head时就要停止，因为后面的头删也存在这样的问题，所以我们干脆分装一个函数来实现：

源文件：List.c
//判断链表是否为空
bool LTEmpty(LTNode* phead)
{
	assert(phead);

	//如果等于phead就返回的是true（真），不是就返回false（假）
	return phead->next == phead;  
}
注：这里的判断函数不一定要使用这个，只要能判断出来是否只有一个头结点就行，按照自己喜欢的代码风格来写

头文件：List.h
//尾删
void LTPopBack(LTNode* phead);
源文件：List.c
//尾删
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);
}

2.8从头部删除数据

头删就更简单了，只需要找到头结点的下一个结点first，和头结点的下一个结点的下一个结点second，然后将头结点与second结点链接，再释放掉first，当然也是要判断链表中是否只有一个头结点：

头文件：List.h
//头删
void LTPopFront(LTNode* phead);
源文件：List.c
//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	//判断链表是否只有一个头结点
	assert(!LTEmpty(phead));

	
	LTNode* first = phead->next;
	LTNode* second = first->next;

	//链接
	phead->next = second;
	second->prev = phead;
	//删除
	free(first);
}

2.9在链表中查找数据

查找数据与单向链表的查找数据一样，只是遍历链表的条件不同，找到了就返回结点的地址，找不到就返回NULL：

头文件：List.h
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
源文件：List.c
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* cur = phead->next;
	//遍历链表
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}
	return NULL;
}

2.10修改链表中的数据

修改链表中的数据是需要配合查找数据来使用，既然我们已经查找到了这个结点的地址，那么将它存起来然后进行修改就可以了，在这里我们来演示一下：

源文件：Test.c
void LTNodeTest1()
{
	LTNode* plist = LTInit();  //哨兵位的头结点

	//头插
	LTPushFront(plist, 2);
	LTPushFront(plist, 1);
	//尾插
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	//打印
	LTPrint(plist);

	//头删
	LTPopFront(plist);
	//尾删
	LTPopBack(plist);
	//打印
	LTPrint(plist);

	//查找
	LTNode* pos = LTFind(plist, 3);
	//修改
	if (pos != NULL)
	{
		pos->data = 2;
	}
	//打印
	LTPrint(plist);

}

int main()
{
	LTNodeTest1();
	return 0;
}

2.11在pos之前插入数据

在指定位置插入数据也是要配合查找函数来完成，先通过查找函数找到pos，然后找到pos的前一个结点，然后将将新节点链接就可以了，这里只需改变四个指针的位置即可：

头文件：Lits.h
//在pos位置之前插入
void LTInsert(LTNode* pos, LTDataType x);
源文件：List.c
//在pos位置之前插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	//找pos的前一个结点
	LTNode* posPrev = pos->prev;
	LTNode* newnode = BuyLTNode(x);

	//链接
	posPrev->next = newnode;
	newnode->prev = posPrev;

	newnode->next = pos;
	pos->prev = newnode;
}

2.12删除pos位置的数据

删除pos位置的数据也是要通过查找函数来找到pos这个结点，然后记录pos的前一个结点和pos的后一个结点，然后将pos的前一个结点和pos的后一个结点链接，将pos结点释放掉：

头文件：List.h
//删除pos位置上的数据
void LTErase(LTNode* pos);
源文件：List.c
//删除pos位置上的数据
void LTErase(LTNode* pos)
{
	assert(pos);
	
	//找前一个结点
	LTNode* posPrev = pos->prev;
	//找后一个结点
	LTNode* posNext = pos->next;

	//链接
	posPrev->next = posNext;
	posNext->prev = posPrev;
	//释放
	free(pos);
}

2.13代码复用

当我们写好了在指定位置的插入和删除时，那么头插、尾插、头删、尾删都可以复用这些函数，只需要传递相应的结点地址就可以了：

尾插：

LTInsert(phead, x);

头插：

LTInsert(phead->next, x);

尾删：

LTErase(phead->prev);

头删：

LTErase(phead->next);

代码演示：

源文件：List.c

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	//代码复用
	LTInsert(phead, x);
	//LTNode* newnode = BuyLTNode(x);  //创建要插入的结点

	找尾
	//LTNode* tail = phead->prev;   

	进行链接
	//tail->next = newnode;
	//newnode->prev = tail;
	//newnode->next = phead;
	//phead->prev = newnode;
	
}

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	//判断链表是否只有头结点
	assert(!LTEmpty(phead));

	//代码复用
	LTErase(phead->prev);

	找尾结点和尾结点的前一个结点
	//LTNode* tail = phead->prev;
	//LTNode* tailPrev = tail->prev;

	链接尾结点的前一个结点和头结点
	//tailPrev->next = phead;
	//phead->prev = tailPrev;
	释放掉尾结点完成尾删
	//free(tail);
}


//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	//代码复用
	LTInsert(phead->next, x);

	保存结点，方便使用
	//LTNode* first = phead->next;  

	创建要插入的结点
	//LTNode* newhead = BuyLTNode(x);

	链接新的结点
	//phead->next = newhead;
	//newhead->prev = phead;

	//newhead->next = first;
	//first->prev = newhead;
}

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	//判断链表是否只有一个头结点
	assert(!LTEmpty(phead));

	//代码复用
	LTErase(phead->next);

//	LTNode* first = phead->next;
//	LTNode* second = first->next;
//
//	//链接
//	phead->next = second;
//	second->prev = phead;
//	//删除
//	free(first);
}

源文件：Test.c

void LTNodeTest2()
{
	LTNode* plist = LTInit();  //哨兵位的头结点

	//头插
	LTPushFront(plist, 2);
	LTPushFront(plist, 1);
	//尾插
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	//打印
	LTPrint(plist);

	//查找
	LTNode* pos1 = LTFind(plist, 3);
	
	//在pos之前插入
	LTInsert(pos1, 3);
	//打印
	LTPrint(plist);

	//删除pos位置的值
	LTNode* pos2 = LTFind(plist, 1);
	LTErase(pos2);
	//打印
	LTPrint(plist);
}

int main()
{
	//LTNodeTest1();
	LTNodeTest2();

	return 0;
}

2.14销毁单链表

在使用完链表之后我们需要对其进行销毁，因为结点都是动态开辟的，所以需要进行手动释放，否则会造成内存泄漏：

头文件：Lits.h
//销毁链表
void LTDestroy(LTNode* phead);
源文件：List.c
//销毁链表
void LTDestroy(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;

	//遍历依次进行释放
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

3.完整代码展示

头文件：List.h

#pragma once

//                     带头双向循环链表 

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int LTDataType;

typedef struct ListNode
{
	struct ListNode* prev;   //指向前一个结点
	struct ListNode* next;   //指向后一个结点
	LTDataType data;         //存放数据
}LTNode;


//初始化链表
LTNode* LTInit();

//创建结点
LTNode* BuyLTNode(LTDataType x);

//尾插
void LTPushBack(LTNode* phead, LTDataType x); 

//尾删
void LTPopBack(LTNode* phead);

//打印
void LTPrint(LTNode* phead);

//头插
void LTPushFront(LTNode* phead, LTDataType x);

//头删
void LTPopFront(LTNode* phead);

//查找
LTNode* LTFind(LTNode* phead, LTDataType x);

//在pos位置之前插入
void LTInsert(LTNode* pos, LTDataType x);

//删除pos位置上的数据
void LTErase(LTNode* pos);

//销毁链表
void LTDestroy(LTNode* phead);

源文件：List.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "List.h"

//创建结点
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));  //动态开辟结点
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->data = x;

	return newnode;
}

//初始化
LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);  //哨兵位在这里是不存储任何有效数据，所以传给它什么值都可以
	//实现循环，指向自己
	phead->next = phead;       
	phead->prev = phead;

	return phead;
}

//判断链表是否为空
bool LTEmpty(LTNode* phead)
{
	assert(phead);

	//如果等于phead就返回的是true（真），不是就返回false（假）
	return phead->next == phead;  
}

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	//代码复用
	LTInsert(phead, x);
	//LTNode* newnode = BuyLTNode(x);  //创建要插入的结点

	找尾
	//LTNode* tail = phead->prev;   

	进行链接
	//tail->next = newnode;
	//newnode->prev = tail;
	//newnode->next = phead;
	//phead->prev = newnode;
	
}

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	//判断链表是否只有头结点
	assert(!LTEmpty(phead));

	//代码复用
	LTErase(phead->prev);

	找尾结点和尾结点的前一个结点
	//LTNode* tail = phead->prev;
	//LTNode* tailPrev = tail->prev;

	链接尾结点的前一个结点和头结点
	//tailPrev->next = phead;
	//phead->prev = tailPrev;
	释放掉尾结点完成尾删
	//free(tail);
}

//打印
void LTPrint(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;  //头结点后面的结点
	printf("phead<==>");
	//遍历
	while (cur!= phead)   
	{
		printf("%d<==>", cur->data);
		//迭代
		cur = cur->next;
	}
	printf("
");
}

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	//代码复用
	LTInsert(phead->next, x);

	保存结点，方便使用
	//LTNode* first = phead->next;  

	创建要插入的结点
	//LTNode* newhead = BuyLTNode(x);

	链接新的结点
	//phead->next = newhead;
	//newhead->prev = phead;

	//newhead->next = first;
	//first->prev = newhead;
}

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	//判断链表是否只有一个头结点
	assert(!LTEmpty(phead));

	//代码复用
	LTErase(phead->next);

//	LTNode* first = phead->next;
//	LTNode* second = first->next;
//
//	//链接
//	phead->next = second;
//	second->prev = phead;
//	//删除
//	free(first);
}

//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* cur = phead->next;
	//遍历链表
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}
	return NULL;
}


//在pos位置之前插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	//找pos的前一个结点
	LTNode* posPrev = pos->prev;
	LTNode* newnode = BuyLTNode(x);

	//链接
	posPrev->next = newnode;
	newnode->prev = posPrev;

	newnode->next = pos;
	pos->prev = newnode;
}

//删除pos位置上的数据
void LTErase(LTNode* pos)
{
	assert(pos);
	
	//找前一个结点
	LTNode* posPrev = pos->prev;
	//找后一个结点
	LTNode* posNext = pos->next;

	//链接
	posPrev->next = posNext;
	posNext->prev = posPrev;
	//释放
	free(pos);
}

//销毁链表
void LTDestroy(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;

	//遍历依次进行释放
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

源文件：Test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "List.h"

void LTNodeTest1()
{
	LTNode* plist = LTInit();  //哨兵位的头结点

	//头插
	LTPushFront(plist, 2);
	LTPushFront(plist, 1);
	//尾插
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	//打印
	LTPrint(plist);

	//头删
	LTPopFront(plist);
	//尾删
	LTPopBack(plist);
	//打印
	LTPrint(plist);

	//查找
	LTNode* pos = LTFind(plist, 3);
	//修改
	if (pos != NULL)
	{
		pos->data = 2;
	}
	//打印
	LTPrint(plist);

}

void LTNodeTest2()
{
	LTNode* plist = LTInit();  //哨兵位的头结点

	//头插
	LTPushFront(plist, 2);
	LTPushFront(plist, 1);
	//尾插
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	//打印
	LTPrint(plist);

	//查找
	LTNode* pos1 = LTFind(plist, 3);
	
	//在pos之前插入
	LTInsert(pos1, 3);
	//打印
	LTPrint(plist);

	//删除pos位置的值
	LTNode* pos2 = LTFind(plist, 1);
	LTErase(pos2);
	//打印
	LTPrint(plist);
}

int main()
{
	//LTNodeTest1();
	LTNodeTest2();

	return 0;
}