带头结点的双向循环链表

淡淡的烟草味﹌ 2024-02-18 11:49 56阅读 0赞

**目录**

带头结点的双向循环链表

1.存储定义

2.结点的创建

3.结点的初始化

4.尾插结点

5.尾删结点

6.头插结点

7.头删结点

8.查找并返回结点

9.在pos结点前插入结点

10.删除pos结点

11.打印链表

12.销毁链表

13.头插结点2.0版

14.尾插结点2.0版

--------------------

**前言：**

当我们使用单链表时，想要去找到前面的前驱结点的时候，我们发现了受到限制，因为当时的结点只能去找后面的结点。

于是，就到了这里的**带头结点的双向循环链表**。

如图：

![333ef6a3735d43b5ba0d58dbe51244f4.png][]

首先给出 双向链表的定义：是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。

那双向循环链表就是最后一个结点的next指向头结点，头结点的前驱指向尾结点。

## **带头结点的双向循环链表** ##

### 1.存储定义 ###

typedef int CLDataType;
    
    typedef  struct ListNode
    {
    	CLDataType val;
    	struct ListNode* next; //存放后面结点的指针
    	struct ListNode* pre;  //存放前面结点的指针
    }ListNode;

### 2.结点的创建 ###

结点的创建，刚开始创建头结点我们一般会采用二级指针的方式，这里我们采用**使用函数返回值的形式**来避免野指针问题。

//创建链表
    ListNode* CreateNode(CLDataType x) 
    {
    	//这里采用返回值的形式进行创建结点
    	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    	if (newnode == NULL) 
    	{
    		perror("malloc");
    		exit(-1);
    	}
    	newnode->val = x;
    	newnode->pre = NULL;
    	newnode->next = NULL;
    	return newnode;
    }

如果是刚开始创建的头节点的话：

![bea34107d5a145aa823a4110c17d8365.png][]

### 3.结点的初始化 ###

这个时候就能体现带头结点双向循环链表的好处了

ListNode* InitNode() 
    {
    	ListNode* phead = CreateNode(-1);
    	//让头节点的前驱和后继结点都指向自己
    	phead->next = phead;	
    	phead->pre = phead;
    	return phead;
    }

因为修改了头结点，所以接着使用函数返回值的形式。

注意：**初始化时，头结点的前驱和后继指针都指向自己**。如图：

![a3a692d6a3dc4086a2d47b956fdddfde.png][]

### 4.尾插结点 ###

之前的单链表尾插需要遍历整个链表去找尾结点，但是，**这里是带头结点的双向循环链表，只需去找头结点的前驱结点就找到了尾结点。**

