当前位置： 首页 > article >正文

【数据结构】双向链表（真正的零基础）

article 2025/2/11 16:26:29

链表是一种物理存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过指针的链接来实现的！在上篇我们学习了单向链表，而单向链表虽然空间利用率高，插入和删除也只需改变指针就可以达到！但是我们在每次查找、删除、访问.....时，都受到单向链表的一个特性干扰：单向不可逆，只能以遍历的形式去使用，这样使得需要从头到尾找到特定的节点再进行操作！今天我们来学习另外一种链表结构：双向链表。既然是零基础，我会从小白的角度进行讲解！放心食用！

目录

                                                            一.链表的分类

                                                   二.带头双向循环链表

                                                                               二.（1）链表节点设置

                                                                      二.（2）链表新增节点

                                                             二.（3）链表初始化 

                                                    二.（4）链表扩容节点

                                                    二.（5）链表打印

                                                    二.（6）在目标节点前面插入

                                                    二.（7）在目标节点后面插入

                                                    二.（8）链表头删

                                                    二.（9）链表尾删

                                                    二.（10）链表头插

                                                    二.（11）链表尾插

                                                    二.（12）删除中间目标节点

                                                    二.（13）释放双链表

               三.总结

               四.代码合并

一.链表的分类

这里就不介绍哈是链表了，如果对此感到疑惑，可以看我上一篇投稿，咱直接进入分类！

链表主要可以分为以下3大类：

单向链表：

单向链表是链表中最简单的一种，它由一系列节点组成，每个节点包含两个部分：指针域与数据域。指针域用来指向下一个节点的地址，数据域用来存储数据。以下是抽象草图，方便巧记：

双向链表：

 双向链表与单向链表不同，它的每个节点有两个指针（next跟prev）跟一个数据域，两个指针分别指向前一个节点和后一个节点。同样，如图巧记：

循环链表：
 循环链表是一种特殊的单链表，它的最后一个节点的指针指向头节点，形成一个“环”，如图：

在进行下面的学习之前，针对链表的各种分类，我们需要理清几个名词：

头指针：

头指针本质上是结构体类型的指针，指向一个节点，这个节点一般是 第一个节点 或者 头节点

头结点：

简单理解为在 第一个节点 前面还有一个节点，这个节点就称为头节点。头节点一般不存储数据

带头：

头指针指向头节点就称为带头节点，如图：

不带头： 

头指针指向第一个节点就称为不带头节点，如图：

针对这几种分类：带头或者不带头、单向或者双向、循环或者非循环 

我们总共可以组合八种链表，我们主要学习 无头双向非循环链表     带头双向循环链表    这两种！

八种链表结构中其中这两种最具代表性，另外六种便自然理解了！上一篇我们已经学完了第一种，今天我们来学习第二种！

注意：双链表一般需要改变四个指针的指向，因此建议大家画图理解！这样就可以轻松操作了！

二.带头双向循环链表

理解了上面几个名词后，我们就能轻易理解哈是带头双向循环链表了！

带头：无非就是第一个节点前还有一个头节点嘛！

双向：节点里面有两个指针，两个指针分别指向一前一后的节点

循环：尾节点的后指针指向头节点，头节点的前指针指向尾节点，达到封闭，形成循环！

二.（1）链表节点设置

不论怎样，我们都需要先创建一个结构体作为接下来各种功能的节点基础， 这个结构体里面有两个指针，一个数据域。这里为了缩短结构体类型，我们用 typedef 重定义以下，需要注意的是typedef重定义的这个结构体里面，结构体指针必须写完整，因为此处还属于声明阶段，后续才可以正常缩写。代码如下：

typedef struct Pointdef
{
	struct Pointdef* next;//指向下一个节点
	struct Pointdef* prev;//指向上一个节点
	int data;//数据域
}Pointdef;
二.（2）链表新增节点

因为我们不管初始化还是各种增添功能，都需要节点，所以我们先完成开辟节点的函数，让这个函数返回指向这个开辟好的节点指针，然后才可以进行初始化操作，代码如下：

//开辟新节点
Pointdef* Newspoint(int x)
{
	Pointdef* news = (Pointdef*)malloc(sizeof(Pointdef));

	if (news == NULL)
	{
		perror("malloc");
		return NULL;
	}
	//初始化新节点
	news->next = NULL;
	news->prev = NULL;
	news->data = x;

	return news;
}

