【数据结构】双向链表

旧城等待， 2023-10-12 22:39 21阅读 0赞

> 前面我们已经学完了单向链表，知道了单向链表如何进行增删查改等基本功能，而今天，我们将要学习双向链表。

**目录**

1.链表的分类

2.双向链表定义

3.双向链表接口的实现

所有接口函数一览

创建返回链表头节点

初始化链表

双向链表打印

双向链表尾插

双向链表尾删

双向链表头插

双向链表头删

双向链表在pos的前面进行插入

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

求双向链表长度

双向链表销毁

4.完整代码

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

回忆上次学习的单向链表结构图：

![a76f853e1d92495db0d0291de735baff.png][]

下面还要详细的介绍一下各种链表示意图，上期遗漏了这部分内容

## 1.链表的分类 ##

**1. 单向或者双向**

![d1daae589d5e490f9608a0f4348ad746.png][]

**2. 带头或者不带头**

![e6b3e044c312460b901f8cb511552164.png][]

**3. 循环或者非循环**

![e5e88b874d4c4fc98926ba77ad619716.png][]

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

![d7c586ee3858477590b9a196d79097bc.png][]

> 1. 无头单向非循环链表：**结构简单**，一般不会单独用来存数据。实际中更多是**作为其他数据结构的子结 构**，如哈希桶、图的邻接表等等。另外这种结构在**笔试面试**中出现很多。
> 
> 2. 带头双向循环链表：**结构最复杂**，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向 循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而 简单了，后面我们代码实现了就知道了。

由于上期我们已经学完了无头单向非循环链表，因此这期我们来学习**带头双向循环链表**。

## 2.双向链表定义 ##

和单向链表一样，双向链表每个节点都是由结构体组成的数据类型，但是双向链表结构体中增加了一个指向前一个节点的指针。

typedef int LTDataType; //方便修改数据类型
    
    typedef struct ListNode
    {
    	struct ListNode* next;//指向下一个节点的指针
    	struct ListNode* prev;//指向前一个节点的指针
    	LTDataType data; //存储的数据
    }LTNode;

我们今天要将的是带哨兵卫头节点的双向循环链表，它的头节点不存储有效数据，头节点中的prev指针指向最后一个节点

![d7ef27007a7a4512984dbd601ba610c5.png][]

当链表为空时，指针的指向关系图：

![abd51ddd629b42b99e8e8f3e71b6f2bf.png][]

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

### 所有接口函数一览 ###

下面是双向链表中经常要用到的一些接口函数：

//初始化
    LTNode* ListInit();
    //打印
    void printList(LTNode* phead);
    //尾插
    void ListPushBack(LTNode* phead, LTDataType x);
    //头插
    void ListPushFront(LTNode* phead, LTDataType x);
    //尾删
    void ListPopBack(LTNode* phead);
    //头删
    void ListPopFront(LTNode* phead);
    //判断链表是否为空
    bool ListEmpty(LTNode* phead);
    //在pos位置前插入x
    void ListInsert(LTNode* pos, LTDataType x);
    //删除pos位置节点
    void ListErase(LTNode* pos);
    //求链表长度
    int ListSize(LTNode* phead);
    //销毁
    void ListDestory(LTNode* phead);

### 创建返回链表头节点 ###

函数使用**`malloc`**动态分配了一个**`LTNode`**类型的内存空间，用node进行接收。同时要检查内存分配是否成功，将新节点中的data赋值为传入的数据x，将新节点的**`next`**和**`prev`**指针都设置为NULL,最后返回新节点的地址。

//创建新节点
    LTNode* BuyListNode(LTDataType x)
    {
    	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    	if (node == NULL)
    	{
    		perror("malloc fail");
    		exit(-1);
    	}
    	node->data = x;
    	node->next = NULL;
    	node->prev = NULL;
    	return node;
    }

###  ###

### 初始化链表 ###

初始化链表就是给链表创建一个头节点，这里需要使用到上面介绍完的创建新节点**BuyListNode**函数，因为头节点不存储有效数据，所以我们将data赋值为-1，同时头节点中的next和prev都指向自己，最后返回头节点的地址。

LTNode* ListInit()
    {
    	LTNode* phead = BuyListNode(-1);
    	phead->next = phead;
    	phead->prev = phead;
    	return phead;
    }

###  ###

