【数据结构初阶（3）】双向带头结点循环链表

Ⅰ 概念及结构

• 双向链表的每一个结点中不仅仅只有指向后继结点的 next 指针，还有指向其前趋结点的 prev 指针。
• 双向链表的头节点的 prev 指针域指向链表的尾结点，双向链表的尾结点的 next 域指向链表的头结点，因此，在双向链表中不存在指向 NULL 的指针。
• 在带头结点的双向链表中，头节点不存储有效数据。因此，即使链表为空，双向链表中还要有一个头节点，头结点的前趋和后继指针都指向自己。

Ⅱ 基本操作实现

1. 结点的定义

• 双向循环链表的结点结构应该包含三部分：存储有效数据的数据域、存储前趋结点的前趋指针域、存储后继结点的后继指针域。

typedef int LTDataType;		//数据域的数据类型

typedef struct ListNode		//双向链表结点
{
	LTDataType data;		//存储有效数据
	struct ListNode* prev;	//存储前趋结点
	struct ListNode* next;	//存储后继结点
}ListNode;

2. 创建头节点

• 只有一个头结点时，链表是空的。
• 头结点的前趋和后继都指针头节点本身。

代码实现

// 创建返回链表的头结点.
ListNode* ListCreate()
{
	ListNode* head = (ListNode*)malloc(sizeof(ListNode));

	if (NULL == head)
	{
		perror("malloc");
		exit(-1);
	}

	head->prev = head;	//头结点的前趋指针指向自己
	head->next = head;	//头结点的后继指针指向自己

	return head;		//返回创建好的头结点
}

3. 创建新结点

实现方法

• 创建除了头结点之外的新结点，这种结点存储有效数据。
• 在创建新结点时，前趋和后继指针域都不指针任何结点，暂时都为 NULL。

代码实现

// 创建一个新结点
ListNode* BuySListNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));

	if (NULL == newnode)
	{
		perror("malloc");
		exit(-1);
	}

	newnode->data = x;		//新结点数据域存储传来的数据
	newnode->next = NULL;	//新结点前趋指针暂时指向 NULL
	newnode->prev = NULL;	//新结点后继指针暂时指向 NULL

	return newnode;			//返回创建好的新结点
}

4. 双向链表销毁

实现方法

先定义一个 cur 指针指向头结点的后继结点，删除链表时有两种情况。

1. 链表为空：此时头节点的后继结点就是头结点本身，直接释放头结点即可。
2. 链表非空：使用一个指针 next 指向 cur 的下一个结点，然后删除 cur 指向的结点，再将 cur 指向 cur 的下一个结点，直到删的只剩头结点为止。

代码实现

// 双向链表销毁
void ListDestory(ListNode* pHead)
{
	assert(pHead);

	ListNode* cur = pHead->next;		//指向头结点的下一个结点
	
	while (cur != pHead)			
	{
		ListNode* next = cur->next;		//存储当前结点的下一个结点的地址
		free(cur);						//释放当前结点
		cur = next;						//让 cur 指向 cur 的下一个结点
	}

	free(pHead);						//不管链表开始是不是为空最后都会释放头结点
	pHead = NULL;
}

5. 双向链表打印

实现方法

• 定义一个 cur 指针指向头节点的下一个结点 (head->next)，输出 cur 指向的结点的数据域的内容，然后让 cur 指向下一个结点。
• 只有在 cur 指针指向头结点的时候，打印才会结束。如果链表本身为空，则 cur 一开始就会指向头结点，自然什么都不会打印。

代码实现

// 双向链表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);					//传过来的不是个空指针

	ListNode* cur = pHead->next;	//指向头结点的下一个结点（首结点）

	printf("头结点<->");
	while (cur != pHead)			//不指向头结点时说明链表中还有结点未遍历到
	{
		printf("%d<->", cur->data);	//输出结点数据域的内容
		cur = cur->next;			//指向当前结点的下一个结点
	}
	printf("\n");
}

6. 双向链表尾插

实现方法

代码实现

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);							//传过来的不是个空指针

	ListNode* newnode = BuySListNode(x);	//先创建要插入的新结点
	ListNode* tail = pHead->prev;			//找到双向链表的尾结点

	tail->next = newnode;					//尾结点的后继指针指向新结点
	newnode->prev = tail;					//新结点的前趋指针指向尾结点
	newnode->next = pHead;					//新结点的后继结点指向头结点
	pHead->prev = newnode;					//头结点的前趋指针指向新结点
}

7. 双向链表尾删

实现方法

代码实现

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	assert(pHead->next != pHead->prev);	//不是空链表

	ListNode* tail = pHead->prev;		//找到链表的尾结点
	ListNode* tail_prev = tail->prev;	//找到尾结点的前一个结点
	pHead->prev = tail_prev;			//让头结点的前趋指针指向尾结点的前一个结点
	tail_prev->next = pHead;			//让尾结点的前一个结点的后继指针指向头结点

	free(tail);							//删除尾结点
	tail = NULL;
}

