数据结构之带头双向循环链表的实现

前言

之前介绍了 无头单向非循环链表，这次将要介绍带头双向循环链表。这是一种特别好的链表结构。通过学习这种链表结构，我们将会对链表认识理解的更加深刻，为以后学习其他数据结构打下牢固的基础。

---

1.带头双向循环链表相关介绍

带头双向循环链表和之前无头单链表的结构是些不一样的。这种链表结构头节点是哨兵位。何谓哨兵位，简单说来说，这个头节点本身是不存储任何数据的，数据实际上是从第二个节点开始存储的。第二节点就相当于原来无头单向非循环链表的第一个节点。此外这种链表节点除了有next指向下一个结点外，还有prev指向上一个节点（包括哨兵位）。哨兵位的prev指向尾节点，尾节点的next指向哨兵位。这样形成了类似于环状的链表结构，每个结点都环环相扣，形成循环，因为每个节点都能找到其节点的前一个节点地址，还能找到其节点的后一个节点地址，这就相当于是双向结构。这种链表的名字便由其这种特别的结构而得来。

无头单向非循环结构

带头双向循环结构
因为之前实现了单链表，所以再实现这种结构的时候相对会简单的。虽然这种结构更复杂一点，但是这种结构比起之前的单链表会带来很多优势。比任意位置插入数据的时候也不用挨个遍历，而且这种链表每个节点都有指向，避免了空指针的问题。

---

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

1.结构的定义声明和节点的创建

之前提到了这种结构的节点比起先前介绍的单链表节点多了一个prev要指向前一个节点，由此这种结构便很好写出来。

#define  LTDataType int 
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;
1
2
3
4
5
6
7

节点的创建和之前单链表没太大的区别都是通过malloc来申请节点空间

