【数据结构】动图详解双向链表

短命女 2024-03-27 11:39 64阅读 0赞

**目录**

1.单向链表的劣势

2.带头双向循环链表

1.逻辑结构

2.结点的代码实现

3.双向链表接口的实现

1.接口1---初始化

2.接口2，3---头插，尾插

3. 接口4，5---头删，尾删

3. 接口6---查找

4. 接口7，8--插入，删除

5. 接口8---打印

6. 接口9--销毁

4.完整代码及效果展示

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

### 1.单向链表的劣势 ###

上期我们讲解了链表8种结构中最为常用的两种结构之一的单向不带头不循环链表的基本概念和实现方法（传送门：[动图详解单向链表][Link 1]）。但是在实现时我们发现了以下局限性：

> 1.  由于单链表是单向的，当我们想进行插入或者删除时，由于无法直接找到前驱结点，导致我们还需再使用一个指针遍历链表找到前一个结点的位置。这就导致了进行插入和删除的时间复杂度为O(N)，时间效率较低。
> 2.  由于我们需要再使用一个指针指向链表前一个结点，这也可能在一些情况下导致出错，例如链表只有一个结点。（详情请见上一期，含动图分析）
> 3.  由于其不带头结点，头指针直接指向第一个有效结点，所以在进行头插等可能改变头指针的操作时我们如果传一级指针就会出错。

### 2.带头双向循环链表 ###

#### 1.逻辑结构 ####

那么，我们要如何解决以上劣势呢？这就不得不说到另一种最为常见的链表结构：带头双向循环链表。

**头结点：**所谓头结点，其作用就是标识链表的有效部分。我们之前实现的无头结点的链表，都是通过头指针直接指向链表的有效数据部分。而带头结点的链表，则是用头指针指向一个不存放有效数据的结点，这个结点就称作头结点。这个结点的next指针存放的下一个结点才是链表的有效结点部分。图示如下：

![354231f6d26b4deea68054fac4e84205.png][]

**带头双向循环链表：**其结构是8种结构中最复杂的，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。此链表的结点在单向链表的基础上，添加了前驱指针prev指向上一个结点，然后添加了上述所描述的头结点，而循环则是体现在首尾结点相连上。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现起来反而更加简单。逻辑结构如下：

![81232953c1e0405b98e91495fc856870.png][]

> **注：蓝色箭头代表逻辑上指针的指向，均表示某个结点next或prev指针指向另一个结点，下同。**

#### 2.结点的代码实现 ####

根据单向链表结点的代码实现和双向链表的结构体，我们可以得出其结点的结构体定义如下：

![7719e30a0310430caa8dc598a832f32a.png][]

### 3.双向链表接口的实现 ###

我们同样先在主函数中定义一个头指针用于指向我们的头结点，后续通过这个指针来完成对链表各种接口的实现。由于头指针并不直接指向有效数据部分，有效数据是从第二个结点开始的，因此当我们对数据进行操作时并不需要改变头指针的内容，只需进行传值调用，用一级指针接收即可，可以有效避免头指针被无意修改。

#### 1.接口1---初始化 ####

在使用链表前，我们需要对链表进行初始化。我们可以在初始化接口中创建一个头结点并将其返回给头指针，代码如下：

//用于创建新结点
    ListNode* CreatNode(ListDateType x)
    {
    	ListNode* cur=(ListNode*)malloc(sizeof(ListNode));
    	cur->date = x;
    	cur->next = NULL;
    	cur->prev = NULL;
    	return cur;
    }
    
    //链表初始化
    ListNode* InitList()
    {
    	ListNode* phead=CreatNode(0); //创建头结点
    	phead->next = phead; //前驱指针指向自身
    	phead->prev = phead; //后继指针指向自身  
    	return phead; //将这个结点返回
    }

#### 2.接口2，3---头插，尾插 ####

对于**头插**，根据双向循环链表结构图，我们只需将头结点的next指向新结点，新结点的prev指向头结点，next指向下一结点，下一结点的prev指向新结点即可完成头插。具体过程如下：

![7afe4379cb664b4c906f1bf68a2951fb.gif][]

代码实现如下：