8. 双向链表头插

实现方法

• 定义一个 first 指针指向链表的首结点，之后就随便插入新结点了。
• 因为已经用 first 指针保存了首结点的地址，所以不用担心会因为插入顺序导致出现 BUG。

代码实现

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

	ListNode* newnode = BuySListNode(x);	//创建新结点
	ListNode* first = pHead->next;			//保存首结点地址

	pHead->next = newnode;					//头结点后继指向新结点
	newnode->prev = pHead;					//新结点前趋指向头结点
	newnode->next = first;					//新结点后继指向首结点
	first->prev = newnode;					//首结点前趋指向新结点
}

9. 双向链表头删

实现方法

1. 定义一个 first 指针指向首结点，再定义一个 second 指针指向第二个结点。
2. 让头结点后继指向第二个结点，让第二个结点前趋指向头结点。
3. 最后即可删除 first 指向的首结点。

代码实现

// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	assert(pHead->next != pHead->prev);	//链表不为空

	ListNode* first = pHead->next;		//指向首结点
	ListNode* second = first->next;		//指向第二个结点

	pHead->next = second;				//头结点的后继指针指向第二个结点
	second->prev = pHead;				//第二个结点的前趋指针指向头结点

	free(first);						//释放首结点
	first = NULL;
}

10. 双向链表查找

• 使用一个 cur 指针遍历链表，返回第一个出现要查找的数据的结点的地址。

代码实现

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);

	ListNode* cur = pHead->next;	//链表不为空时指向首结点，链表为空时最后直接返回 NULL

	while (cur != pHead)			//链表还没彻底遍历一遍时继续指向循环体内容
	{
		if (cur->data == x)			//结点数据域等于要查找的数
		{
			return cur;				//返回出现要查找的数据的结点地址
		}

		cur = cur->next;
	}

	return NULL;
}

11. 在指定 pos 位置前插入新结点

获取 pos 位置

• 利用双向链表查找找到要插入的 pos 位置。

实现方法

• 定义一个 posprev 指针保存 pos 结点的前一个结点，之后可按照任意顺序插入新结点

代码实现

// 双向链表在 pos 的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);							//传过来的不是空指针
	
	ListNode* newnode = BuySListNode(x);	//创建新结点
	ListNode* posprev = pos->prev;			//保存 pos 的前一个结点

	posprev->next = newnode;				//前一个结点的 next 域指向新结点
	newnode->prev = posprev;				//新结点的 prev 域指向前一个结点
	newnode->next = pos;					//新结点的 next 域指向 pos 结点
	pos->prev = newnode;					//pos 的 prev 域指向新结点
}

功能特点

• 如果 pos 是头结点的话，那么 pos 的前一个结点就是链表的尾结点，执行该函数就会变成对链表执行尾插。

• 如果 pos 是首结点的话，执行该函数功能就相当于直接对链表执行头插。

12. 删除指定 pos 位置的结点

获取 pos 位置

• 利用双向链表查找找到要删除的 pos 位置。

实现方法

• 定义一个 posprev 指针指向 pos 位置的前一个结点，定义一个 posnext 指针指向 pos 位置的后一个结点。
• 将 posprev 结点的后继指向 posnext，将 posnext 结点的前趋指向 posprev，最后再删除 pos 结点即可。

代码实现

// 双向链表删除 pos 位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	
	ListNode* posprev = pos->prev;	//保存 pos 位置结点的前趋结点
	ListNode* posnext = pos->next;	//保存 pos 位置结点的后继结点

	posprev->next = posnext;		//pos 前一个结点的后继指向 pos 的后一个结点
	posnext->prev = posprev;		//pos 后一个结点的前趋指向 pos 的前一个结点

	free(pos);
	pos = NULL;
}

功能特点

• 如果 pos 是尾结点，该函数执行的功能就是尾删操作。
• 如果 pos 是首结点，该函数执行的功能就是头删操作。

Ⅲ 十分钟手搓链表

• 根据在指定 pos 位置前插入新结点和删除指定 pos 位置的结点，这两个函数的功能特点可以直接对进行函数的头尾插和头尾删功能。

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

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

1. 指向头尾插功能

• 头插：直接将 pos 定为首结点即可

ListInsert(pHead->next, xxx);	//首结点为 pos，执行的是头插

• 尾插：直接将 pos 定为头结点即可

ListInsert(pHead, xxx);			//头结点为 pos，执行的是尾插

2. 执行头尾删功能

• 头删：直接将 pos 定为首结点即可

ListErase(pHead->next)			//首结点为 pos，执行的是头删

• 尾删：直接将 pos 定位尾结点即可

ListErase(pHead->prev)			//尾结点为 pos，执行的是尾删