当前位置：
  1. 首页
  2. 全部分类
  3. 数据结构与算法
  4. 正文

【数据结构】链表其实并不难 —— 手把手带你实现双向链表

数据结构与算法 0 2

csv

文章目录

Date

0. 前言

之前，我们已经学习了单链表，在实现单链表的过程中，也发现了单链表的缺陷。

虚拟环境

比如在尾插时，需要找到尾结点；尾删时，需要找到尾结点的前一个节点；在任意位置删除时需要找到该位置前一个节点等等等…这些都需要用时间复杂度为 O(N)的算法来处理。

rsync

所以我们说，单链表 ，也就是单向无头非循环链表，是一个有缺陷的结构 ，它有时会作为其他数据结构的 子结构 。

Material

基于单链表的这些缺陷，带头双向循环链表，也就是我们说的 双向链表 就完美的解决了 单链表 的这些问题。

解压缩

1. 双向链表的概念

我们首先分析一下 双向链表 ，双向链表实际上就是 带头双向循环链表 。

json语法规则

之前我们说过链表的几种结构：带头 / 不带头，单向 / 双向，循环 / 非循环，而双向链表很明显就是这些结构中，最复杂结构 的集合。

transformer

它的主要表现就是，含有头结点 —— 有一个不存储有效数据的虚拟节点，链表永不为空，所以无需传二级指针，只需要改变节点之间的链接关系；双向 —— 可以通过一个节点直接找到上一个节点；循环 —— 链表头尾相连呈环状，链表中无空指针。

CCF-CSP考试

那么它的 结构 设计就必然有些特殊，由于是双向，所以要比 单链表 多一个 prev 用来找到上一个节点。同样的 单链表 有的 next、data 也必不可少；再考虑上它的循环结构，那么就需要最后一个节点的 next 能找到第一个节点，第一个节点的 prev 能找到最后一个节点。

鍓嶇

我们可以大概画出它的 示意图：

负载均衡

image-20221022144955761

安全

从这幅图就可以看出，双向链表的结构十分完美，它完美解决了 单链表插入、删除数据时复杂的操作，加上存储单元之间的链接多样，让数据之间的管理变得非常简单！

threejs

那么它实现起来到底复不复杂呢，我们接下来就开始设计 双向链表 ，我们在实现的过程中感受！

数学建模

2. 双向链表的实现

2.1 结构设计

双向链表 比 单链表 的结构多一个 prev 指针，用来记录上一个节点的地址。

remove方法 

typedef struct ListNode
{
	LTDataType data; // 保存数据
	struct ListNode* next; // 记录下一个节点的地址
	struct ListNode* prev; // 记录上一个节点的地址
}LTNode;

2.2 接口总览

实现一个 双向链表 ，总共需要以下接口：

render 

