数据结构-带头双向循环链表_带头指针的双向循环链表

目录

链表的分类

带头双向循环链表的概念及结构

概念

结构

带头双向循环链表的基本操作

初始化ListInit

尾插ListPushBack

头插ListPushFront

尾删ListPopBack

​头删ListPopFront

插入ListInsert

删除ListErase

查找ListFind

修改ListModify

打印ListPrint

长度ListSize

销毁ListDestroy

判空ListEmpty

动态顺序表与带头双向循环链表的比较

代码

---

链表的分类

   链表的种类非常丰富，有带头结点的或不带头结点的，有单向的或双向的，有循环的或非循环的，这样组合起来有2*2*2=8种链表结构。

   虽然有这么多的链表结构，但是我们实际中最常用的还是两种结构：

   最后我们再了解一下头结点与头指针的概念：不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点是带头链表中第一个结点，该结点通常不存储数据。 

   引入头结点可以带来两个优点：1.由于第一个数据结点的位置被存储在头结点的指针域中，因此在链表的第一个位置上的操作和在链表其他位置上的操作一致，无须进行特殊处理。2.无论链表是否为空，其头指针都指向头结点，因此空表与非空表的处理也得到统一。

---

带头双向循环链表的概念及结构

概念

   链表是一种物理结构上非连续、非顺序的存储结构，数据元素的逻辑结构顺序是通过链表
中的指针链接次序实现的 。

   而带头双向循环链表是链表组合中最复杂的结构。

• 因为是双向的，所以每个结点中有prev指针与next指针，其prev指针指向其结点的前一个结点，next指针指向其结点的后一个结点。
• 并且拥有头结点，其头结点的next指向第一个数据结点，prev指向最后一个数据结点。
• 又因为是循环结构，所以最后一个数据结点的next指向头结点。

结构

   带头双向循环链表的结点需要存储前一个结点地址的指针prev，存储后一个结点地址的指针next以及存储数据的data，这样的带头双向循环链表的结点结构才算完整。

---

带头双向循环链表的基本操作

初始化ListInit

   带头双向循环链表的初始化操作本质上就是开辟一个头结点并将头指针指向开辟好的头结点。    有两种实现方法：1.将头指针传给ListInit在函数体内把头指针的指向改为头结点，所以需要用到二级指针，传头指针的地址才能改变头指针的指向。2.直接将开辟好的头结点地址作为返回值来改变头指针的指向。

   在这之前我们先实现一个开辟结点的函数，并将开辟好的结点中的prev和next指向自己。

尾插ListPushBack

   尾插就是在链表的最后一个数据结点的后面增添一个新结点，本质上就是将最后一个数据结点的next指向newNode，而newNode的prev指向最后一个数据结点，因为是循环结构，还需将头结点的prev指向newNode，而newNode的next指向头结点。

   与单链表相比，我们不需要遍历寻找最后一个数据结点，因为头结点的prev就是指向最后一个数据结点。

   当链表为空时，其操作也是一样的：

头插ListPushFront

   头插的操作就是将第一个数据结点的prev指向newNode，而newNode的next指向第一个数据结点，头结点的next指向newNode，而newNode的prev指向头结点。

   当链表为空时，其操作也是一样的。

尾删ListPopBack

   尾删的操作就是将最后一个数据结点的前一个结点的next指向头结点，而头结点的prev指向最后一个数据结点的前一个结点，然后释放掉最后一个数据结点。如果链表只剩下一个数据结点进行删除的话，操作也是一样的，尾删完最后一个结点就会回到头结点的next与prev指向自己的场景。

头删ListPopFront

   头删的操作就是将第一个数据结点的下一个结点的prev指向头结点，而头结点的next指向第一个数据结点的下一个结点，然后释放掉第一个数据结点。如果链表只剩下一个数据结点进行删除的话，操作也是一样的，头删完最后一个结点就会回到头结点的next与prev指向自己的场景。

插入ListInsert

   插入就是在pos位置前插入一个新结点，因为该链表为带头双向循环链表，所以我们可以直接找到pos位置的前一个结点，而不需要遍历找pos位置的前一个结点。具体操作就是将pos位置的前一个结点的next指向newNode,而newNode的prev指向pos位置的前一个结点，再将pos的prev指向newNode，而newNode的next指向pos即可完成插入操作。

    实现插入操作后，我们的尾插与头插可以复用插入操作：