//头插
    void ListPushFront(ListNode* phead, ListDateType x) //不改变头指针，无需传址
    {
    	assert(phead != NULL); //保证链表有头结点，即完成了初始化
    	ListNode* NewNode = CreatNode(x); //创建新结点
    	ListNode* frist = phead->next; //找到链表头
    
        //进行头插
    	phead->next = NewNode;
    	NewNode->prev = phead;
    	NewNode->next = frist;
    	frist->prev = NewNode;
    }

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

对于**尾插**，由于双向循环链表结构的特殊性，我们不需要向单链表一样遍历链表找到链表尾，直接通过头结点的prev指针就可直接找到链表尾，也不需要再遍历链表找到上一个结点。代码反而变得更加简单，只需要通过改变结点的prev和next指针即可完成尾插，这就是结构带来的优势。其时间复杂度为O(1)。具体过程如下：

![4b1a2ae223834b45bba2954aac4f3803.gif][]

具体代码如下：

//尾插
    void ListPushBack(ListNode* phead, ListDateType x)
    {
    	assert(phead != NULL); //保证链表已经初始化
    	ListNode* NewNode = CreatNode(x); //创建新结点
    	ListNode* tail = phead->prev; //找到链表尾
    
        //进行尾插
    	tail->next = NewNode; 
    	NewNode->prev = tail;
    	NewNode->next = phead;
    	phead->prev = NewNode;
    }

> **需要注意的是，与单链表不同，这里是双向循环链表，所以链表尾并不是指向NULL，而是指向头结点。同时不会出现对NULL解引用的情况，不需要对单向链表一样进行分类讨论。**

#### 3. 接口4，5---头删，尾删 ####

对于**头删**，我们只需要将头结点指向下一个位置，然后将原来指向的空间free()掉即可。如果链表为空，我们就让函数直接返回，具体动态效果如下：

![5a1f39beedd94fc1b2d1b76f168e42d5.gif][]

代码实现如下：

//头删
    void ListPopFront(ListNode* phead)
    {
    	assert(phead != NULL); //确保链表初始化
    	if (phead->next == phead)
    	{
    		return; //链表为空直接返回，防止把头结点删除
    	}
    	ListNode* frist = phead->next; //找到链表头
    	ListNode* second = frist->next; //找到链表头下一个结点
    
        //进行头删
    	phead->next = second;
    	second->prev = phead;
    	free(frist); //释放结点
    	frist = NULL;
    }

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

对于**尾删**，我们同样通过头结点的prev指针直接找到链表尾，然后进行删除操作，过程与头删类似，时间复杂度为O(1)。具体过程如下：

![685c36b0493f4a60b64de556a37edc3d.gif][]

具体代码如下：

//尾删
    void ListPopBack(ListNode* phead)
    {
    	assert(phead != NULL); //确保链表已经初始化
    	if (phead->next == phead)
    	{
    		return; //链表为空直接返回，防止把头结点删除
    	}
    	ListNode* tail = phead->prev; //找到链表尾
    	ListNode* prev = tail->prev;  //找到前驱
    
        //进行尾删
    	phead->prev = prev;
    	prev->next = phead;
    	free(tail); //释放空间
    	tail = NULL;
    }

#### 3. 接口6---查找 ####

对于**查找**，其方法与单向链表一样，通过遍历链表的所有结点即可。有一点不同的是我们的双向链表是循环的，因此循环的条件不再是cur！=NULL而是cur！=phead，当cur等于头指针时则说明已经成功遍历一遍了。代码如下：

//查找
    ListNode* ListFind(ListNode* phead, ListDateType x)
    {
    	assert(phead != NULL); //确保已经初始化
    	ListNode* cur = phead->next; //指向第一个有效结点，准备遍历
    	while (cur != phead) //遍历一圈
    	{
    		if (cur->date == x)
    		{
    			return cur; //找到了，返回结点
    		}
    		cur = cur->next; //指向下一结点
    	}
    
        //找不到，返回空指针
    	return NULL;
    }

#### 4. 接口7，8--插入，删除 ####