// 初始化
LTNode* ListInit(); // 使用返回值处理
// 打印
void ListPrint(LTNode* phead);
// 尾插
void ListPushBack(LTNode* phead, LTDataType x);
// 尾删
void ListPopBack(LTNode* phead);
// 头插
void ListPushFront(LTNode* phead, LTDataType x);
// 头删
void ListPopFront(LTNode* phead);
// 查找元素
LTNode* ListFind(LTNode* phead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(LTNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(LTNode* pos);
// 销毁双向链表
void ListDestroy(LTNode* phead);

虽然接口和 单链表 差不多，但是这些接口的实现，远远比单链表 简单 地多~

hibernate

而且这里有一个特殊的地方就是函数传参时，初始化接口参数 无参 ，其他接口传的是 一级指针 ，这是为什么？

Set

首先需要明确的一点是，双向链表是带头的，含有一个头结点，就是我们单链表中提到的 哨兵位 。哨兵位不存储 有效数据 ，存在哨兵位链表就不为空，并使实现接口时更加方便。需要注意的是 只要存在哨兵位，链表的第一个节点就是哨兵位后面第一个节点 。

web3.js

  1. 初始化函数 无参。双向链表初始化只需要创建哨兵位，然后得到哨兵位即可。在这里我也同样可以使用二级指针来操作，但是为了配合下面的接口函数，就不那么“突出”了~
  2. 其他接口参数传 一级指针，是因为我在进行相应的操作时，由于哨兵位不存储有效数据并且我并不需要改变哨兵位，所以我只需要找到哨兵位然后改变它的链接关系就可以，所以 不需要二级指针 。

2.3 初始化

创建一个 哨兵位 节点。

Onvif协议

双向链表 在只有一个哨兵位时，让它自己指向自己。哨兵位的 next 指向它自己的prev ，哨兵位的 prev 指向它自己的 next 。说白了就是一个特殊的环形链表。

C语言深度解剖

image-20221022145010877

microsoft

由于我们这里使用的是返回值的形式，所以只要创建返回就可以。

decorator 

// 初始化
LTNode* ListInit()
{
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	// 双向带头循环链表的prev指向next，next指向prev
	// 但是这里只有一个节点，所以只能让它自己指向自己
	if (phead == NULL)
	{
		perror("ListInit");
		exit(-1);
	}
	phead->next = phead;
	phead->prev = phead;
	
	return phead;
}

2.4 创建新节点

当 双向链表 需要插入元素时，需要创建节点。这就很简单，直接 malloc 开辟，然后把值存入，两个指针给为空指针，然后返回节点就行。

大数据 

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

	return newnode;
}

2.5 尾插

为什么说 双向链表 很完美，实现也比单链表 简单 ，从尾插就能看出来。

域名

我们 单链表 的尾插，在链表为空时，需要特殊处理；在平常插入时，需要找到 尾结点 ，改变尾结点的链接。

私有属性

对于 双向链表 的尾结点，就是哨兵位的 prev ，将其拷贝一份，放在 tail 中，然后将 tail 的 next 链接至新节点 newnode ，然后将 newnode 的 prev 链接到 tail。在处理一下 newnode 的 prev 和 tail 的链接就可以了~ 且这些步骤没有先后顺序 ~

pytorch

image-20221022155719811

需求

怎么样，单链表 要 O(N) 的时间复杂度的尾插，在这里只需要用 O(1) 就可以完成，是不是简单多了？

CPUProfiler 

// 尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);// 一定不为空-->有哨兵位

	LTNode* tail = phead->prev;// 尾就是prev，由于是双向循环链表，所以头的prev就是尾
	LTNode* newnode = BuyListNode(x);

	// phead              tail            newnode
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

2.6 头插

对于 头插 来说，首先需要创建节点。

干货

然后将哨兵位的后一个节点，即链表实际上的 第一个节点 phead->next，给定一个新节点 newnode 。然后将 newnode 的 prev 链接到 哨兵位。再将 newnode 的 next 给定为先前的第一个节点 next 。然后改变该节点 (next)的 prev 和 newnode 的链接关系。

image-20221022160633145

// 头插
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	LTNode* next = phead->next;
	
	phead->next = newnode;
	newnode->prev = phead;
	
	newnode->next = next;
	next->prev = newnode;
}

2.7 尾删

对于 双向链表 的尾删，只要找到尾结点的前一个节点改变它和哨兵位的连接关系即可。

如果要找到尾结点的前一个节点，那么我只需要通过 哨兵位 的 prev 找到 尾，在通过 尾 的 prev 就可以找到 尾结点的前一个节点。然后调整这个节点和哨兵位的链接关系，然后 释放尾结点 就可以了。

但是要注意，当链表只有哨兵位的时候不能进行删除！！！

image-20221022162006011

// 尾删
void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);// 防止把哨兵位删掉 
	LTNode* tail = phead->prev; 
	LTNode* tailprev = tail->prev;
	free(tail);
	
	phead->prev = tailprev;
	tailprev->next = phead;
}

2.8 头删

对于头删来说，我需要删除链表的第一个节点，也就是 哨兵位的 next 节点 ，我需要改变 哨兵位 和 第二个节点 的链接关系，然后释放 第一个节点 。总体来说也很简单~

image-20221022170755020

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
    
	LTNode* next = phead->next;
	LTNode* nextNext = next->next;

	phead->next = nextNext;
	nextNext->prev = phead;
	free(next);
}

2.9 查找