### 双向链表打印 ###

双向链表的打印和单向链表类似，**注意循环的截止条件不是cur为空，而当当cur重新指向头节点的时候停止循环。因为最后一个节点的next指针指向的是头节点。**

//打印
    void printList(LTNode* phead)
    {
    	LTNode* cur = phead->next;
    	while (cur != phead)
    	{
    		printf("%d->", cur->data);
    		cur = cur->next;
    	}
    	printf("NULL\n");
    }

### 双向链表尾插 ###

普通的方法是创建一个新的节点插入到链表的尾部，当然还有更为简单的方法，就是调用一下我们后面要讲到的 **ListInsert** 函数，这个函数可以在指定位置前插入一个节点并存储有效数据。如果这个指定位置是头节点的位置，那么头节点的前一个位置就是链表最后一个节点所在的位置。

下面介绍一下普通的方法吧：

![188e23d9b8bf40ab8f65b8d0f6fd1c9a.png][]

将最后一个节点命名为tail，然后根据上图修改一下phead ， tail ， newNode之间的指向关系即可

//尾插
    void ListPushBack(LTNode* phead, LTDataType x)
    {
    	assert(phead);
    
    	/*
    		//可以直接调用void ListInsert来实现
    		ListInsert(phead , x);
    		//代码复用
    	*/
    
    	LTNode* newNode = BuyListNode(x);
    	LTNode* tail = phead->prev;
    	newNode->next = phead;
    	newNode->prev = tail;
    	tail->next = newNode;
    	phead->prev = newNode;
    }

### 双向链表尾删 ###

这里也可以使用两种方法来实现，普通方法是找到最后一个节点，修改指向关系，再释放掉最后一个节点的空间。简单的方法是调用一个可以删除指定位置节点的函数**ListErase**，将最后一个节点的位置传入到这个函数就可以进行尾删，（最后一个节点的位置是phead->prev）这个函数下面也将会给大家介绍到。

普通方法：

![db70c06568a24b0784ec648f0d992bda.png][]

将最后一个节点命名为tail，倒数第二个节点命名为tailPrev，按上图修改它们的指向关系即可。

**为了防止出现尾删空链表的情况出现，我们需要使用一个ListEmpty函数来判断链表是否为空，同时使用assert断言，一旦链表为空，用户仍然使用尾删程序就会报错。头删同理如此。**

//尾删
    void ListPopBack(LTNode* phead)
    {
    	assert(phead);
    	assert(ListEmpty(phead));
    
    	/*
    		//可以复用ListErase函数来实现后面的代码
    		ListErase(phead->prev);
    	*/
    	
    
    	LTNode* tail = phead->prev;
    	LTNode* tailPrev = tail->prev;
    	phead->prev = tailPrev;
    	tailPrev->next = phead;
    
    	free(tail);
    }

### 双向链表头插 ###

这里也可使用两种方法，我们介绍一下普通的方法：

![da7d7b56a01c4babb40a9c9ee6f715f1.png][]

将头节点的后一个节点命名为pheadNext，然后将newNode插入到phead和pheadNext之间即可。

//头插
    void ListPushFront(LTNode* phead, LTDataType x)
    {
    	assert(phead);
    
    	/*
    		//可以直接调用void ListInsert来实现
    		ListInsert(phead->next , x);
    		//代码复用
    	*/
    
    	LTNode* newNode = BuyListNode(x);
    	LTNode* pheadNext = phead->next;
    	phead->next = newNode;
    	newNode->prev = phead;
    	newNode->next = pheadNext;
    	pheadNext->prev = newNode;
    }

### 双向链表头删 ###

这里也可使用两种方法，我们介绍一下普通的方法：

![08f64e076f3d4069b16a927c642eff10.png][]

//头删
    void ListPopFront(LTNode* phead)
    {
    	assert(phead);
    	assert(ListEmpty(phead));
    
    	/*
    		//可以复用ListErase函数来实现后面的代码
    		ListErase(phead->next);
    	*/
    
    	LTNode* next = phead->next;
    	phead->next = next->next;
    	next->next->prev = phead;
    
    	free(next);
    }

### 双向链表在pos的前面进行插入 ###

直接将pos的前一个节点命名为prev，再将newNode插入。

![a2a90d5ab98c4b57a67e8cdfbcf5f124.png][]