ListNode* BuyListNode(LTDataType x)//创建节点
{
	ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
	if (new_node != NULL)
	{
		new_node->data = x;
		new_node->prev = NULL;
		new_node->next = NULL;
		return new_node;
	}
	else
	{   
		perror("BuyListNode:");
		exit("-1");
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

prev和next都先初始化置为空。后续根据需求在进行赋值，这点和单链表还是一样的。

---

2.相关接口的实现

ListNode* ListCreate();// 创建返回链表的头结点.
void ListDestory(ListNode* Head);// 双向链表销毁
void ListPrint(ListNode* Head);// 双向链表打印
void ListPushBack(ListNode* Head, LTDataType x);// 双向链表尾插
void ListPopBack(ListNode* Head);// 双向链表尾删
void ListPushFront(ListNode* Head, LTDataType x);// 双向链表头插
void ListPopFront(ListNode* Head);// 双向链表头删
ListNode* ListFind(ListNode* Head, LTDataType x);// 双向链表查找
void ListInsert(ListNode* pos, LTDataType x);// 双向链表在pos的前面进行插入
void ListErase(ListNode* pos);// 双向链表删除pos位置的节点
int ListSize(ListNode* Head);//计算节点个数
bool Listmpty(ListNode* Head);//链表判空处理

这个接口函数和之前的单链表相比都是差不多的，无非就是多了链表判空和计算节点个数。这两个函数在实现单链表的时候也可以加上去。加不加都凭自己的喜好，主要的接口没有省略就行。

---

1.创建头节点和打印函数

这里没有引入初始化的接口函数，只是实现一个创建头节点(哨兵位)的函数。这些都是凭自己的需求喜好，我调用插入数据的函数接口也可以实现初始化。这个哨兵位是必须要有的。打印函数实现起来也是比较简单就是挨个遍历即可。

ListNode* ListCreate()//创建哨兵位头节点
{
	ListNode* newnode = BuyListNode(-1);
	newnode->next = newnode;
	newnode->prev = newnode;
	return newnode;
}
1
2
3
4
5
6
7

void ListPrint(ListNode* Head)//打印显示
{
	assert(Head);
	ListNode* cur = Head->next;
	while (cur != Head)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	return;
}
1
2
3
4
5
6
7
8
9
10
11

这个哨兵位是不存储任数据的，所以哨兵位的data存什么值都可以，遍历数据的时候是实际上是从第二个节点开始的。我直接随便存了一个-1，因为在没有任何数据的时候只有哨兵位，所以哨兵位的prev指向自己，next也是指向自己。打印函数也是挨个遍历，之前单链表遍历循环结束的条件是不位空，因为双向链表的尾节点的next是指向哨兵位，所以循环条件不为哨兵位。当cur是哨兵位的时候说明这个链表已经遍历完毕。

---

2.数据的插入

1.尾插

尾插就不用像之前单链表那样挨个遍历找尾了，直接通过哨兵位的prev就可以找到链表尾节点。

代码实现

void ListPushBack(ListNode* Head, LTDataType x)//尾插数据
{   
	assert(Head);
	ListNode* newnode = BuyListNode(x);
	ListNode* head = Head;
	ListNode* tail = head->prev;//找到旧尾
	tail->next = newnode; //旧尾节点next指向新尾
	newnode->next = head; //新尾next指向哨兵位
	newnode->prev = tail; //新尾prev指向旧尾
	head->prev = newnode; //哨兵位prev更新指向新尾
}

1
2
3
4
5
6
7
8
9
10
11
12

之前单链表尾插的时候还要对头节点进判断是否为空，但是这种链表结构直接插入即可。因为始终会有一个哨兵位，没有数据的时候哨兵位也存在，就不需要判断处理了。哨兵位是始终不用更改的，改变的是节点的next和prev，参数类型是一级指针即可。尾插先找到旧尾，旧尾next更新，新节点就是尾节点，新节点next和prev指向对应位置即可。哨兵位的prev也要更新。

---

2.头插数据

头插数据也很简单，头插数据也不用像单链表那样对头节点判空处理。哨兵位不管链表有没有数据始终存在。

代码实现

void ListPushFront(ListNode* Head, LTDataType x)//头插
{
	assert(Head);
	ListNode* head = Head;
	ListNode* newnode = BuyListNode(x);
	ListNode* frist = head->next;//原来链表第一个节点
	newnode->next = frist;//新节点next指向旧的第一个节点
	newnode->prev = head;//新节点的prev指向哨兵位
	frist->prev = newnode;//原来首节点的prev指向新节点
	head->next = newnode; //哨兵位next指向新节点
}
1
2
3
4
5
6
7
8
9
10
11

头插一个新节点，哨兵位的next和原来存储数据的第一个节点的prev都要更新。新节点的next是指向原来第一个节点，新节点的prev指向哨兵位。

---

3.指定位置插入

这个指定位置插入数据是在指定位置pos之前插入数据。这个指定位置之前或者之后插入数据还是凭自己的需求喜好，没有什么固定的实现方式。

代码示例

void ListInsert(ListNode* pos, LTDataType x)//在pos前插入
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);
	ListNode* Prev = pos->prev;
	Prev->next = newnode;
	newnode->next = pos;
	newnode->prev = Prev;
	pos->prev = newnode;
	return;
}
1
2
3
4
5
6
7
8
9
10
11

因为是在pos之前插入数据，所以应该将pos位置的前一个节点先保存，这个节点的next不能在指向pos了，应该指向新节点。pos的prev应该指向新节点。新节点的next要指向pos，新节点的prev要指向原来pos处前一个节点。
这个指定位插入，还可以被尾插和头插复用。

这个头插的函数调用很容易想到，但是这个尾插的调用就看起来有点奇怪。为啥尾插是head在之前呢？其实，这个双向循环链表的结构有点像一个环。首尾相连的结构，头的前一个不就是尾嘛，因此尾插复用的时候参数是Head.

---

3.删除数据

1.尾删数据

尾删数据，需要哨兵位更新一下prev的指向。同时，原来尾节点的前一个节点要成为新的尾节，相应的next指向也要更新。