我们刚开辟好的节点还没有连接，只是一个结构体大小，因此它的prev跟next指针都指向NULL，x就是初始化节点的数据域，如下图理解：

二.（3）链表初始化 

上面我们先调用 新增节点 的函数，在外面开辟一个节点作为头节点（如果有问题，可以先看下面的合并代码！），接下来对这个头节点进行初始化，将它作为头节点，此时头节点的next跟prev指针都应该指向自己（因为是循环链表，此时只有一个节点）。代码如下：

//链表初始化
void Initialize(Pointdef* head)
{
	head->next = head;
	head->prev = head;
}

二.（4）链表扩容节点

此时我们已经初始化了链表，下面我们给它新增几个节点，调用新增函数，改变节点指针指向，代码如下：

//链表扩容节点
Pointdef* tail = head;
for (int i = 2; i <= 5; i++)
{
	Pointdef* news = Newspoint(i);
	//连接
	tail->next = news;
	news->prev = tail;
	news->next = head;
	head->prev = news;

	tail = tail->next;
}

二.（5）链表打印

与单向链表访问区别不大，只需要注意是这里的链表是循环的，需要控制打印的条件不能是当前指针不能指向头节点，否则就是死循环了，代码如下： 

//链表打印
void Printf(Pointdef* head)
{
	Pointdef* tail = head->next;

	while (tail != head)
	{
		printf("%d <= ", tail->data);
		tail = tail->next;
	}
    printf("NULL\n");
}

二.（6）在目标节点前面插入

我们已经写好了一条双链表，那么我们只需要找到目标节点然后连接四个指针就行了，代码如下：

这里我们假设目标节点是 tail ，新节点 news  新节点前面的节点是 prev

//在目标节点前面插入
void FrontInsertion(Pointdef* tail ,int x)
{
	
	assert(tail);

	Pointdef* prev = tail->prev;
	Pointdef* news = Newspoint(x);

	prev->next = news;
	news->prev = prev;

	news->next = tail;
	tail->prev = news;
	
}

二.（7）在目标节点后面插入

将找到的目标节点作为参数，然后在函数中改变它的前后四个指针就行，如图：

//在目标节点后面插入
void OutInsertion(Pointdef* tail, int x)
{
	assert(tail);
	//目标节点的下一个节点不能是空，否则就是尾插了
	assert(tail->next);

	Pointdef* news = Newspoint(x);
	Pointdef* next = tail->next;

	tail->next = news;
	news->prev = tail;

	news->next = next;
	next->prev = news;
}


 二.（8）链表头删

头删咱直接将头节点作为参数就行了，再记录第二个节点方便释放，然后用四个指针连接头节点和第二个节点，最后记得释放第一个节点的空间，如图：

//链表头删
void Outomit(Pointdef* head,int x)
{
	assert(head);
	assert(head->next);

	Pointdef* tail = head->next->next;
	Pointdef* next = head->next;

	head->next = tail;
	tail->prev = head;

	free(next);
	next = NULL;
}

二.（9）链表尾删

这个咱就不多说了！就是先记录倒数第二个节点，将它作为尾节点就行了，同样记得释放空间，直接上代码：

//链表尾删
void Tailomit(Pointdef* head, int x)
{
	assert(head);

	Pointdef* prev = head->prev->prev;
	Pointdef* tail = head->prev;
	
	prev->next = head;
	head->prev = prev;

	free(tail);
	tail = NULL;
}

二.（10）链表头插

但凡插入节点的都具有很大的相似之处，无非就是将这个节点插入某处，通过记录附近节点的位置，再把新增节点的左右节点与它进行连接，看代码：

//链表头插
void Headinsert(Pointdef* head, int x)
{
	assert(head);

	Pointdef* tail = head->next;
	Pointdef* news = Newspoint(x);

	head->next = news;
	news->prev = head;

	news->next = tail;
	tail->prev = news;
}

二.（11）链表尾插
//链表尾插
void Tailinsert(Pointdef* head, int x)
{
	assert(head);

	Pointdef* tail = head->prev;
	Pointdef* news = Newspoint(x);

	tail->next = news;
	news->prev = tail;

	head->prev = news;
	news->next = head;
}

二.（12）删除中间目标节点

删除节点我们肯定要先找到目标节点，我们在链表中可以通过以下两种方式寻找：指针域  数据域，在上面的前后插入中，我们选择的指针查找方式，下面我们进行数据查找方式来删除：