//在pos位置前插入x
    void ListInsert(LTNode* pos, LTDataType x)
    {
    	assert(pos);
    
    	LTNode* prev = pos->prev;
    	LTNode* newNode = BuyListNode(x);
    
    	prev->next = newNode;
    	newNode->prev = prev;
    	newNode->next = pos;
    	pos->prev = newNode;
    }

###  ###

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

![cb3e438d8a614723b97cceb3b9706e99.png][]

将pos前一个节点命名为prev,后一个节点命名为next,这样命名方便我们修改指针的指向。然后按照上图修改指针即可。

//删除pos位置节点
    void ListErase(LTNode* pos)
    {
    	assert(pos);
    	LTNode* prev = pos->prev;
    	LTNode* next = pos->next;
    
    	prev->next = next;
    	next->prev = prev;
    	free(pos);
    }

###  ###

### 求双向链表长度 ###

这里使用的方法是遍历整个链表。

//求链表长度
    int ListSize(LTNode* phead)
    {
    	assert(phead);
    	LTNode* cur = phead->next;
    	int size = 0;
    	while (cur != phead)
    	{
    		++size;
    		cur = cur->next;
    	}
    	return size;
    }

### 双向链表销毁 ###

这一步可以复用删除pos位置节点的函数ListErase，我们只要将链表的每一个节点地址都传入到这个函数，就可销毁链表。当然，最后也要将头节点给释放销毁。

//销毁
    void ListDestory(LTNode* phead)
    {
    	assert(phead);
    	LTNode* cur = phead->next;
    	while (cur != phead)
    	{
    		LTNode* next = cur->next;
    		ListErase(cur);
    		cur = next;
    	}
    	free(phead);
    }

## 4.顺序表和链表的区别 ##

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>不同点</td> 
   <td>顺序表</td> 
   <td>链表</td> 
  </tr> 
  <tr> 
   <td>存储空间上</td> 
   <td>物理上一定连续</td> 
   <td>逻辑上连续，但物理上不一定连 续</td> 
  </tr> 
  <tr> 
   <td>随机访问</td> 
   <td>支持O(1)</td> 
   <td>不支持：O(N)</td> 
  </tr> 
  <tr> 
   <td>任意位置插入或者删除元 素</td> 
   <td>可能需要搬移元素，效率低O(N)</td> 
   <td>只需修改指针指向</td> 
  </tr> 
  <tr> 
   <td>插入</td> 
   <td>动态顺序表，空间不够时需要扩 容</td> 
   <td>没有容量的概念</td> 
  </tr> 
  <tr> 
   <td>应用场景</td> 
   <td>元素高效存储+频繁访问</td> 
   <td>任意位置插入和删除频繁</td> 
  </tr> 
  <tr> 
   <td>缓存利用率</td> 
   <td>高</td> 
   <td>低</td> 
  </tr> 
 </tbody> 
</table>

**顺序表优点：下标随机访问，cpu高速缓存命中率高**

**顺序表缺点：头部或者中间插入删除效率低，扩容有一定程度性能消耗，可能存在一定程度空间浪费。**

**链表优点：任意位置插入删除O(1)复杂度，按需申请释放。**

**链表缺点：不支持下标随机访问。**

## 5.完整代码 ##

头文件： 存放函数声明部分

#pragma once
    
    #include<stdio.h>
    #include<assert.h>
    #include<stdbool.h>
    #include<stdlib.h>
    
    typedef int LTDataType; //方便修改数据类型
    
    typedef struct ListNode
    {
    	struct ListNode* next;//指向下一个节点的指针
    	struct ListNode* prev;//指向前一个节点的指针
    	LTDataType data; //存储的数据
    }LTNode;
     
    //初始化
    LTNode* ListInit();
    //打印
    void printList(LTNode* phead);
    //尾插
    void ListPushBack(LTNode* phead, LTDataType x);
    //头插
    void ListPushFront(LTNode* phead, LTDataType x);
    //尾删
    void ListPopBack(LTNode* phead);
    //头删
    void ListPopFront(LTNode* phead);
    //判断链表是否为空
    bool ListEmpty(LTNode* phead);
    //在pos位置前插入x
    void ListInsert(LTNode* pos, LTDataType x);
    //删除pos位置节点
    void ListErase(LTNode* pos);
    //求链表长度
    int ListSize(LTNode* phead);
    //销毁
    void ListDestory(LTNode* phead);