对于查找一个元素在 双向链表 中存不存在，那肯定是采用遍历链表的形式。

但是对于 双向链表 来说，它是没有指向 NULL 的节点的，它是一个环，停不下来。所以我们要把循环的截止条件设定为 != phead ，这个条件就表示，已经遍历过一遍链表了，走到哨兵位了。

如果找到，返回该节点的地址；如果找不到返回 NULL 。

// 查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* cur = phead->next;

	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

2.10 在pos位置之前插入

在 pos 位置之前插入，那么通过 pos 的 prev 找到 pos 位置的上一个节点 posPrev ，然后改变 posPrev 和 新节点 newnode 之间的链接和 newnode 和 pos 之间的链接。和头插尾插思路大致相同。

image-20221022170928980

// 在pos位置之前插入
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* newnode = BuyListNode(x);

	LTNode* posPrev = pos->prev;

	newnode->prev = posPrev;
	posPrev->next = newnode;

	newnode->next = pos;
	pos->prev = newnode;
}

那么有了这个接口，那么我们就可以把它 复用 于 尾插 和 头插。

对于 尾插 来说， pos 位置就是 phead ，因为 phead 的前面就是链表的尾，在 phead 位置前插入，就是尾插：

void ListPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);
	ListInsert(phead, x);
}

对于 头插 来说，pos 位置就是 phead->next ，为第一个节点的前面，在 phead->next 位置前插入，就是头插：

void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}

2.11 在pos位置删除

在 pos 位置删除，只要找到 pos 的前一个节点 posPrev ，然后找到 pos 的后一个节点 posNext ，然后将这两个节点的 prev 和 next 建立正确的链接关系。然后释放 pos 节点，pos 节点置空。

但是注意，删除的位置不能是哨兵位。但是由于这里设计的原因，再传 phead 就显得有点不划算了，所以我们需要注意一下，pos 不能为哨兵位，自己控制好就可以了。

image-20221022171203777

void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;

	posPrev->next = posNext;
	posNext->prev = posPrev;

	free(pos);
	pos = NULL;
}

同样的，这个接口也能复用于 尾删 和 头删 。

对于 尾删 来说，pos 位置就是 phead->prev ，为链表的尾，删除 phead->prev 位置，就是尾删：

void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);// 防止把哨兵位删掉 

	ListErase(phead->prev);
}

对于 头删 来说，pos 位置就是 phead->next ，为链表的头，删除 phead->next 位置，就是头删：

// 头删
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);// 防止把哨兵位删掉 
    
	ListErase(phead->next);
}

2.12 打印

打印整个链表，就只需要遍历链表，控制好循环的停止条件：

// 打印
void ListPrint(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;

	while (cur != phead)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

2.13 销毁

我需要把 哨兵位 ，链表的节点 全部删除，那么我就要使用循环来删除。所以，销毁 双向链表 的思路 和 查找是差不多的，循环的结束条件为 != phead。在销毁的过程中，每次记住我当前节点的下一个节点，以便迭代。

但是当前接口函数中，哨兵位是不能正常删除的！！！

注意：由于在函数中，我释放了哨兵位，并要将其置空。释放是可以的，因为我知道哨兵位的地址，释放就可以，但是置空却完成不了。因为我的 哨兵位 是形参，改变形参并不能影响实参，所以我们还需要在主函数中将 哨兵位 置空(在这个部分就不展示了，马上会在完整代码中呈现)。

// 销毁
void ListDestroy(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);// 只销毁了形参，没有销毁实参，这里只是象征性的销毁一下
	phead = NULL;
}

3. 完整代码

List.h

