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

带头双向链表的基本概念

带头双向循环链表：结构最复杂，一般用在单独存储数据。

实际中使用的链表数据结构，都是带头双向循环链表。

另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了

---

---

链表带头和不带头的区别

• ==不带头==：用头指针，指针指向的就是第一个结点
  • 因为函数中可能要修改一级指针plist，所以我们要传plist的地址进行操作，即要使用二级指针
• ==带头==：plist指向的就是哨兵位结点，这个结点不存储有效数据。哨兵位的next，是第一个结点
  • 因为函数中不会修改plist，插入和删除都不会改变plist，因此不需要使用二级指针。插入删除改变的是plist指向的哨兵位的内容，plist本身不被修改

---

*函数内部要改变int类型的变量 ->传int **(传int的地址)

函数内部要改变int*类型变量->传int**(传int*的地址)

---

我们选择的是带头的链表，==哨兵位的next指针指向的才是第一个结点==

---

1.0-带头双向循环链表的结构

// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;//存放数据
	struct ListNode* next;//前驱指针
	struct ListNode* prev;//后继指针
}ListNode;

---

1.1-生成哨兵位结点

初始化哨兵位的prev和next指针都是指向自己的

---

方法1：通过返回值带回去

// 创建返回链表的头结点.
ListNode* plist =ListCreate();

//方法1：通过返回值带回去
ListNode* ListCreate()
{
	//哨兵位结点
	ListNode* plist = (ListNode*)malloc(sizeof(ListNode));
	plist->next = plist;
	plist->prev = plist;
	//头结点的data不存储有效数据
	return plist;
}

---

方法2：外面传二级指针

ListNode* plist ;
ListCreate(&plist);

//方法二：外面传二级指针
void ListCreate(ListNode** pphead)
{
	(*pphead) = (ListNode*)malloc(sizeof(ListNode));
	(*pphead)->prev = *pphead;
	(*pphead)->next = *pphead;
}

---

1.1.1-新建结点

//新建结点
ListNode* ListNewNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->data = x;
	return newnode;
}

---

1.2-双向链表打印

遍历链表打印即可，谨记：哨兵位的next指针指向的才是第一个结点

循环结束条件：cur ！= pHead

当cur回到哨兵位，跳出循环结束

// 双向链表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);
	//遍历打印
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

---

1.3-双向链表尾插

尾插数据：

pHead pHead newnode 三者进行链接

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	//pHead->prev就是尾
	//pHead tail newnode 进行链接
	ListNode* tail = pHead->prev;
	ListNode* newnode = ListNewNode(x);
	pHead->prev = newnode;
	newnode->next = pHead;
	tail->next = newnode;
	newnode->prev = tail;
	//ListInsert(pHead, x);
}

---

1.4-双向链表尾删

就算删完了，哨兵位指针也不为空。

断言pHead只是怕别人传空指针过来

注意：尾删要先找到尾的前一个结点和哨兵位的next进行链接，然后释放尾结点

---

==删除时，不能把哨兵位也删除了 ->assert(pHead->next !=pHead)==

断言条件为假：报错终止 条件为真：继续执行

//双向链表尾删
void ListPopBack(ListNode* pHead)
{
	//尾删->即删除pHead->prev结点
	assert(pHead);
	////哨兵位不能删除
	assert(pHead->next != pHead);

	ListNode* tail = pHead->prev;
	ListNode* tailPrev = tail->prev;
	free(tail);
	tailPrev->next = pHead;
	pHead->prev = tailPrev;
	//ListErase(pHead->prev);
}

---

1.5-双向链表头插

头插

pHead newnode next 进行链接

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	ListNode* newnode = ListNewNode(x);
	//pHead newnode next
	ListNode* next = pHead->next;	//原来的第一个结点
	pHead->next = newnode;
	newnode->next = next;

	newnode->prev = pHead;
	next->prev = newnode;
	//ListInsert(pHead->next, x);
}

---

1.6-双向链表头删

头删：要保证链表中还有数据->即哨兵位指针不是指向自己

步骤：1.保存第二个结点 2.释放第一个结点 3.pHead 和 第二个结点链接

---

==删除时，不能把哨兵位也删除了 ->assert(pHead->next !=pHead)==

断言条件为假：报错终止 条件为真：继续执行

// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	//防止链表为空
	assert(pHead->next != pHead);
	ListNode* first = pHead->next;
	ListNode* next = first->next;
	free(first);
	pHead->next = next;
	next->prev = pHead;
	//ListErase(pHead->next);
}

---

1.7-双向链表查找

遍历链表查找即可

和打印同理,

循环结束条件：cur ！= pHead

当cur回到哨兵位，跳出循环结束，跳出循环则说明找不到,返回NULL

// 双向链表查找
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.8-双向链表在pos的前面进行插入

在pos前插入

posPrev newnode pos 进行链接

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	ListNode* PosPrev = pos->prev;
	ListNode* newnode = ListNewNode(x);
	//PosPrev newnode pos 链接
	PosPrev->next = newnode;
	newnode->prev = PosPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

---

**头插时 :pos = pHead->next **

尾插时： pos = pHead

---

==综上==

头插：	ListInsert(pHead->next, x);
尾插： ListInsert(pHead, x);

---

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

删除pos位置的节点

posPrev posNext 进行链接 ,然后释放pos位置结点

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	//pos后一个位置和pos前一个位置
	ListNode* posPrev = pos->prev;
	ListNode* posNext = pos->next;
	free(pos);
	posPrev->next = posNext;
	posNext->prev = posPrev;
}

**头删时:pos = pHead->next **

尾删时:pos = pHead->prev

==综上：==

头删：ListErase(pHead->next);
尾删：ListErase(pHead->prev);

---

1.10-双向链表的销毁

链表的每个结点都是动态开辟的，说一要逐一释放。

注意：最后要把哨兵位也释放掉

无论是方法1还是方法2:都要遍历链表销毁结点

---

哨兵位释放：方法1：函数外部销毁

函数外部：
    ListNode* phead;
	....
    ListDestory(phead);
	//自己销毁哨兵位
	free(phead);
	phead = NULL;

// 双向链表销毁 - 方法1：在外部销毁头结点
void ListDestory(ListNode* pHead)
{
	//遍历链表进行销毁
	//pHead->next才是第一个结点
	ListNode* cur = pHead->next;
	//用于保存下一个结点
	ListNode* next = NULL;
	//最后回到哨兵位结束
	while (cur != pHead)
	{
		next = cur->next;
		free(cur);
		cur = cur->next; 
	}
}

---

哨兵位释放：方法1：函数内部销毁->传二级指针

函数外部：
    ListNode* phead;
	....
        //传址，直接用函数销毁哨兵位
    ListDestory(&phead);

//方法2：在内部销毁头结点->要改变plist->传二级指针
void ListDestory(ListNode** ppHead)
{
	ListNode* cur = (*ppHead)->next;
	ListNode* next = ListNewNode();
	while (cur != (*ppHead))
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	free(*ppHead);
	*ppHead = NULL;
}

---