List.c文件 存放函数定义

#define _CRT_SECURE_NO_WARNINGS 1
    
    #include"List.h"
    
    //创建新节点
    LTNode* BuyListNode(LTDataType x)
    {
    	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    	if (node == NULL)
    	{
    		perror("malloc fail");
    		exit(-1);
    	}
    	node->data = x;
    	node->next = NULL;
    	node->prev = NULL;
    	return node;
    }
    
    //初始化
    LTNode* ListInit()
    {
    	LTNode* phead = BuyListNode(-1);
    	phead->next = phead;
    	phead->prev = phead;
    	return phead;
    }
    
    //判断链表是否为空
    bool ListEmpty(LTNode* phead)
    {
    	assert(phead);
    	return phead->next != phead;
    }
    
    //打印
    void printList(LTNode* phead)
    {
    	LTNode* cur = phead->next;
    	while (cur != phead)
    	{
    		printf("%d->", cur->data);
    		cur = cur->next;
    	}
    	printf("NULL\n");
    }
    
    //尾插
    void ListPushBack(LTNode* phead, LTDataType x)
    {
    	assert(phead);
    
    	/*
    		//可以直接调用void ListInsert来实现
    		ListInsert(phead , x);
    		//代码复用
    	*/
    
    	LTNode* newNode = BuyListNode(x);
    	LTNode* tail = phead->prev;
    	newNode->next = phead;
    	newNode->prev = tail;
    	tail->next = newNode;
    	phead->prev = newNode;
    }
    
    //头插
    void ListPushFront(LTNode* phead, LTDataType x)
    {
    	assert(phead);
    
    	/*
    		//可以直接调用void ListInsert来实现
    		ListInsert(phead->next , x);
    		//代码复用
    	*/
    
    	LTNode* newNode = BuyListNode(x);
    	LTNode* pheadNext = phead->next;
    	phead->next = newNode;
    	newNode->prev = phead;
    	newNode->next = pheadNext;
    	pheadNext->prev = newNode;
    }
    
    //尾删
    void ListPopBack(LTNode* phead)
    {
    	assert(phead);
    	assert(ListEmpty(phead));
    
    	/*
    		//可以复用ListErase函数来实现后面的代码
    		ListErase(phead->prev);
    	*/
    	
    
    	LTNode* tail = phead->prev;
    	LTNode* tailPrev = tail->prev;
    	phead->prev = tailPrev;
    	tailPrev->next = phead;
    
    	free(tail);
    }
    
    //头删
    void ListPopFront(LTNode* phead)
    {
    	assert(phead);
    	assert(ListEmpty(phead));
    
    	/*
    		//可以复用ListErase函数来实现后面的代码
    		ListErase(phead->next);
    	*/
    
    	LTNode* next = phead->next;
    	phead->next = next->next;
    	next->next->prev = phead;
    
    	free(next);
    }
    
    //在pos位置前插入x
    void ListInsert(LTNode* pos, LTDataType x)
    {
    	assert(pos);
    
    	LTNode* prev = pos->prev;
    	LTNode* newNode = BuyListNode(x);
    
    	prev->next = newNode;
    	newNode->prev = prev;
    	newNode->next = pos;
    	pos->prev = newNode;
    }
    
    //删除pos位置节点
    void ListErase(LTNode* pos)
    {
    	assert(pos);
    	LTNode* prev = pos->prev;
    	LTNode* next = pos->next;
    
    	prev->next = next;
    	next->prev = prev;
    	free(pos);
    }
    
    //求链表长度
    int ListSize(LTNode* phead)
    {
    	assert(phead);
    	LTNode* cur = phead->next;
    	int size = 0;
    	while (cur != phead)
    	{
    		++size;
    		cur = cur->next;
    	}
    	return size;
    }
    	
    //销毁
    void ListDestory(LTNode* phead)
    {
    	assert(phead);
    	LTNode* cur = phead->next;
    	while (cur != phead)
    	{
    		LTNode* next = cur->next;
    		ListErase(cur);
    		cur = next;
    	}
    	free(phead);
    }

test.c文件  用于测试接口函数正确性

