数据结构：双向循环带头链表

一.前言

再次之前我已经讲过了单链表的使用了。但是我们会发现，单链表还存在一些问题，比如尾插尾删的时候比较麻烦，或者单链表很多函数还要传二级指针…这些情况在双向循环带头链表这里都不是问题。

二.双向循环带头链表结构

这个链表的结构虽然是所有链表中最复杂的那一种，但是我肯定它用起来绝对是最简单的。过会我们实现起来的时候，你们就能发现它能给我们带来很多便利。

因为功能强大，实际使用的过程中双向循环带头链表使用的是很多的。但这不代表单链表就没人用了，实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

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

3.1双向循环带头链表节点的结构体

typedef int LTDataType;

//定义结构体
typedef struct LTNode
{
	LTDataType data;
	struct LTNode* next;
	struct LTNode* prev;
}LTNode;

1
2
3
4
5
6
7
8
9
10

3.2创建一个节点

//创建一个节点
LTNode* BuyListNode(LTDataType x)
{
	//用malloc函数创建一个节点
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("BuyListNode");
		exit(-1);
	}

	//将节点内容赋值
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.3初始化链表

//初始化链表
LTNode* LTInit()
{
	//头节点里的数据不能存长度
	LTNode* phead = BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}
1
2
3
4
5
6
7
8
9
10

我们这个链表是带头并且是双向的，带头的意思是带有一个哨兵位。刚开始时链表长度为0，这里初始化的内容是把链表的头创建好：
因为是循环链表，所以这个链表的最后一个的下一个应该指向第一个，第一个的前面应该指向最后一个。但此时只有一个节点所以这个节点的下一个和上一个都指向自己。

在这里我把哨兵位里面的内容放成-1，这里我是随便放的，你们可以放其他的，但是不要在里面放成链表的个数，有的书里可能会将链表哨兵位的数据放成链表的个数，虽然这里肯上去是挺好的，而且也可以实现出来，无非就是在定义一个变量再添加节点时加一个，删除节点时减一个。但是这样会存在一些缺陷：
首先链表里的数据不可能任何时候都是int类型，虽然现在我定义好的类型是int类型，但是我改成char类型呢？

这样就会导致结构体里data的类型也是char类型的，现在问题就来了char类型的取值范围是-128~127.如果你的链表长度是128呢？这样不就越界了吗？这样的出来的结果还是你想要的吗？

如果真的想要计算链表长度，还是写成一个函数比较好，这样写容易出错。

3.4打印链表

//打印链表
void LTPrint(LTNode* phead)
{
	//	判断链表是否为空
	if (phead->next == phead)
	{
		printf("NULL");
		exit(-1);
	}

	LTNode* cur = phead->next;

	//判断cur指针是否走到底
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

首先判断链表是否为空，如果为空就打印NULL。通过图可以看到phead,phead->next,phead->prev其实指向的是一块地方：所以我们随便判断其中两个是否相等就行，相等就代表是空链表，此时只有一个光杆司令在这里杵着，后面没其他的节点。

可能在单链表的时候我们判断循环结束的条件是cur是否为空，但是现在是双向循环链表，链表只要存在节点cur就不可能为空，所以此时我们换一种写法，先看图：本来cur走到这里的时候，只要把此时指向的节点打印出来然后再往后走一步就该结束了，但是注意它的下一步其实指向的是phead,也就是说在cur == phead的时候就该停下来跳出循环了，所以循环的判断条件应该是：

while (cur != phead)
1

3.5链表的头插

//链表的头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	//需要插入的节点
	LTNode* newnode = BuyListNode(x);
	LTNode* cur = phead->next;
	
	newnode->next = cur;
	newnode->prev = phead;
	phead->next = newnode;
	cur->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

直接看图：如果刚看我刚给的代码，可能不是很好理解，但通过图来看，应该就能看懂了吧。

newnode->next = cur;
1

newnode->prev = phead;
1

phead->next = newnode;
1

cur->prev = newnode;
1

这样就把新节点完美的插进去了。

3.6链表的头删

//链表头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	//如果phead == phead->next说明这个链表是空链表
	//空链表就不要再删了
	assert(phead != phead->next);

	LTNode* next = phead->next;
	
	phead->next = next->next;
	next->next->prev = phead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

头删非常简单，两步就能搞定：


将这两个节点链接起来之后，把next指向的节点free掉就行

3.7链表的尾插

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

	LTNode* newnode = BuyListNode(x);
	phead->prev->next = newnode;
	newnode->prev = phead->prev;
	phead->prev = newnode;
	newnode->next = phead;
}
1
2
3
4
5
6
7
8
9
10
11

可以先将新的节点与之前最后一个节点连起来，接下来就是将此时最后一个节点与头节点相连：


这样就完成了尾插的操作。因为循环的关系，最后一个节点就不用麻烦的去遍历了，直接找头节点的上一个节点就行。将本来复杂的尾删变得十分的简洁。

3.8链表的尾删

//链表尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead != phead->next);

	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;

	tailprev->next = phead;
	phead->prev = tailprev;

	free(tail);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

把最后一个节点操作，只需将头节点与倒数第二个节点连起来就行，把最后一个节点切开就能完成尾删的操作。
连好之后就可以把tail指向的节点释放掉了，当然这一步在链接之前完成也可以但前提是先将tail->prev的地址保存下来。

3.9链表的查找

//链表的查找
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

因为phead是哨兵位的节点，我们是不在这里保存数据的，所以定义cur指针遍历的时候应从头节点的下一个节点开始遍历。
如果cur == phead说明已经走到末节点又回来了，如果这期间一直没有找到需要找的x，说明找不到就返回NULL.

3.10在pos位之前插入x

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

	LTNode* newnode = BuyListNode(x);
	LTNode* prev = pos->prev;

	prev->next = newnode;
	newnode->next = pos;
	newnode->prev = prev;
	pos->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

因为pos,prev,newnode三个指针我们都已经知道了，所以这四段代码的顺序也不用这么在意，只要能连起来就可以。

3.11删除pos位位置

//删除pos位位置
void LTErase(LTNode* pos)
{
	assert(pos);

	LTNode* prev = pos->prev;
	LTNode* next = pos->next;

	prev->next = next;
	next->prev = prev;
	free(pos);
}
1
2
3
4
5
6
7
8
9
10
11
12

删除也很简单把prev,next指向的两个节点相连，然后把pos指向的节点释放掉。

3.11判断链表是否为空

//判断链表是否为空
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead == phead->next;
}
1
2
3
4
5
6

bool类型有两种true和false,如果整型表达式为真，这个函数就返回true,假就返回false

我们这个函数是判断是否为空链表如果phead == phead->next说明此时链表只有一个头节点，也就是链表内容为空返回true.反之就返回false.

3.12计算链表长度

//计算链表长度
size_t LTSize(LTNode* phead)
{
	assert(phead);

	size_t count = 0;
	LTNode* cur = phead->next;

	while (cur != phead)
	{
		count++;
		cur = cur->next;
	}
	return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

和查找的步骤差不多，从头节点下一个节点开始一直到末尾，每走一步，新定义的变量就++。最后结果返回。

3.13删除链表

//删除链表
void LTDostroy(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;

	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

每次在删除cur指向的节点时，都应该把此时节点的下一个节点的位置保存下来，否则删除之后就找不到下一个节点的位置了。
在循环里，cur指针一直往后走，直到删除掉最后一个节点时结束，跳出循环后，要记得把头节点的空间也释放掉。