//尾插结点
    void ListPushBack(ListNode* phead, CLDataType x) 
    {
    	assert(phead);
    	ListNode* newnode = CreateNode(x);
    	ListNode* tail = phead->pre;
    	
    	tail->next = newnode; //之前的尾结点的后继指针指向新结点
    	newnode->pre = tail;  //新结点的前驱指向之前的尾结点
    	newnode->next = phead; //新结点的后继指针指向头结点
    	phead->pre = newnode;  //头结点的前驱指向

当链表中只有一个头结点的时候，tail指向自己。

![47ca6c22fa7b4f208dc5320f95c522e5.png][]

再继续尾插时，仍是这样。

![78ba69a963114790b435d571aeff468a.png][]

### 5.尾删结点 ###

一般都是先找到尾节结点，然后再去找到尾结点的前一个结点Pre。Pre指向头结点，头结点的前驱指向Pre。之后再删去尾节结。

//尾删结点
    void ListPopBack(ListNode* phead)
    {
    	assert(phead);
    	assert(phead->next != phead); //避免只有一个头结点
    	ListNode* tail = phead->pre;
    	ListNode* Pre = tail->pre; //用来记录尾结点的前一个结点
    	Pre->next = phead;
    	phead->pre = Pre;
    	free(tail);
    	tail = NULL;
    }

注意：当只有一个头结点的情况时，说明已经没有链表结点。所以不能进行删除。进而这里采用，assert( phead->next != phead) 来避免此情况。

### 6.头插结点 ###

和单链表的头插相似，用next指针记录头结点的下一个结点。先让新结点与next指针指向的结点建立连接，再与头结点建立连接。

//头插结点
    void ListPushFront(ListNode* phead,CLDataType x) 
    {
    	assert(phead);
    	ListNode* newnode = CreateNode(x);
    	ListNode* next = phead->next; //记录头结点后的第一个结点
    
    	newnode->next = next;
    	next->pre = newnode;
    
    	phead->next = newnode;
    	newnode->pre = phead;
    }

![91db3ebb76e54d37bb01e4c71f665344.png][]

### 7.头删结点 ###

这里需要注意的是避免只有一个头结点的情况下，删除结点，这样使用同尾删结点一样的方法，通过断言 assert(phead->next != phead);

//头删结点
    void ListPopFront(ListNode* phead) 
    {
    	assert(phead);
    	assert(phead->next != phead);
    	phead->next = phead->next->next;
    	phead->next->next->pre = phead;
    }

![aa3a3083b934486ea69cc30346af348c.png][]

### 8.查找并返回结点 ###

这里采用cur指针去遍历链表，找到就返回结点，没有找到就返回空。

//查找并返回结点
    ListNode* ListFind(ListNode* phead, CLDataType x) 
    {
    	assert(phead);
    	ListNode* cur = phead->next;
    	while (cur != phead) 
    	{
    		if (cur->val == x)
    		{
    			return cur;
    		}
    		cur = cur->next;
    	}
    	return NULL;
    }

### 9.在pos结点前插入结点 ###

因为是带头结点的双向循环链表，这样就可以直接进行插入。

//在pos前面插入结点
    void ListInsert(ListNode* pos, CLDataType x) 
    {
    	assert(pos);
    	ListNode* newnode = CreateNode(x);
        //注意顺序
        //先让后驱建立连接
    	newnode->next = pos;
    	pos->pre->next = newnode;
        //再前驱建立连接
    	newnode->pre = pos->pre;
    	pos->pre = newnode;
    }

![ecff7f44384e4fb3b98b117f90644da7.png][]

![12370658e1274e14827742bf6c8c9d5e.png][]

### 10.删除pos结点 ###

修改pos的前驱和后继

//删除pos位置的结点
    void ListErase(ListNode* pos) 
    {
    	assert(pos);
    	pos->pre->next = pos->next;
    	pos->next->pre = pos->pre;
    }

![ca9c335fe1f7448b80ef6b398ea7cb1d.png][]

### 11.打印链表 ###

//打印链表
    void ListPrint(ListNode* phead) 
    {
    	assert(phead);
    	ListNode* cur = phead->next;
    	printf("phead<==>");
    	while (cur != phead) 
    	{
    		printf("%d<==>", cur->val);
    		cur = cur->next;
    	}
    	printf("\n");
    }

### 12.销毁链表 ###

//销毁链表
    void ListDestory(ListNode* phead) 
    {
    	assert(phead);
    	ListNode* cur = phead->next;
    	while (cur != phead)
    	{
    		ListNode* next = cur->next;
    		free(cur);
    		cur = next;
    	}
    	free(phead);
    	phead = NULL;
    }

### 13.头插结点2.0版 ###

这里我们借助 在pos结点前插入结点 的接口。

头插结点，那就是**把pos结点变为 phead->next 的结点**。这样结点的插入就模拟了头插结点，从而减少了一写代码的工作量。

//头插结点2.0
    void ListushFront(ListNode* phead, CLDataType x)
    {
    	assert(phead);
    	ListNode* newnode = CreateNode(x);
    	ListNode* next = phead->next; //记录头结点后的第一个结点
    	ListInsert(next,x); //这里的next相当于pos结点
    }

例如 ：在 1结点 前插入 结点25

![38636054b67345be873ffe3369b630e1.png][]

### 14.尾插结点2.0版 ###

根据带头结点的双向循环链表的特性，再借助前面的 在pos结点前插入结点（ListInsert） 的接口

这时我们会想到的就是 尾插结点不是在尾结点的后面进行插入的吗，而ListInsert是在pos前面进行结点的插入。 这时就采用 **在头结点的前进行插入结点，从而达到尾插结点的特性。**

//尾插结点
    void ListPushBack(ListNode* phead, CLDataType x)
    {
    	assert(phead);
    	ListNode* newnode = CreateNode(x);
    	ListInsert(phead,x);
    }

![fee9d824539643ea9a31e263eb228733.png][]

[333ef6a3735d43b5ba0d58dbe51244f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/0cf3446f10bc48fa918a45460b17f251.png
[bea34107d5a145aa823a4110c17d8365.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/ed4f8d8ae8704d5ca5d0afc3024bedc2.png
[a3a692d6a3dc4086a2d47b956fdddfde.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/ed06a015c0f149e898f6fecf75d9116f.png
[47ca6c22fa7b4f208dc5320f95c522e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/2a60c5a080cb4c19ab146f44381add58.png
[78ba69a963114790b435d571aeff468a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/0ea5b40ee3a74d81b1b2b5c3c1401b02.png
[91db3ebb76e54d37bb01e4c71f665344.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/6d1ff122fb4e4364b5d66df7b16179c5.png
[aa3a3083b934486ea69cc30346af348c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/def32402ea0f490f874bf781dd2239c1.png
[ecff7f44384e4fb3b98b117f90644da7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/80ecf8e91a2f4dff9d9ef96123008ae9.png
[12370658e1274e14827742bf6c8c9d5e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/573863bd035f49daa9f5a5321175864a.png
[ca9c335fe1f7448b80ef6b398ea7cb1d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/1102d50520784a798699d3b43f371f0e.png
[38636054b67345be873ffe3369b630e1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/d489246dc2f14ba2a6a32b57ceb879a7.png
[fee9d824539643ea9a31e263eb228733.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/98ecd6b22fb8446dba242a1c7c19e341.png