代码示例

void ListPopBack(ListNode*Head)//尾删
{   
	assert(Head);
	assert(Head->next!=Head);
	ListNode* tail = Head->prev;
	ListNode* head = Head;
	head->prev = tail->prev;
	tail->prev->next = head;
	free(tail);
}
1
2
3
4
5
6
7
8
9
10

尾删数据找到尾节点很简单不用遍历，通过哨兵位的prev就可以很快找到。哨兵位的prev要指向原来倒数第二个节点，倒数第二个节点的next要指向哨兵位。最后用free释放掉尾节点的空间即可。当只有一个尾节点的时就不能删除了。

---

2.头删数据

头删数据实现起来也是很简单的，这个头删是删除保存第一个有效数据的节点。删除后，哨兵位的next应该指向之前保存有效数据的第二个节点，第二个节点的prev应该指向哨兵位。

void ListPopFront(ListNode* Head)//头删
{
	assert(Head);
	assert(Head->next);
	ListNode* head = Head;
	ListNode* frist = head->next;
	head->next = frist->next;
	frist->next->prev = head;
	free(frist);
	return;
}
1
2
3
4
5
6
7
8
9
10
11

只有头节点的时候是不能删除的。

---

3.指定位置删除

这个指定位置删除，有一个位置是不能删除的，那就是哨兵位。同时，更新相应的next和prev即可。

void ListErase(ListNode* pos)//任意位置删除
{
	assert(pos);
	ListNode* Prev = pos->prev;
	ListNode* Next = pos->next;
	Prev->next = Next;
	Next->prev = Prev;
	free(pos);
	return;
}

1
2
3
4
5
6
7
8
9
10
11

这个删除也是可以复用的。

---

4.链表的销毁和查找判空以及节点的计数

1.链表的销毁

销毁和单链表没啥太大区别，挨个遍历释放空间即可。

代码示例

void ListDestory(ListNode* Head)//销毁链表
{
	ListNode* cur = Head->next;
	while (cur != Head)
	{
		ListNode* Next = cur->next;
		free(cur);
		cur = Next;
	}
	free(Head);
	return;
}
1
2
3
4
5
6
7
8
9
10
11
12

这里销毁了以后没有将哨兵位置为空，如果想置空参数设计成二级指针即可。

---

2.查找数据

查找和单链表相比也没啥区别，还是遍历查找。如果找到了就返回节点地址，没找到就返回值空指针。

代码示例

ListNode* ListFind(ListNode* Head, LTDataType x)//查找
{
	assert(Head);
	ListNode* cur = Head->next;
	while (cur != Head)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这个查找没啥好说的还是上次单链表的一样，只不过是循环条件改变了。

---

3.链表判空

在C语言种是可以用用布尔类型的，但是要包含头文件#include。链表判空只需要对哨兵位的next进行判断即可，如果哨兵位的next不是指向自己的，说明链表就不是空的。

代码示例

bool Listmpty(ListNode* Head)//判空
{ 
	assert(Head);
	return Head == Head->next;
}
1
2
3
4
5

如果链表为空就返回真，如果不为空就返回假

---

4.节点计数

节点计数还是挨个遍历即可，实现起来也是很简单的

代码示例

int  ListSize(ListNode* Head)//计算节点个数
{
	ListNode* cur = Head->next;
	int  sz = 0;
	while (cur != Head)
	{
		++sz;
		cur=cur->next;
	}
	return sz;
}
1
2
3
4
5
6
7
8
9
10
11

---

3.总结

• 1.带头双向循环链表是一种非常好的结构。虽然看起开结构稍微复杂了一点，但是实际实现起来并不是特别难。要明白每个节点的next prev的指向，同时可以画图帮助理解记忆。
• 2.同时链表和顺序表各有千秋。不同的结构有不同的优势和劣势。使用者应该注意在适合的场景下选择使用适合的数据结构。
• 3.以上内容如有错误，欢迎指正！