删除ListErase

   删除就是将pos位置的结点释放掉。具体操作就是将pos位置的前一个结点的next指向pos位置的后一个结点，而pos位置的后一个结点的prev指向pos位置的前一个结点，然后释放掉pos位置的结点。

    实现删除操作后，我们的尾删与头删可以复用删除操作：

查找ListFind

   按值查找就是将链表遍历一遍，并将查到存储该值的结点地址返回。

修改ListModify

   修改操作就是将pos位置的data数据改为x数据。

   将链表中所有存储2的结点改为存储0：

打印ListPrint

   之前单链表遍历的结束条件是curr是否等于NULL，因为最后一个数据结点的next指向NULL。而带头双向循环链表的遍历结束条件是curr是否等于phead，因为最后一个数据结点的next指向phead。 

长度ListSize

   求大小的操作同样是将链表遍历一遍，通过计数来求链表的长度。

   另一种求链表长度的方法： 将头指针与一个整形size封装到一个结构体中，当链表增加数据时size++，若链表减少数据时size--这样就不需要遍历。

销毁ListDestroy

   销毁的操作就是反复调用ListErase将所有的数据结点释放，最后将头结点也释放掉，调用ListDestroy之后记得将头指针置空。

判空ListEmpty

   如果带头双向循环链表为空返回true，不为空返回false；当头结点的next与prev都指向自身则说明链表为空。

---

动态顺序表与带头双向循环链表的比较

   动态顺序表

• 优点：支持随机访问，缓存利用率高
• 缺点：头部或者中间位置插入删除效率低，扩容有一定程度的性能消耗，也可能存在一定程度的空间浪费
• 应用场景：频繁访问，高效存储

   带头双向循环链表

• 优点：任意位置插入和删除的时间复杂度为O(1)，按需申请释放
• 缺点：不支持随机访问，缓存利用率低，会造成一定的内存碎片
• 应用场景：频繁的任意位置插入删除

---

代码

// 头文件
typedef int ListDataType; // 数据的类型
 
typedef struct ListNode
{
	struct ListNode* prev; // 指向前一个结点 
 
	ListDataType data; // 存储数据
 
	struct ListNode* next; // 指向后一个结点
}ListNode;
 
struct List
{
	ListNode* phead; // 头指针
	int size; // 记录长度
};
 
//void ListInit(ListNode** pphead);
ListNode* ListInit(); // 初始化
void ListPushBack(ListNode* phead,ListDataType x); // 尾插
void ListPushFront(ListNode* phead, ListDataType x); // 头插
void ListPopBack(ListNode* phead); // 尾删
void ListPopFront(ListNode* phead); // 头删
void ListPrint(ListNode* phead); // 打印
void ListInsert(ListNode* pos,ListDataType x); // 任意位置插入
void ListErase(ListNode* pos); // 任意位置删除
ListNode* ListFind(ListNode* phead,ListDataType x); // 按值查找
void ListModify(ListNode* pos, ListDataType x); // 修改
int ListSize(ListNode* phead); // 求长度
void ListDestroy(ListNode* phead); // 销毁
bool ListEmpty(ListNode* phead); //判空
 
//源文件
void ListPrint(ListNode* phead) // 遍历打印带头双向循环链表
{
	assert(phead);
 
	ListNode* curr = phead->next;
 
	while (curr != phead)
	{
		printf("%d ", curr->data);
		curr = curr->next;
	}
 
	printf("\n");
}
 
//void ListLnit(ListNode** pphead) // 链表的初始化---创建头结点并让头指针指向头结点
//{
//	assert(pphead);
//
//	ListNode* newNode = BuyListNode(0); 
//
//	*pphead = newNode;
//}
 
ListNode* BuyListNode(ListDataType x) // 在堆上创建一个结点
{
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
 
	if (!newNode)
	{
		perror("malloc");
		exit(-1);
	}
 
	newNode->data = x;
	newNode->prev = newNode; // 让结点中的prev与next指向自己
	newNode->next = newNode;
 
	return newNode; // 返回创建成功的结点的地址
}
 
