【数据结构】带头双向循环链表_循环双链表的终止条件

双向链表的结构

1.双向循环链表的每一个结点都包括以下部分：

2.头结点中的data域没有实际意义

3.双向循环链表
例如：

基础操作

数据结构

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

创建结点

由于链表是动态开辟空间，所以每次插入元素是都需要从堆上申请空间。
具体操作细节如下：

//创建一个节点
ListNode* BuyListNode(LTDataType x)
{
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	if (NULL == newNode)
	{
		return NULL;
	}
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

创建头结点

对于头结点来说，创建头结点时与其他结点略有不同，它的data域没有实际意义。

// 创建返回链表的头结点.
ListNode* ListCreate()
{
	//头结点的data域无实际意义
	ListNode* head = BuyListNode(0);
	head->next = head;
	head->prev = head;
	return head;
}
1
2
3
4
5
6
7
8
9

双向链表的销毁

由于链表的每一个结点都是从堆上动态开辟的，所以在使用完毕后必须要手动的释放，否则就会产生内存泄漏。
具体细节分析见下图：

注意传参问题。其他的都是一些常规操作！
具体实现代码如下：

// 双向链表销毁
void ListDestory(ListNode** pHead)
{
	assert(pHead);
	
	ListNode* delNode = (*pHead)->next;
	while (delNode != *pHead)
	{
		(*pHead)->next = delNode->next;
		delNode->next->prev = (*pHead);
		free(delNode);
		delNode = (*pHead)->next;
	}
	//最终剩下头结点没有释放
	free(*pHead);
	*pHead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

双向链表的打印

循环遍历整个链表，同时输出每个节点的data域内容。
注意：循环终止条件的确定
由于是循环双链表 ，所以当输出结点与头结点相等时就已经完成一趟的遍历。

// 双向链表打印
void ListPrint(ListNode* pHead)
{
		

	if (pHead == pHead->next)
	{
		printf("空链表，无结点！\n");
		return;
	}
	ListNode* cur = pHead->next;
	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

双链表的尾插

在链表的末尾插入一个结点，要经历以下步骤：
1.创建新节点
2.找到原链表的最后一个结点
3.改变链表相关指针的指向，使得新结点成为链表的最后一个结点
前两步可以很容易的实现。我们具体分析一下第三步：

可以看到，在双向循环链表中尾插一个结点，需要改变四个指针的指向，并且具有一定的先后顺序。
接下来看具体实现代码

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);

	ListNode* newNode = BuyListNode(x);
	newNode->next = pHead;
	newNode->prev = pHead->prev;
	pHead->prev->next = newNode;
	pHead->prev = newNode;
}
1
2
3
4
5
6
7
8
9
10
11

双向链表的尾删

想要删掉末尾结点，需要有以下操作步骤：
1.找到末尾结点

2.由于末尾结点将要被删除，所以应当改变相关指针，使得原链表的倒数第二个结点成为新链表的末尾结点。

3.释放要删除结点的内存空间。

对于双向循环链表来说，1,3两步都很容易实现，我们具体分析一下步骤2
通过改变指针的指向，从而将倒数第二个结点（下图的结点3）作为新链表的末尾结点。

完整操作见代码

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);

	if (pHead ==  pHead->next)
	{
		printf("链表为空，无法删除！\n");
		return;
	}

	ListNode* delNode = pHead->prev;
	pHead->prev = delNode->prev;
	delNode->prev->next = pHead;
	free(delNode);
	delNode = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

双链表的头插

想要头插一个结点，需要进行如下几步操作：
1.为要插入的结点申请空间

2.找到原链表的第一个结点

3.调整相关指针指向，让新结点的prev与头结点相连，新结点的next与原链表的首结点相连

着重分析步骤3：
要想插入一个结点，我们就要对原链表中的相关指针进行修改，从而将新结点加进去。具体实现过程见下图

下面是总体实现的代码

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newNode = BuyListNode(x);

	newNode->next = pHead->next;
	newNode->prev = pHead;
	pHead->next->prev = newNode;
	pHead->next = newNode;
}

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

双链表的头删

步骤：
1.找到第一个结点、

2.修改指针，使得第二个结点与头结点相连

3.释放原来的结点（步骤1找到的结点）

主要分析步骤2的实现过程：

完整实现代码如下

// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	if (pHead == pHead->next)
	{
		printf("没有结点，无法删除！\n");
		return;
	}
	ListNode* delNode = pHead->next;

	pHead->next = delNode->next;
	delNode->next->prev = pHead;
	free(delNode);
	delNode = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

双向链表的查找

主体思想与链表的输出一致，循环遍历链表，在遍历的过程中判断每一个结点的data域与目标值是否相等，若相等，则返回该结点的地址，退出循环。如果遍历链表一遍后仍然没有找到，难么就返回NULL值。
这个就不画图分析了，直接上代码

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	//循环遍历比较data域，注意循环的控制条件
	ListNode* cur  = pHead->next;
	while (pHead != cur)
	{
		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

双向链表在pos的前面进行插入

步骤：
1.为插入的结点开辟空间
2.修改相关指针，插入链表
具体过程如下图所示

上图分析的比较详细，直接上实现代码

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);

	ListNode* newNode = BuyListNode(x);
	newNode->next = pos;
	newNode->prev = pos->prev;
	pos->prev->next = newNode;
	pos->prev = newNode;
}
1
2
3
4
5
6
7
8
9
10
11

双向链表删除pos位置的节点

要删除一个结点，那么我们要将它的前一个节点与后一个结点建立关系后，再将要删除结点直接释放掉就可以。就如下图展示的这样

操作都比较简单，就直接上代码了

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);

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

改写相关函数

仔细观察上述代码，我们可以发现，其实对链表进行尾插、尾删、头插、头删都可以看做是对链表任意位置的插入与删除操作。所以我们可以根据任意位置的插入与删除函数对前面的尾插、尾删、头插、头删函数进行改写！

尾插

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	//改写
	ListInsert(pHead,x);

}
1
2
3
4
5
6
7
8

尾删

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);

	if (pHead ==  pHead->next)
	{
		printf("链表为空，无法删除！\n");
		return;
	}
	ListErase(pHead->prev);
}
1
2
3
4
5
6
7
8
9
10
11
12

头插

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListInsert(pHead->next, x);

}
1
2
3
4
5
6
7

头删

// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	if (pHead == pHead->next)
	{
		printf("没有结点，无法删除！\n");
		return;
	}
	ListErase(pHead->next);

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

完整代码

详情请点击 我的Git

总结

对于带头结点的双向循环链表来说，它的特点比较明显：
1.头结点将链表的首尾结点紧密的联系起来，增加了寻找结点的效率

2.链表内部前后结点也更为灵活，可以随意访问，在执行插入、删除等操作时，效率很高，只需要改变对应指针的指向就能实现。

3.支持任意位置时间复杂度为O(1)的插入和删除，不需要扩容、不存在空间浪费。

各位看官们三连支持一波啊·~~~