//链表中间节点删除
void Omit(Pointdef* tail)
{
	Pointdef* pc = tail->prev;
	Pointdef* pt = tail->next;

	pc->next = pt;
	pt->prev = pc;

	free(tail);
	tail = NULL;
}

二.（13）释放双链表

咋从第一个节点释放到尾就OK了！注意：链表的空间不是连续的，因此需要一个个销毁！

//双链表销毁
void Undermine(Pointdef* head)
{
	assert(head);

	Pointdef* cur = head->next;
	Pointdef* tail = cur->next;

	while (cur != head)
	{
		tail = cur->next;

		free(cur);
		cur = tail;
	}
    free(head);
    head=NULL;

	printf("释放完毕\n");
}
三.总结

针对以上实现的双链表，其实针对整个链表，都有以下特点：

1：首先我们要有设计好开辟节点的函数，然后知道如何连接这些节点

2：头插、尾插、中间插其实都有很大的共性，只是目标地点稍微差异，这点大家可以画图理解！

3：删除某个节点需要及时释放该空间，避免空间泄漏。需要注意是先连接，再释放

4：针对为何单向链表很多涉及二级指针，而双向链表大多是一级指针？

因为单向链表有很多地方需要改变头指针（单向链表将第一个节点作为头节点）的指向，而双向链表是固定了哨兵节点，因此其它操作其实是针对结构体里面的指针操作的。该知识的原理是：对形参的改变不影响实参，如需改变形参，需要使用二级指针

5：双向链表为哈要从第一个节点开始释放？

双向链表的头节点是链表结构的一部分，不是数据节点，应该先释放数据节点，再释放链表结构

四.代码合并

流程文件（可以使用打印来进行功能的测试！）

#define _CRT_SECURE_NO_WARNINGS 1
#include"text.h"

int main()
{
	int x = 4;

	//链表新增节点
	Pointdef* head=Newspoint(1);

	//链表初始化
	void Initialize(head);

	//链表扩容节点
	Pointdef* tail = head;
	for (int i = 2; i <= 5; i++)
	{
		Pointdef* news = Newspoint(i);
		//连接
		tail->next = news;
		news->prev = tail;
		news->next = head;
		head->prev = news;

		tail = tail->next;
	}
	
	//链表打印
	Printf_t(head);

	//在目标节点前面插入                      
	tail = (head->next)->next;
	x = 6;
	FrontInsertion(tail, x);

	//在目标节点后面插入                
	OutInsertion(tail, x);

	//                                  测试点
	Printf_t(head);

	//链表头删
	x = 7;
	Outomit(head,x);

	//链表尾删
	x = 8;
	Tailomit(head, x);

	//                                  测试点
	Printf_t(head);

	//链表头插
	x = 1;
	Headinsert(head, x);

	//链表尾插
	x = 9;
	Tailinsert(head, x);

	//                                  测试点
	Printf_t(head);

	//链表中间节点删除
	x = 4;
	tail = head -> next;
	while (tail->data != x)
	{
		tail = tail->next;
	}
	Omit(tail);

	//                                   测试点
	Printf_t(head);

	//双链表销毁
	Undermine(head);

	return 0;
}

头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>

typedef struct Pointdef
{
	struct Pointdef* next;//指向下一个节点
	struct Pointdef* prev;//指向上一个节点
	int data;//数据域
}Pointdef;

//链表新增节点
Pointdef* Newspoint(int x);
//链表初始化
void Initialize(Pointdef* head);
//链表打印
void Printf_t(Pointdef* head);
//在目标节点前面插入
void FrontInsertion(Pointdef* tail, int x);
//在目标节点后面插入
void OutInsertion(Pointdef* tail, int x);
//链表头删
void Outomit(Pointdef* head ,int x);
//链表尾删
void Tailomit(Pointdef* head, int x);
//链表头插
void Headinsert(Pointdef* head, int x);
//链表尾插
void Tailinsert(Pointdef* head, int x);
//链表中间节点删除
void Omit(Pointdef* tail);
//双链表销毁
void Undermine(Pointdef* head);

函数执行文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"text.h"

//链表新增节点
Pointdef* Newspoint(int x)
{
	Pointdef* news = (Pointdef*)malloc(sizeof(Pointdef));

	if (news == NULL)
	{
		perror("malloc");
		return NULL;
	}
	//初始化新节点
	news->next = NULL;
	news->prev = NULL;
	news->data = x;

	return news;
}

