【数据结构】—带头双向循环链表的实现（完美链表）

前言

链表结构一共有八种形式，在前面的文章里已经讲完了不带头单向非循环链表的实现，但是我们发现该链表实现尾插与尾删时比较麻烦，要先从头节点进行遍历，找到尾节点，时间复杂度为O(N)，而本次所讲的带头双向循环单链表，则可以直接找到尾节点。

虽然该链表看起来特别复杂，但实际上真正实现起来很简单，并且用起来真的超爽，还能拿来吹吹牛皮。唬一唬一知半解的外行人。

链表的实现

typedef int LTDataType;//类型重命名
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* phead = (ListNode*)malloc(sizeof(ListNode));
	if (phead == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	phead->_data = x;
	phead->_next = NULL;
	phead->_prev = NULL;
	return phead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

链表初始化

空表状态下应该是如下图这样的，因为它是带头的循环链表，所以第一个节点不用来存储有效数据。它的next与prev都指向自己就说明该链表是空表。

ListNode* InitListNode()
{
	ListNode* phead = BuyListNode(-1);//这里的-1不是有效数据
	phead->_next = phead;
	phead->_prev = phead;
	return phead;
}
1
2
3
4
5
6
7

尾插与尾删

尾插

尾插首先要找到尾节点，这里的尾节点很容易找到，就是头节点的prev指向的节点。如下：

这里的尾插也满足空表情况下进行尾插。所以该代码没问题

代码

void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode = BuyListNode(x);//新节点创建
	ListNode* tail = pHead->_prev;//找到尾节点
	tail->_next = newnode;//尾节点连接新节点
	newnode->_prev = tail;//新节点的prev与尾节点连接
	pHead->_prev = newnode;//头节点的prev指向新节点
	newnode->_next = pHead;//新节点的next指向头节点，至此，新节点成了为节点
}
1
2
3
4
5
6
7
8
9
10

尾删

尾删的实现也很简单，找到尾节点即可，再让尾节点的前一个节点与头节点连接，最后释放尾节点即可。如下：

这里要注意的就是空表情况下是不可以继续删除的。

代码

void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	assert(pHead->_next!=pHead);//空表情况下不能继续删
	//找尾
	ListNode* tail = pHead->_prev;
	//记录尾部前一个节点
	ListNode* tailprev = tail->_prev;
	tailprev->_next = pHead;
	pHead->_prev = tailprev;
	//释放尾部
	free(tail);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

测试

//链表初始化+尾插尾删
void ListNodeTest1()
{
	//初始化
	ListNode* phead=InitListNode();
	//尾插
	ListPushBack(phead, 1);
	ListPushBack(phead, 2);
	ListPushBack(phead, 3);
	ListPushBack(phead, 4);
	ListPushBack(phead, 5);
	ListPrint(phead);//1 2 3 4 5
	//尾删
	ListPopBack(phead);
	ListPopBack(phead);
	ListPopBack(phead);
	ListPrint(phead);//1 2
	//ListPopBack(phead);
	//ListPopBack(phead);
	//ListPopBack(phead);
	//ListPrint(phead);//error
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

头插与头删

头插

头插的实现在这里也很简单，先找到有效节点的头节点（即PHead的next指向的第一个节点），然后将新节点的next指向该节点，该节点的prev指向新节点，再让PHead的next指向新节点，新节点的prev指向PHead即可。（看起来可能有些乱，但是画图就特别容易理解）

代码

//头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	//找到头节点
	ListNode* first = pHead->_next;
	ListNode* newnode = BuyListNode(x);//新节点创建
	//连接
	newnode->_next = first;
	first->_prev = newnode;
	pHead->_next = newnode;
	newnode->_prev = pHead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

头删

头删的实现与尾删异曲同工，找到有效节点的头节点，保存下一个节点，将PHead与之连接，然后再释放有效节点的头节点即可。

这里依然要注意，空表情况不能进行删除

代码

void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	assert(pHead->_next != pHead);//
	//找到头节点以及头节点后面的节点
	ListNode* first = pHead->_next;
	ListNode* second = first->_next;
	//进行连接
	pHead->_next = second;
	second->_prev = pHead;
	free(first);//释放
}
1
2
3
4
5
6
7
8
9
10
11
12

测试

void ListNodeTest2()
{
	//初始化
	ListNode* phead = InitListNode();
	//头插
	ListPushFront(phead, 1);
	ListPushFront(phead, 2);
	ListPushFront(phead, 3);
	ListPushFront(phead, 4);
	ListPushFront(phead, 5);
	ListPrint(phead);//5 4 3 2 1
	//头删
	ListPopFront(phead);
	ListPopFront(phead);
	ListPopFront(phead);
	ListPrint(phead);// 2 1
	//ListPopFront(phead);
	//ListPopFront(phead);
	//ListPopFront(phead);
	//ListPrint(phead);// error
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

查找数据

这里进行查找数据，依然还是遍历整个链表即可。没啥可说的，如下：

ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* 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

在任意位置的插入与删除

pos位置插入

这里与头插的操作相比，两者其实也没啥区别。头插是找有效节点的头节点，在这里我们把pos看作该节点，把pos的prev指向的节点看作是PHead节点，这样的话，原理就与头插相同了。

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	//pos前面的节点
	ListNode* posprev = pos->_prev;
	//新节点
	ListNode* newnode = BuyListNode(x);
	//连接即可
	posprev->_next = newnode;
	newnode->_prev = posprev;
	newnode->_next = pos;
	pos->_prev = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

pos位置删除
原理也是与头删相似，只要画图即可理解。这里就不一一进行解析了，大家根据代码画图纸就行。不过需要注意的是，空表不可进行删除。

void ListErase(ListNode* pos)
{
	assert(pos);
	pos->_prev->_next = pos->_next;
	pos->_next->_prev = pos->_prev;
	free(pos);
}
1
2
3
4
5
6
7

链表的销毁

这里的销毁也是需要进行遍历链表，先保存下一个链表，再释放当前链表。将有效节点销毁后，再将PHead销毁。

代码

void ListDestory(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->_next;
	while (cur != pHead)
	{
		//找到cur后面的节点
		ListNode* curnext = cur->_next;
		free(cur);//释放
		cur = curnext;
	}
	//释放pHead
	free(pHead);
}
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

测试

//双向链表查找、任意位置插入、删除
ListNodeTest3()
{
	ListNode* phead = InitListNode();
	ListPushFront(phead, 1);
	ListPushFront(phead, 2);
	ListPushFront(phead, 3);
	ListPushFront(phead, 4);
	ListPushFront(phead, 5);
	//查找
	ListNode* pos = ListFind(phead, 2);
	//pos->_data = 50;
	//ListPrint(phead);// 5 4 3 50 1
	// 双向链表在pos的前面进行插入
	ListInsert(pos, 0);
	ListPrint(phead);// 5 4 3 0 2 1

	//删除pos位置
	ListErase(pos);
	ListPrint(phead);// 5 4 3 0 1
	//链表销毁
	ListDestory(phead);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

总结

该链表用起来真的很爽，能直接找到头尾节点，并且因为有头的存在，就不需要考虑是否为空表的情况下的插入，就不用改变PHead，所以就不用像之前的单链表一样，得传二级指针。真的是链表中的完美存在，不过在进行删除操作时，一定要考虑空表情况下不可进行删除。因此要加个assert进行断言。