对于**插入**，我们可以实现一个在指定结点前插入一个新结点的接口，而这个指定结点我们可以通过查找接口来获取。由于我们的链表是双向的，我们就可以很容易的得到新结点的前一个与后一个结点的位置，进而实现插入接口，其时间复杂度为O(1)。动态效果如下：

![2c05524e840b415082f76837a40549a3.gif][]

//插入
    void ListInsert(ListNode* phead, ListNode* pos, ListDateType x)
    {
    	assert(pos != NULL); //确保已经初始化
    	ListNode* NewNode = CreatNode(x); //创建新结点
    	ListNode* prev = pos->prev; //前一个结点
    
        //进行插入
    	NewNode->next = pos;
    	pos->prev = NewNode;
    	prev->next = NewNode;
    	NewNode->prev = prev;
    
    }

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

对于**删除**，我们同样可以实现一个删除指定结点的接口，而这个指定结点我们依旧可以通过查找接口来获取。同样的，由于结构上的优势，我们可以很方便的直接对指定位置进行删除，时间复杂度为O(1)。具体过程如下：

![61d3f320104c4631a0e48f504992275c.gif][]

具体代码如下：

//删除
    void ListErase(ListNode* phead, ListNode* pos)
    {
    	assert(pos != NULL); //确保已经初始化
    	ListNode* next = pos->next; //后一个结点
    	ListNode* prev = pos->prev; //前一个结点
    
        //进行删除
    	prev->next = next;
    	next->prev = prev;
    	free(pos); //释放空间
    	pos = NULL;
    }

#### 5. 接口8---打印 ####

对于**打印**，很简单，遍历一圈链表即可，当cur等于头结点地址时停止打印。动图效果如下：

![ef4edaae6b8747ce87be70d1fd81f6d7.gif][]

具体代码如下：

//打印
    void ListPrint(ListNode* phead)
    {
    	assert(phead != NULL); //确保链表已经初始化
    	ListNode* cur = phead->next; //指向有效部分
    	while (cur != phead) //遍历一圈
    	{
    		printf("%d ", cur->date); //打印数据
    		cur = cur->next; //指向下一结点
    	}
    	printf("\n");
    }

#### 6. 接口9--销毁 ####

对于**销毁**，我们动态内存申请所得到的空间，当我们不需要的时候，需要我们进行手动销毁。因此，我们还需要一个接口对使用完毕的链表进行free()，具体代码如下：

//销毁
    void ListDestroy(ListNode* phead)
    {
    	assert(phead != NULL); //确保已经初始化
    	ListNode* cur = phead->next; //指向有效部分
    	while (cur != phead) //释放有效结点
    	{
    		ListNode* next = cur->next;
    		free(cur);
    		cur = next;
    	}
    
    	//释放头结点
    	free(phead);
    	phead = NULL;
    }

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

> 通过上面一个个接口的实现，我们发现：
> 
> 虽然双向带头循环链表的结构比起单向链表结构复杂太多，但对于各接口的实现反而变得更加方便，并且很多接口时间效率更加地高。因此，一个好的结构不仅可以简化我们的代码量，也可以提高我们代码的效率。

### 4.完整代码及效果展示 ###

我们同样采用多文件编写的形式，将上述接口的定义实现放在List.c文件中，然后将接口的声明和结构体的定义放于List.h头文件中，以达到封装的效果。这样我们如果需要使用双向链表，就只需要在文件中包含对应的头文件List.h就可以使用我们上面定义的各种接口。以下为本文实现的带头双向循环链表完整代码以及效果展示：

//List.h文件，用于声明接口函数，定义结构体
    #pragma once
    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    
    typedef int ListDateType; //重命名便于维护
    typedef struct ListNode
    {
    	ListDateType date;
    	struct ListNode* next; //指向前一个结点
    	struct ListNode* prev; //指向后一个结点
    }ListNode;
    
    //初始化
    ListNode* InitList();
    //尾插
    void ListPushBack(ListNode* phead, ListDateType x);
    //头插
    void ListPushFront(ListNode* phead, ListDateType x);
    //尾删
    void ListPopBack(ListNode* phead);
    //头删
    void ListPopFront(ListNode* phead);
    //查找
    ListNode* ListFind(ListNode* phead, ListDateType x);
    //删除
    void ListErase(ListNode* phead, ListNode* pos);
    //插入
    void ListInsert(ListNode* phead, ListNode* pos, ListDateType x);
    //打印
    void ListPrint(ListNode * phead);
    //销毁
    void ListDestroy(ListNode* phead);