//链表初始化
void Initialize(Pointdef* head)
{
	head->next = head;
	head->prev = head;
}

//链表打印
void Printf_t(Pointdef* head)
{
	Pointdef* tail = head->next;

	while (tail != head)
	{
		printf("%d <= ", tail->data);
		tail = tail->next;
	}
	printf("NULL\n");
}

//在目标节点前面插入
void FrontInsertion(Pointdef* tail ,int x)
{
	
	assert(tail);

	Pointdef* prev = tail->prev;
	Pointdef* news = Newspoint(x);

	prev->next = news;
	news->prev = prev;

	news->next = tail;
	tail->prev = news;
	
}

//在目标节点后面插入
void OutInsertion(Pointdef* tail, int x)
{
	assert(tail);
	//目标节点的下一个节点不能是空，否则就是尾插了
	assert(tail->next);

	Pointdef* news = Newspoint(x);
	Pointdef* next = tail->next;

	tail->next = news;
	news->prev = tail;

	news->next = next;
	next->prev = news;
}

//链表头删
void Outomit(Pointdef* head,int x)
{
	assert(head);
	assert(head->next);

	Pointdef* tail = head->next->next;
	Pointdef* next = head->next;

	head->next = tail;
	tail->prev = head;

	free(next);
	next = NULL;
}

//链表尾删
void Tailomit(Pointdef* head, int x)
{
	assert(head);

	Pointdef* prev = head->prev->prev;
	Pointdef* tail = head->prev;
	
	prev->next = head;
	head->prev = prev;

	free(tail);
	tail = NULL;
}

//链表头插
void Headinsert(Pointdef* head, int x)
{
	assert(head);

	Pointdef* tail = head->next;
	Pointdef* news = Newspoint(x);

	head->next = news;
	news->prev = head;

	news->next = tail;
	tail->prev = news;
}

//链表尾插
void Tailinsert(Pointdef* head, int x)
{
	assert(head);

	Pointdef* tail = head->prev;
	Pointdef* news = Newspoint(x);

	tail->next = news;
	news->prev = tail;

	head->prev = news;
	news->next = head;
}

//链表中间节点删除
void Omit(Pointdef* tail)
{
	Pointdef* pc = tail->prev;
	Pointdef* pt = tail->next;

	pc->next = pt;
	pt->prev = pc;

	free(tail);
	tail = NULL;
}

//双链表销毁
void Undermine(Pointdef* head)
{
	assert(head);

	Pointdef* cur = head->next;
	Pointdef* tail = cur->next;

	while (cur != head)
	{
		tail = cur->next;

		free(cur);
		cur = tail;
	}
	free(head);
	head = NULL;

	printf("释放完毕\n");
}


http://www.kler.cn/a/540876.html

相关文章：

  • python-leetcode 23.回文链表
  • 防御保护-----前言
  • 推荐一个免费的、开源的大数据工程学习教程
  • 云计算——AWS Solutions Architect – Associate（saa）4.安全组和NACL
  • 移动(新)魔百盒刷机教程[M301A_YS]
  • 【漫话机器学习系列】088.常见的输出层激活函数（Common Output Layer Activation Functions）
  • Rust 测试组织指南：单元测试与集成测试
  • 前端-导出png,jpg,pptx,svg
  • 【Kubernetes】常用命令全解析：从入门到实战（上）
  • 【Linux】深入理解linux权限
  • 【开源免费】基于SpringBoot+Vue.JS公寓报修管理系统（JAVA毕业设计）
  • VBA语言的软件工程
  • 《LeetCode Hot100》 Day01
  • 常见的前端框架和库有哪些
  • 04：定时器
  • ArcGIS中的空值问题
  • Java中的设计模式应用与最佳实践
  • 本地部署模型全攻略阶段二_3---Kiln AI
  • 51单片机独立按键的基本操作
  • 区块链可投会议CCF B--ICWS 2025 截止3.3 附2024录用率
  • win11+mac键盘+PowerToys 重映射热键
  • 随手记：小程序手机号一键登录
  • R语言的软件开发工具
  • 如何使用C++将处理后的信号保存为PNG和TIFF格式
  • 基于微信小程序的博物馆预约系统的设计与实现
  • Web UI自动化测试中的显示等待、隐式等待有什么区别？