#define _CRT_SECURE_NO_WARNINGS 1
    
    #include"List.h"
    
    //尾插测试
    void ListTest1()
    {
    	LTNode* plist = ListInit();
    	
    	ListPushBack(plist, 1);
    	ListPushBack(plist, 2);
    	ListPushBack(plist, 3);
    	ListPushBack(plist, 4);
    	ListPushBack(plist, 5);
    
    	printList(plist);
    
    }
    
    //头插测试
    void ListTest2()
    {
    	LTNode* plist = ListInit();
    
    	ListPushFront(plist, 1);
    	ListPushFront(plist, 2);
    	ListPushFront(plist, 3);
    	ListPushFront(plist, 4);
    	ListPushFront(plist, 5);
    
    	printList(plist);
    	 
    }
    
    //尾删测试
    void ListTest3()
    {
    	LTNode* plist = ListInit();
    
    	ListPushFront(plist, 1);
    	ListPushFront(plist, 2);
    	ListPushFront(plist, 3);
    	ListPushFront(plist, 4);
    	ListPushFront(plist, 5);
    	printList(plist);
    
    	ListPopBack(plist);
    	ListPopBack(plist);
    	ListPopBack(plist);
    	ListPopBack(plist);
    
    	printList(plist);
    }
    
    //头删测试
    void ListTest4()
    {
    	LTNode* plist = ListInit();
    
    	ListPushBack(plist, 1);
    	ListPushBack(plist, 2);
    	ListPushBack(plist, 3);
    	ListPushBack(plist, 4);
    	ListPushBack(plist, 5);
    	printList(plist);
    
    	ListPopFront(plist);
    	ListPopFront(plist);
    	ListPopFront(plist);
    	ListPopFront(plist);
    	
    	printList(plist);
    }
    
    
    void ListTest5()
    {
    	LTNode* plist = ListInit();
    
    	ListPushBack(plist, 1);
    	ListPushBack(plist, 2);
    	ListPushBack(plist, 3);
    	ListPushBack(plist, 4);
    	ListPushBack(plist, 5);
    	printList(plist);
    
    	ListDestory(plist);
    
    	//printList(plist);
    }
    
    int main()
    {
    	//ListTest1();
    	ListTest1();
    
    	return 0;
    }

[a76f853e1d92495db0d0291de735baff.png]: https://img-blog.csdnimg.cn/a76f853e1d92495db0d0291de735baff.png
[d1daae589d5e490f9608a0f4348ad746.png]: https://img-blog.csdnimg.cn/d1daae589d5e490f9608a0f4348ad746.png
[e6b3e044c312460b901f8cb511552164.png]: https://img-blog.csdnimg.cn/e6b3e044c312460b901f8cb511552164.png
[e5e88b874d4c4fc98926ba77ad619716.png]: https://img-blog.csdnimg.cn/e5e88b874d4c4fc98926ba77ad619716.png
[d7c586ee3858477590b9a196d79097bc.png]: https://img-blog.csdnimg.cn/d7c586ee3858477590b9a196d79097bc.png
[d7ef27007a7a4512984dbd601ba610c5.png]: https://img-blog.csdnimg.cn/d7ef27007a7a4512984dbd601ba610c5.png
[abd51ddd629b42b99e8e8f3e71b6f2bf.png]: https://img-blog.csdnimg.cn/abd51ddd629b42b99e8e8f3e71b6f2bf.png
[188e23d9b8bf40ab8f65b8d0f6fd1c9a.png]: https://img-blog.csdnimg.cn/188e23d9b8bf40ab8f65b8d0f6fd1c9a.png
[db70c06568a24b0784ec648f0d992bda.png]: https://img-blog.csdnimg.cn/db70c06568a24b0784ec648f0d992bda.png
[da7d7b56a01c4babb40a9c9ee6f715f1.png]: https://img-blog.csdnimg.cn/da7d7b56a01c4babb40a9c9ee6f715f1.png
[08f64e076f3d4069b16a927c642eff10.png]: https://img-blog.csdnimg.cn/08f64e076f3d4069b16a927c642eff10.png
[a2a90d5ab98c4b57a67e8cdfbcf5f124.png]: https://img-blog.csdnimg.cn/a2a90d5ab98c4b57a67e8cdfbcf5f124.png
[cb3e438d8a614723b97cceb3b9706e99.png]: https://img-blog.csdnimg.cn/cb3e438d8a614723b97cceb3b9706e99.png