//SList.c文件，用于定义接口函数
    #define _CRT_SECURE_NO_WARNINGS 1
    #include "List.h"
    
    ListNode* CreatNode(ListDateType x)
    {
    	ListNode* cur=(ListNode*)malloc(sizeof(ListNode));
    	cur->date = x;
    	cur->next = NULL;
    	cur->prev = NULL;
    	return cur;
    }
    ListNode* InitList()
    {
    	ListNode* phead = CreatNode(0); //创建头结点
    	phead->next = phead; //前驱指针指向自身
    	phead->prev = phead; //后继指针指向自身  
    	return phead; //将这个结点返回
    }
    
    void ListPushBack(ListNode* phead, ListDateType x)
    {
    	assert(phead != NULL);
    	ListNode* NewNode = CreatNode(x);
    	ListNode* tail = phead->prev; //找到链表尾
    	tail->next = NewNode; 
    	NewNode->prev = tail;
    	NewNode->next = phead;
    	phead->prev = NewNode;
    }
    
    void ListPushFront(ListNode* phead, ListDateType x) //不改变头指针，无需传址
    {
    	assert(phead != NULL); //保证链表有头结点，即完成了初始化
    	ListNode* NewNode = CreatNode(x); //创建新结点
    	ListNode* frist = phead->next; //找到链表头
    
    	//进行头插
    	phead->next = NewNode;
    	NewNode->prev = phead;
    	NewNode->next = frist;
    	frist->prev = NewNode;
    }
    
    void ListPopBack(ListNode* phead)
    {
    	assert(phead != NULL);
    	if (phead->next == NULL)
    	{
    		return; //链表为空直接返回
    	}
    	ListNode* tail = phead->prev; //找到链表尾
    	ListNode* prev = tail->prev;  //找到前驱
    	phead->prev = prev;
    	prev->next = phead;
    	free(tail);
    	tail = NULL;
    
    }
    
    void ListPopFront(ListNode* phead)
    {
    	assert(phead != NULL); //确保链表初始化
    	if (phead->next == NULL)
    	{
    		return; //链表为空直接返回
    	}
    	ListNode* frist = phead->next; //找到链表头
    	ListNode* second = frist->next; //找到链表头下一个结点
    
    	//进行头删
    	phead->next = second;
    	second->prev = phead;
    	free(frist); //释放结点
    	frist = NULL;
    }
    
    ListNode* ListFind(ListNode* phead, ListDateType x)
    {
    	assert(phead != NULL); //确保已经初始化
    	ListNode* cur = phead->next; //指向第一个有效结点，准备遍历
    	while (cur != phead) //遍历一圈
    	{
    		if (cur->date == x)
    		{
    			return cur; //找到了，返回结点
    		}
    		cur = cur->next; //指向下一结点
    	}
    
    	//找不到，返回空指针
    	return NULL;
    }
    
    void ListErase(ListNode* phead, ListNode* pos)
    {
    	assert(pos != NULL); //确保已经初始化
    	ListNode* next = pos->next; //后一个结点
    	ListNode* prev = pos->prev; //前一个结点
    
    	//进行删除
    	prev->next = next;
    	next->prev = prev;
    	free(pos); //释放空间
    	pos = NULL;
    }
    
    void ListInsert(ListNode* phead, ListNode* pos, ListDateType x)
    {
    	assert(pos != NULL); //确保已经初始化
    	ListNode* NewNode = CreatNode(x); //创建新结点
    	ListNode* prev = pos->prev; //前一个结点
    
    	//进行插入
    	NewNode->next = pos;
    	pos->prev = NewNode;
    	prev->next = NewNode;
    	NewNode->prev = prev;
    
    }
    
    void ListPrint(ListNode* phead)
    {
    	assert(phead != NULL); //确保链表已经初始化
    	ListNode* cur = phead->next; //指向有效部分
    	while (cur != phead) //遍历一圈
    	{
    		printf("%d ", cur->date); //打印数据
    		cur = cur->next; //指向下一结点
    	}
    	printf("\n");
    }
    
    void ListDestroy(ListNode* phead)
    {
    	assert(phead != NULL); //确保已经初始化
    	ListNode* cur = phead->next; //指向有效部分
    	while (cur != phead) //释放有效结点
    	{
    		ListNode* next = cur->next;
    		free(cur);
    		cur = next;
    	}
    
    	//释放头结点
    	free(phead);
    	phead = NULL;
    }

