📒博客主页：要早起的杨同学的博客
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文所属专栏：【数据结构】
✉️坚持和努力从早起开始！
💬参考在线编程网站：🌐牛客网🌐力扣
🙏作者水平有限，如果发现错误，敬请指正！感谢感谢！

前言

• 实际中链表的结构非常多样，上篇单链表博文中我们介绍了8种链表结构，但实际中最常用的还是这两种结构

• 无头单向非循环链表：

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

• 带头双向循环链表：

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

此链表其实也是两个环，每个节点的前驱指针构成一个环，后继指针也可以构成一个环。

---

学习双向链表之前，建议先学习下顺序表和单链表：
【C语言】详解顺序表(SeqList)
【C语言】链表详解（无头单向非循环）

一. 带头双向循环链表的实现

首先新建一个工程（ 博主使用的是 VS2019 ）

• list.h（带头双向循环链表的类型定义、接口函数声明、引用的头文件）
• list.c（带头双向循环链表接口函数的实现）
• Test.c（主函数、测试顺序表各个接口功能）

如图：

• list.h 头文件代码如下：

#pragma once
#include
#include
#include

typedef int DLTDateType;//定义数据类型

typedef struct DLT_Node
{
	struct DLT_Node* prev;
	struct DLT_Node* next;
	DLTDateType date;
}DLT_Node;

//初始化节点
DLT_Node* dlt_init();
//打印节点
void dlt_print(DLT_Node* phead);
//尾插
void dlt_push_back(DLT_Node* phead, DLTDateType x);
//头插
void dlt_push_front(DLT_Node* phead, DLTDateType x);
//尾删
void dlt_pop_back(DLT_Node* phead);
//头删
void dlt_pop_front(DLT_Node* phead);

//查找pos位置的节点
DLT_Node* dlt_find(DLT_Node* plist, DLTDateType x);
//pos位置前插入函数
void dlt_insert(DLT_Node* plist, DLTDateType x);
//删除pos节点的函数
void dlt_erase(DLT_Node* plist);

//判断链表是否为空
int is_empty(DLT_Node* phead);
//链表长度
int dlt_len(DLT_Node* phead);
//销毁链表,使用该函数时，手动将指针置空。也可以改成二级指针
void dlt_destory(DLT_Node* phead);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

---

这里重点讲解 list.c 中各个接口函数的实现。

1）双向链表的定义

带头双向循环链表，有一个数据域和两个指针域，一个是前驱指针，指向其前一个节点；一个是后继指针，指向其后一个节点

//定义双向链表的节点
typedef int DLTDateType;//定义数据类型

typedef struct DLT_Node
{
	struct DLT_Node* prev;
	struct DLT_Node* next;
	DLTDateType date;
}DLT_Node;
1
2
3
4
5
6
7
8
9

---

2）双向链表的初始化

初始化带头双向循环链表，首先动态申请一个头结点，头结点的前驱和后继指针都指向自己，形成一个循环

• 动态申请一个新节点

//动态申请一个新节点
DLT_Node* BuyNewNode(DLTDateType x)
{
	DLT_Node* node = (DLT_Node*)malloc(sizeof(DLT_Node));
	node->date = x;
	node->next = NULL;
	node->prev = NULL;
	return node;
}