ListNode* ListInit() // 链表的初始化---创建头结点并返回头结点的地址
{
	ListNode* newNode = BuyListNode(0);
 
	return newNode;
}
 
void ListPushBack(ListNode* phead, ListDataType x) // 尾插
{
	assert(phead);
 
	ListInsert(phead, x); // 尾插
 
	/*ListNode* newNode = BuyListNode(x);
	ListNode* tail = phead->prev;
	tail->next = newNode;
	newNode->prev = tail;
	phead->prev = newNode;
	newNode->next = phead;*/
 
	/*ListNode* newNode = BuyListNode(x);
	phead->prev->next = newNode;
	newNode->prev = phead->prev;
	phead->prev = newNode;
	newNode->next = phead;*/
}
 
void ListPushFront(ListNode* phead, ListDataType x) // 头插
{
	assert(phead);
 
	ListInsert(phead->next, x); // 头插
 
	/*ListNode* newNode = BuyListNode(x);
	ListNode* temp = phead->next;
	temp->prev = newNode;
	newNode->next = temp;
	phead->next = newNode;
	newNode->prev = phead;*/
 
	/*ListNode* newNode = BuyListNode(x);
	phead->next->prev = newNode;
	newNode->next = phead->next;
	phead->next = newNode;
	newNode->prev = phead;*/
}
 
void ListPopBack(ListNode* phead) // 尾删
{
	assert(phead);
	if (phead->next == phead && phead->prev == phead) // 如果链表为空不需要删除
	{
		assert(0);
		return;
	}
 
	ListErase(phead->prev); // 尾删
 
	/*ListNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);*/
 
	/*ListNode* del = phead->prev;
	phead->prev->prev->next = phead;
	phead->prev = phead->prev->prev;
	free(del);*/
}
 
void ListPopFront(ListNode* phead) // 头删
{
	assert(phead);
	if (phead->next == phead && phead->prev == phead) // 链表为空则不需要删除
	{
		assert(0);
		return;
	}
 
	ListErase(phead->next); // 头删
 
	/*ListNode* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;
	free(del);*/
 
 
	/*ListNode* del = phead->next;
	phead->next->next->prev = phead;
	phead->next = phead->next->next;
	free(del);*/
}
 
void ListInsert(ListNode* pos, ListDataType x) // 插入---在pos位置前插入
{
	assert(pos);
 
	ListNode* newNode = BuyListNode(x);
 
	ListNode* prev = pos->prev; 
 
	prev->next = newNode;
	newNode->prev = prev;
	pos->prev = newNode;
	newNode->next = pos;
 
	/*pos->prev->next=newNode;
	newNode->prev=pos->prev;
	pos->prev=newNode;
	newNode->next=pos;*/
}
 
void ListErase(ListNode* pos) // 删除---删除pos位置的结点
{
	assert(pos); // 不需要额外检查链表是否为空，因为pos存在就证明链表不为空。
	
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
 
	prev->next = next;
	next->prev = prev;
	free(pos);
 
	/*pos->prev->next=pos->next;
	pos->next->prev=pos->prev;
	free(pos);*/
}
 
ListNode* ListFind(ListNode* phead, ListDataType x) // 按值查找
{
	assert(phead);
 
	ListNode* curr = phead->next;
 
	while (curr != phead) 
	{
		if (curr->data == x)
			return curr;
 
		curr = curr->next;
	}
 
	return NULL; // 没有找到返回空指针
}
 
void ListModify(ListNode* pos, ListDataType x) // 修改---将pos位置的data数据改为x
{
	assert(pos);
	pos->data = x;
}
 
int ListSize(ListNode* phead) // 求长度（元素个数）
{
	assert(phead);
 
	int size = 0;
 
	ListNode* curr = phead->next;
 
	while (curr != phead)
	{
		size++;
		curr = curr->next;
	}
 
	return size;
}
 
void ListDestroy(ListNode* phead) // 销毁
{
	assert(phead);
 
	ListNode* curr = phead->next;
 
	while (curr != phead)
	{
		ListNode* next = curr->next;
		ListErase(curr);
		curr = next;
	}
 
	free(phead);
}
 
bool ListEmpty(ListNode* phead) // 判断带头双向循环链表是否为空
{
	assert(phead);
 
	return phead->next == phead && phead->prev == phead; // 为空返回true否则返回false
}