最后， 我们在text.c文件调用双向循环链表各个接口进行测试，如下：

//text.c文件，用于测试
    #define _CRT_SECURE_NO_WARNINGS 1
    #include "List.h"
    void ListText()
    {
    	ListNode* plist = NULL;
    	//初始化
    	plist = InitList();
    	printf("链表起始数据:\n");
    	ListPrint(plist);
    	//尾插
    	ListPushBack(plist, 1);
    	ListPushBack(plist, 2);
    	ListPushBack(plist, 3);
    	printf("尾插后数据:\n");
    	ListPrint(plist);
    	//头插
    	ListPushFront(plist, 4);
    	ListPushFront(plist,5);
    	ListPushFront(plist, 6);
    	printf("头插后数据:\n");
    	ListPrint(plist);
    	//尾删
    	ListPopBack(plist);
    	printf("尾删后数据:\n");
    	ListPrint(plist);
    	//头删
    	ListPopFront(plist);
    	printf("头删后数据:\n");
    	ListPrint(plist);
    
    	//修改数据为5的结点为50
    	ListNode* cur1 = ListFind(plist, 5); //找数据为5结点
    	if (cur1)
    	{
    		cur1->date = 50; //查找附带着修改的作用
    	}
    	printf("修改数据为5的结点为50后\n");
    	ListPrint(plist);
    
    	//在date为4的结点前插入数据为7的结点
    	ListNode* cur2 = ListFind(plist,4); //找数据为4结点
    	if (cur2) 
    	{
    		ListInsert(plist, cur2, 7); //插入
    	}
    	printf("在4前插入7后数据:\n");
    	ListPrint(plist);
    	//删除数据为1的结点
    	ListNode* cur3 = ListFind(plist, 1); //找数据为1结点
    	if (cur3) 
    	{
    		ListErase(plist, cur3); //删除
    	}
    	printf("删除1后数据:\n");
    	ListPrint(plist);
    	//销毁
    	ListDestroy(plist);
    }
    int main()
    {
    	ListText();
    	return 0;
    }

以下就是测试的最终效果：

![4c19f3e13d4b4696a51230b09eeb3385.png][]

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

***以上，就是本期的全部内容。***

***制作不易，能否点个赞再走呢qwq***

[Link 1]: http://t.csdn.cn/5C1cz
[354231f6d26b4deea68054fac4e84205.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/08748af4c09947f2b61bd872e1d44b6d.png
[81232953c1e0405b98e91495fc856870.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/f49c630bc79f4280aab026c0a576827f.png
[7719e30a0310430caa8dc598a832f32a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/11f848bfc089495b8f271c8d1a40395c.png
[7afe4379cb664b4c906f1bf68a2951fb.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/45807dad943f4ff3889f7295446ace76.png
[4b1a2ae223834b45bba2954aac4f3803.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/dc77096254f5457cb749e59c1c53b92d.png
[5a1f39beedd94fc1b2d1b76f168e42d5.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/52918fea20be470583b666519ccc6448.png
[685c36b0493f4a60b64de556a37edc3d.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/a8d3690596fe4b92a3f8510b3d89b427.png
[2c05524e840b415082f76837a40549a3.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/aa6dbd3e6f1a45f4b457807410303dd2.png
[61d3f320104c4631a0e48f504992275c.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/b7b3268fbec640198c8501aeb45ca109.png
[ef4edaae6b8747ce87be70d1fd81f6d7.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/c527d2251d464be8873f2ab42d9d115b.png
[4c19f3e13d4b4696a51230b09eeb3385.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/cd0f76de32c14ff5879b4007d75d9d2f.png