DLT_Node* dlt_init(void)
{
	DLT_Node* newNode = BuyNewNode(0);
	newNode->next = newNode;
	newNode->prev = newNode;
	return newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 初始化头节点

头指针初始指向 NULL，初始化链表时，我们要改变头指针的指向，使其指向头节点，所以需要传二级指针

//初始化链表
void dlt_init(DLT_Node** pphead)
{
	*pphead = BuyNewNode(-1);  //动态申请一个头节点
    
	(*pphead)->prev = *pphead;  //前驱指针指向自己
	(*pphead)->next = *pphead;  //后继指针指向自己
}
1
2
3
4
5
6
7
8

---

3）双向链表的销毁

销毁链表，因为前面的接口参数都用的是一级指针，为了保持一致所以也用一级指针接收，但是需要在函数外面置空phead。也可以用二级指针参数，在函数里面置空。

//销毁双向链表
void dlt_destory(DLT_Node* phead)
{
	assert(phead);
	DLT_Node* cur = phead->next;
	while (cur != phead)
	{
		DLT_Node* Next = cur->next;
		free(cur);
		cur = Next;
	}
	free(phead);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

4）打印双向链表

//打印双向链表
void dlt_print(DLT_Node* phead)
{
    assert(phead);
	DLT_Node* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->date);
		cur = cur->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12

---

5）双向链表的尾插

• 图解尾插操作

• 代码如下

//双向链表尾插
void dlt_push_back(DLT_Node* phead, DLTDateType x)
{
	assert(phead);  //头指针不能为空

	DLT_Node* newnode = BuyNewNode(x);  //动态申请一个节点
	DLT_Node* tail = phead->prev;  //记录尾节点

	tail->next = newnode;  //1、尾节点的后继指针指向新节点
	newnode->prev = tail;  //2、新节点的前驱指针指向尾节点

	newnode->next = phead;  //3、新节点的后继指针指向头节点
	phead->prev = newnode;  //4、头节点的前驱指针指向新节点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

6）双向链表的尾删

• 图解尾插操作

• 代码如下

先记录下尾节点tail，尾节点的直接前驱tailPrev，然后再进行尾删操作。

//双向链表的尾删
void dlt_pop_back(DLT_Node* phead)
{
	assert(phead);
	assert(phead->next != phead);  //只剩头节点时，链表为空，不能再继续删除
	//head ...  tailprev tail
	DLT_Node* tail = phead->prev;  //记录尾节点
	DLT_Node* tailPrev = tail->prev;  //记录尾节点的直接前驱
	
	tailPrev->next = phead;  //1、尾节点的前驱节点的next指针指向头节点
	phead->prev = tailPrev;  //2、头节点的prev指针指向尾节点的前驱节点
	free(tail);  //3、释放尾节点
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

7）双向链表的头插

• 图解头插操作

• 代码如下

先记录下头节点的直接后继pheadNext，即第一个节点，然后再进行头插操作。

//双向链表的头插
void dlt_push_front(DLT_Node* phead, DLTDateType x)
{
	assert(phead);

	DLT_Node* newnode = BuyNewNode(x); //申请新节点
	DLT_Node* pheadNext = phead->next;  //记录第一个节点
	//head newnode pheadNext
	//头节点和新节点建立链接
	phead->next = newnode;
	newnode->prev = phead;

	//新节点和第一个节点建立链接
	newnode->next = pheadNext;
	pheadNext->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

8）双向链表的头删

• 图解头插操作

• 代码如下

先记录下头节点的直接后继pheadNext，即第一个节点，然后再进行头删操作。

//双向链表的头删
void dlt_push_front(DLT_Node* phead)
{
	assert(phead);
	assert(phead->next != phead);  //只剩头节点时，链表为空，不能再继续删除

	DLT_Node* pheadNext = phead->next;  //记录第一个节点

	//头节点和第一个节点的后继节点建立链接
	phead->next = pheadNext->next;
	pheadNext->next->prev = phead;
	//头删
    free(pheadNext);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

9）查找双向链表中的元素

若查找到该元素，返回它的地址，否则返回 NULL

//在双向链表中查找元素，并返回该元素的地址
DLT_Node* dlt_find(DLT_Node* phead, DLTDateType x)
{
	assert(phead);

	DLT_Node* cur = phead->next;
	while (cur != phead)  //遍历链表
	{
		if (cur->data == x)
		{
			return cur;  //找到了，返回该元素的地址
		}
		cur = cur->next;
	}
	return NULL;  //没找到，返回 NULL
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

10）在指定pos位置之前插入元素

• 图解插入操作

• 代码如下

首先记录下pos的直接前驱posPrev，然后再进行插入操作。

//在指定pos位置之前插入元素
void dlt_insert(DLT_Node* pos, DLTDateType x)
{
	assert(pos);  //断言

	DLT_Node* newnode = BuyListNode(x);  //申请一个节点
	DLT_Node* posPrev = pos->prev;  //记录pos的直接前驱

	//pos的直接前驱和新节点建立链接
	posPrev->next = newnode;
	newnode->prev = posPrev;

	//新节点和pos建立链接
	newnode->next = pos;
	pos->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

观察该函数的参数，需要传递指定pos位置节点的地址，调用该函数时需要搭配 ListFind 函数（查找双向链表中的元素），判断一下能不能找到该元素，若找到了该元素，才能进行插入操作。

• 补充

实现了该函数之后，我们可以尝试改进下头插函数（pos相当于链表的第一个节点）和尾插函数（pos相当于链表的头节点）

---

11）删除指定pos位置的元素

• 图解删除操作

• 代码如下

首先记录下pos的直接前驱posPrev，和pos的直接后继posNext，然后再进行删除操作。

//删除指定pos位置的元素
void dlt_erase(DLT_Node* pos)
{
	assert(pos);  //断言

	DLT_Node* posPrev = pos->prev;  //记录pos的直接前驱
	DLT_Node* posNext = pos->next;  //记录pos的直接后继
	//pos的直接前驱和直接后继建立链接
	posPrev->next = posNext;
	posNext->prev = posPrev;
	//释放pos位置的元素
	free(pos);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

观察该函数的参数，需要传递指定pos位置节点的地址，调用该函数时需要搭配 dlt_find函数（查找双向链表中的元素），判断一下能不能找到该元素，若找到了该元素，才能进行删除操作。

• 补充

实现了该函数后，我们可以尝试下改进头删函数（pos相当于链表的第一个节点）和尾删函数（pos相当于链表的最后一个节点）

---

12）双向链表的判空

双向带头循环链表中，head不是存放有效数据的节点，如果只有一个head节点，说明链表为空。

//双向链表的判空
int is_empty(DLT_Node* phead)
{ 
	assert(phead);
	//若为空，返回 ture，否则返回 false
	return phead->next == phead;
}
1
2
3
4
5
6
7

---

13）获取双向链表的元素个数

int dlt_len(DLT_Node* phead)
{
	DLT_Node* cur = phead->next;
	int size = 0;
	while (cur != phead)
	{
		++size;
		cur = cur->next;
	}
	return size;
}
1
2
3
4
5
6
7
8
9
10
11

---

当我们要实现带头双向循环链表时，可以先写初始化、销毁、打印、查找、在pos之前插入元素、删除pos位置元素这些接口，尾插尾删、头插头删接口可以直接复用（在pos之前插入元素、删除pos位置元素）的代码。