#pragma once
/*
* c++中带头双向循环链表命名方式为List，所以我们也采用这个命名方式
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;
// 初始化
LTNode* ListInit();// 使用返回值处理
// 打印
void ListPrint(LTNode* phead);
// 尾插
void ListPushBack(LTNode* phead, LTDataType x);
// 尾删
void ListPopBack(LTNode* phead);
// 头插
void ListPushFront(LTNode* phead, LTDataType x);
// 头删
void ListPopFront(LTNode* phead);
// 查找元素
LTNode* ListFind(LTNode* phead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(LTNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(LTNode* pos);
// 销毁双向链表
void ListDestroy(LTNode* phead);

List.c

#define _CRT_SECURE_NO_WARNINGS 1 
#include "List.h"
// 初始化
LTNode* ListInit()
{
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	// 双向带头循环链表的prev指向next，next指向prev
	// 但是这里只有一个节点，所以只能让它自己指向自己
	if (phead == NULL)
	{
		perror("ListInit");
		exit(-1);
	}
	phead->next = phead;
	phead->prev = phead;	
	return phead;
}
// 创建新节点
LTNode* BuyListNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("ListPushBack");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
// 打印
void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

// 尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);// 一定不为空-->有哨兵位
	//LTNode* tail = phead->prev;// 尾就是prev，由于是双向循环链表，所以头的prev就是尾
	//LTNode* newnode = BuyListNode(x);

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

// 尾删
void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);// 防止把哨兵位删掉 
	/*LTNode* tail = phead->prev; 
	LTNode* tailprev = tail->prev;
	free(tail);
	
	phead->prev = tailprev;
	tailprev->next = phead;*/
	ListErase(phead->prev);
}

// 另一种写法
//void ListPopBack(LTNode* phead)
//{
//	assert(phead);
//	assert(phead->next != phead);// 防止把哨兵位删掉 
//	LTNode* tail = phead->prev; 
//	
//	phead->prev = tail->prev;
//	tail->prev->next = phead;
//	
//	free(tail); 	
//}

// 头插
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	/*LTNode* newnode = BuyListNode(x);
	LTNode* next = phead->next;
	
	phead->next = newnode;
	newnode->prev = phead;
	
	newnode->next = next;
	next->prev = newnode;*/

	ListInsert(phead->next, x);
}

// 头删
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	/*LTNode* next = phead->next;
	LTNode* nextNext = next->next;

	phead->next = nextNext;
	nextNext->prev = phead;
	free(next);*/
	ListErase(phead->next);
}

// 查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

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

// 在pos位置删除
void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
	pos = NULL;
}

// 销毁
void ListDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);// 只销毁了形参，没有销毁实参
	phead = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1 
#include "List.h"
// 测试尾插、尾删
void TestList1()
{
	LTNode* plist = ListInit();// 哨兵位
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);
	ListPrint(plist);

	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	// 双向链表的缺点
	// 当链表只剩下哨兵位时，链表为空
	// 如果这时候进行删除，会把哨兵位删掉  
	// ListPopBack(plist);
	ListPrint(plist);
}
// 测试头插、任意位置删除
void TestList2()
{
	LTNode* plist = ListInit();// 哨兵位
	ListPushFront(plist, 1);
	ListPushFront(plist, 2);
	ListPushFront(plist, 3);
	ListPushFront(plist, 4);
	ListPushFront(plist, 5);
	ListPrint(plist);

	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);
	ListPrint(plist);

	LTNode* pos = ListFind(plist, 2);
	if (pos)
	{
		ListErase(pos);
	}
	ListPrint(plist);

	ListDestroy(plist);
	plist = NULL;// 手动置空
}

int main()
{
	//TestList1();
	TestList2();

	return 0;
}

4. 结语

到这里，本篇博客就到此结束了。其实双向链表中还可以增加判空和计算链表大小的接口，也很简单，我这里就不实现了，大家有兴趣可以试一下。

总体来说，双向链表的结构是非常完美的，一般我们说的存储数据的链表其实也就是双向链表，单链表一般是作为其他数据结构的子结构的。所以双向链表因其结构，对于数据管理是十分高效的。而且实现起来也十分便捷~

如果觉得anduin写的还不错的话，还请一键三连！如有错误，还请指正！

我是anduin，一名C语言初学者，我们下期见！

上一篇 第十四届蓝桥杯第一期模拟赛 python
下一篇 AutoDL使用教程：1）创建实例 2）配置环境+上传数据 3）PyCharm2021.3专业版下载安装与远程连接完整步骤

相关文章

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

插入图片
浏览器会保存昵称、邮箱和网站cookies信息，下次评论时使用。