数据结构--双链表

目录

一、引言

二 、链表的分类

1.单向或双向

2.带头或不带头 

3.循环或不循环 

 三、双链表的概念与基本结构

1.概念

2.基本结构 

三、双链表的常见操作

1.创建节点

2.初始化 

3.头插

4.尾插

5.头删

6.尾删

7.打印

8.查找

9.插入节点

10.删除节点

11.销毁链表

五、完整代码

1.List.h

2.List.c

3.test.c

六、总结


一、引言

双链表是一种在节点之间通过两个指针进行连接的数据结构,每个节点都有两个指针:一个指向前一个节点,另一个指向下一个节点。带头节点的双链表在实际应用中非常常见,本文将详细介绍其实现方法,并提供完整的 C 语言代码示例。

二 、链表的分类

链表的结构⾮常多样,以下情况组合起来就有8种(2 x 2 x 2)链表结构:

1.单向或双向

  • 单向链表:

    • 每个节点包含一个指向下一个节点的指针。
    • 只能从头到尾单向遍历。
    • 插入和删除操作较简单,但需要从头开始查找节点。
  • 双向链表:

    • 每个节点包含两个指针,一个指向下一个节点,一个指向前一个节点。
    • 可以从头到尾或尾到头双向遍历。
    • 插入和删除操作更灵活,但每个节点占用更多内存。

2.带头或不带头 

  • 带头节点:

    • 链表有一个额外的头节点,它不存储实际数据,只作为链表的起始点。
    • 操作如插入和删除更简单,因为头节点简化了边界条件处理。
  • 不带头节点:

    • 链表从第一个实际数据节点开始,没有额外的头节点。
    • 需要特别处理空链表和边界情况。

3.循环或不循环 

  • 循环链表:

    • 链表的尾节点指向头节点,形成一个循环结构。
    • 遍历时可以从任何节点开始,不会遇到“末尾”问题。
  • 非循环链表:

    • 链表的尾节点指向 NULL,表示链表的结束。
    • 遍历时需要检查是否到达链表末尾。

虽然有这么多的链表的结构,但是我们实际中最常⽤还是两种结构:单链表和双向带头循环链表
1. ⽆头单向⾮循环链表:结构简单,⼀般不会单独⽤来存数据。实际中更多是作为其他数据结 构的⼦结构,如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。
2. 带头双向循环链表:结构最复杂,⼀般⽤在单独存储数据。实际中使⽤的链表数据结构,都 是带头双向循环链表。另外这个结构虽然结构复杂,但是使⽤代码实现以后会发现结构会带 来很多优势,实现反⽽简单了,后⾯我们代码实现了就知道了。

本节我们所讲的双链表即为双向带头循环链表。 

 三、双链表的概念与基本结构

1.概念

双链表简介
双链表是一种链表变体,每个节点都包含三个部分:
存储的数据。
指向前一个节点的指针(prev)。
指向下一个节点的指针(next)。
带头节点的双链表有一个特殊的节点称为头节点,它不存储有效数据,只是作为链表的一个起始辅助节点存在。头节点的 prev 指针指向自己,next 指针指向链表的第一个有效节点。

2.基本结构 

双链表的基本结构如下:

typedef struct ListNode
{
	DataType data;//数据域
	struct ListNode* prev;//指针域,指向前一个节点
	struct ListNode* next;//指针域,指向后一个节点
}LN;

三、双链表的常见操作

1.创建节点

//申请节点
LN* ListBuyNode(DataType x)
{
	LN* node = (LN*)malloc(sizeof(LN));
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	node->data = x;
	node->prev = node->next = node;//前后指针都指向自己,使得链表循环起来
}

2.初始化 

//初始化
void ListInit(LN** pphead)
{
	*pphead = ListBuyNode(-1);//头节点,随便给一个值(用不到)
}

3.头插

//头插
void ListPushFront(LN* phead, DataType x)
{
	assert(phead);
	LN* newnode = ListBuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
	//上面两行代码位置不能交换
}

4.尾插

//尾插
void ListPushBack(LN* phead, DataType x)
{
	assert(phead);
	LN* newnode = ListBuyNode(x);
	newnode->prev = phead->prev;//新节点prev指向原来的尾节点
	newnode->next = phead;//新节点next指向头节点
	phead->prev->next = newnode;//原来的尾节点next指向newnode
	phead->prev = newnode;//头节点的prev指向newnode
	//上面两行代码位置不能交换
}

5.头删

//头删
void ListPopFront(LN* phead)
{
	assert(phead && phead->next != phead);//链表必须有效且链表不为空
	LN* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;
	//删除del节点
	free(del);
	del = NULL;
}

 

6.尾删

//尾删
void ListPopBack(LN* phead)
{
	assert(phead&&phead->next!=phead);//链表必须有效且链表不为空
	LN* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	//删除del节点
	free(del);
	del = NULL;
}

7.打印

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

8.查找

//查找
LN* ListFind(LN* phead, DataType x)
{
	LN* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;//找到了
		}
		pcur = pcur->next;
	}
	return NULL;//没有找到 
}

9.插入节点

//插入,pos节点后插入
void ListInsert(LN* pos, DataType x)
{
	assert(pos);
	LN* newnode = ListBuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}

10.删除节点

//删除
void ListErase(LN* pos)//这里不传二级指针,是为了保持接口一致性
{
	assert(pos);
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}

11.销毁链表

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

注:

LTErase和LTDestroy参数理论上要传一级,因为我们需要让形参的改变影响到实参,但是为了保持接口一致性才传的一级。传一级存在的问题是,当形参phead置为NULL后,实参plist不会被修改为NULL,因此解决办法是:调用完方法后手动将实参置为NULL~ 

五、完整代码

1.List.h

该部分放顺序表结构定义、函数的声明

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int DataType;
typedef struct ListNode
{
	DataType data;//数据域
	struct ListNode* prev;//指针域,指向前一个节点
	struct ListNode* next;//指针域,指向后一个节点
}LN;
//初始化
void ListInit(LN** pphead);
//尾插
void ListPushBack(LN*phead,DataType x);
//头插
void ListPushFront(LN*phead,DataType x);
//打印
void ListPrint(LN* phead);
//尾删
void ListPopBack(LN* phead);
//头删
void ListPopFront(LN* phead);
//查找
LN* ListFind(LN* phead, DataType x);
//插入,pos节点后插入
void ListInsert(LN* pos, DataType x);
//删除
void ListErase(LN* pos);
//销毁链表
void ListDestory(LN* phead);

2.List.c

该部分是函数功能的实现

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
//申请节点
LN* ListBuyNode(DataType x)
{
	LN* node = (LN*)malloc(sizeof(LN));
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	node->data = x;
	node->prev = node->next = node;//前后指针都指向自己,使得链表循环起来
}
//初始化
void ListInit(LN** pphead)
{
	*pphead = ListBuyNode(-1);//头节点,随便给一个值(用不到)
}
//尾插
void ListPushBack(LN* phead, DataType x)
{
	assert(phead);
	LN* newnode = ListBuyNode(x);
	newnode->prev = phead->prev;//新节点prev指向原来的尾节点
	newnode->next = phead;//新节点next指向头节点
	phead->prev->next = newnode;//原来的尾节点next指向newnode
	phead->prev = newnode;//头节点的prev指向newnode
	//上面两行代码位置不能交换
}
//头插
void ListPushFront(LN* phead, DataType x)
{
	assert(phead);
	LN* newnode = ListBuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
	//上面两行代码位置不能交换
}
//尾删
void ListPopBack(LN* phead)
{
	assert(phead&&phead->next!=phead);//链表必须有效且链表不为空
	LN* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	//删除del节点
	free(del);
	del = NULL;
}
//头删
void ListPopFront(LN* phead)
{
	assert(phead && phead->next != phead);//链表必须有效且链表不为空
	LN* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;
	//删除del节点
	free(del);
	del = NULL;
}
//打印
void ListPrint(LN* phead)
{
	LN* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
//查找
LN* ListFind(LN* phead, DataType x)
{
	LN* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;//找到了
		}
		pcur = pcur->next;
	}
	return NULL;//没有找到 
}
//插入,pos节点后插入
void ListInsert(LN* pos, DataType x)
{
	assert(pos);
	LN* newnode = ListBuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}
//删除
void ListErase(LN* pos)//这里不传二级指针,是为了保持接口一致性
{
	assert(pos);
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}
//销毁链表
void ListDestory(LN* phead)
{
	assert(phead);
	LN* pcur = phead->next;
	while (pcur != phead)
	{
		LN* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
}

3.test.c

测试,函数的调用

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
void test01()
{
	LN* plist = NULL;
	ListInit(&plist);
	/*ListPushBack(plist, 3);
	ListPushBack(plist, 2);
	ListPushBack(plist, 1);
	ListPushBack(plist, 0);*/
	ListPushFront(plist, 1);
	ListPushFront(plist, 2);
	ListPushFront(plist, 3);
	ListPushFront(plist, 4);
	// ListPopBack(plist);
	//ListPopFront(plist);
	LN* find = ListFind(plist, 3);
	//if (find == NULL)
	//	printf("没找到\n");
	//else
	//	printf("找到了\n");
	ListInsert(find, 99);
	ListErase(find);
	find = NULL;
	ListPrint(plist);
	ListDestory(plist);
	plist = NULL;

}
int main()
{
	test01();
	return 0;
}

六、总结

带头节点的双链表在进行节点的插入和删除操作时具有较好的灵活性。头节点的存在简化了链表操作的边界条件,减少了对空链表和链表边界的特殊处理。通过本文的实现和示例代码,你应该能掌握双链表的基本操作,并能够将其应用于实际的编程任务中。
希望这个博客对你有帮助!如果你有任何问题或者需要进一步的解释,欢迎在评论区留言。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/881177.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

gin配置swagger文档

一、基本准备工作 1、安装依赖包 go get -u github.com/swaggo/swag/cmd/swag go get -u github.com/swaggo/gin-swagger go get -u github.com/swaggo/files2、在根目录上配置swagger的路由文件 //2.初始化路由router : initialize.Routers()// 配置swaggerdocs.SwaggerInfo…

京东商品属性的详细api数据解析:颜色、尺寸与材质

京东&#xff08;JD.com&#xff09;作为一个大型电商平台&#xff0c;其商品信息通过API接口提供给开发者或第三方服务使用&#xff0c;以便进行商品搜索、展示、分析等操作。然而&#xff0c;直接访问京东的详细商品属性&#xff08;如颜色、尺寸、材质等&#xff09;API通常…

uniapp|微信小程序 实现输入四位数 空格隔开

<template><page-meta :page-style"cssVar"></page-meta><view class"container"><u-navbartitle"优惠券兑换"placeholderbgColor"#fff":autoBack"true":titleStyle"{fontFamily: SourceHa…

Maven Helper 插件

推荐指数&#xff1a;★★★★★ 分析依赖冲突插件 Maven Helper插件就可免去命令行困扰。通过界面解决依赖冲突。 点击此按钮&#xff0c;切换到此工具栏 可进行相应操作&#xff1a; Conflicts&#xff08;查看冲突&#xff09;All Dependencies as List&#xff08;列表形…

Java 在 GIS 领域的学习路线?

Java是一门广泛应用于企业级开发的编程语言&#xff0c;而GIS则是一种常用于地理信息处理和分析的技术。将Java与GIS结合起来&#xff0c;可以在企业级应用中实现更多的功能和业务需求&#xff0c;且在实际领域越来越广泛。 Java在GIS中重要的作用 1、跨平台性 Java具有跨平台…

鸿蒙HarmonyOS开发:一次开发,多端部署(界面级)天气应用案例

文章目录 一、布局简介二、典型布局场景三、侧边栏 SideBarContainer1、子组件2、属性3、事件 四、案例 天气应用1、UX设计2、实现分析3、主页整体实现4、具体代码 五、运行效果 一、布局简介 布局可以分为自适应布局和响应式布局&#xff0c;二者的介绍如下表所示。 名称简介…

搜索引擎onesearch3实现解释和升级到Elasticsearch v8系列(一)-概述

简介 此前的专栏介绍Onesearch1.0和2.0&#xff0c;详情参考4 参考资料&#xff0c;本文解释onesearch 3.0&#xff0c;从Elasticsearch6升级到Elasticsearch8代码实现 &#xff0c;Elasticsearch8 废弃了high rest client&#xff0c;使用新的ElasticsearchClient&#xff0c;…

uniapp 如何自定义导航栏并自适应机型

如今的移动设备有各种不同的屏幕形状&#xff0c;如刘海屏、水滴屏等。这些异形屏会影响页面的布局&#xff0c;尤其是导航栏和底部栏的显示。通过获取安全区域信息&#xff0c;可以确保页面内容不会被异形屏的特殊区域遮挡。 在设计页面顶部导航栏时&#xff0c;可以根据 saf…

模拟自然的本质:与IBM量子计算研究的问答

量子计算可能是计算领域的下一个重大突破&#xff0c;但它的一般概念仍然处于炒作和猜测的现状&#xff1f;它能破解所有已知的加密算法吗&#xff1f;它能设计出治愈所有疾病的新分子吗&#xff1f;它能很好地模拟过去和未来&#xff0c;以至于尼克奥弗曼能和他死去的儿子说话…

【Redis入门到精通二】Redis核心数据类型(String,Hash)详解

目录 Redis数据类型 1.String类型 &#xff08;1&#xff09;常见命令 &#xff08;2&#xff09;内部编码 2.Hash类型 &#xff08;1&#xff09;常见命令 &#xff08;2&#xff09;内部编码 Redis数据类型 查阅Redis官方文档可知&#xff0c;Redis提供给用户的核心数据…

dockercompose指定配置文件

dockercompose指定配置文件 文件名字必须是以下的集中形式&#xff1a; docker-compose.yaml docker-compose.yml compose.yaml compose.yml 其他名字就失败的。 一般白眉大叔都是用 compose.yaml 这个格式&#xff0c; 用习惯了。 但是我们必须知道它有几种格式都是可以…

如何利用nw.js打包vue项目

引言 最近有一个开发windows桌面应用的需求, 需要将vue项目打包成.exe文件&#xff0c;最好是变成可安装版(非绿色版)。特此记录一下如何通过nw.js将vue项目打包成.exe。可能这种方式不是最优&#xff0c;仅供大家参考&#xff01; nw.js简介&#xff08;以下描述来自nw.js官…

C#|.net core 基础 - 扩展数组添加删除性能最好的方法

今天在编码的时候遇到了一个问题&#xff0c;需要对数组变量添加新元素和删除元素&#xff0c;因为数组是固定大小的&#xff0c;因此对新增和删除并不友好&#xff0c;但有时候又会用到&#xff0c;因此想针对数组封装两个扩展方法&#xff1a;新增元素与删除元素&#xff0c;…

大数据概念与价值

文章目录 引言大数据的概念高德纳咨询公司的定义麦肯锡全球研究所的定义什么是大数据&#xff1f; 大数据的特征Volume&#xff08;体积&#xff09;Variety&#xff08;种类&#xff09;Velocity&#xff08;速度&#xff09;Value&#xff08;价值&#xff09;Veracity&#…

【Redis入门到精通三】Redis核心数据类型(List,Set)详解

目录 Redis数据类型 ​编辑 1.List类型 &#xff08;1&#xff09;常见命令 &#xff08;2&#xff09;内部编码 2.Set类型 &#xff08;1&#xff09;常见命令 &#xff08;2&#xff09;内部编码 Redis数据类型 查阅Redis官方文档可知&#xff0c;Redis提供给用户的核…

ASP.NET Core高效管理字符串集合

我们在开发 Web 项目时经常遇到需要管理各种来源的字符串集合&#xff08;例如HTTP 标头、查询字符串、设置的值等&#xff09;的情况。合理的管理这些字符串集合不仅可以减少出bug的几率&#xff0c;也能提高应用程序的性能。ASP.NET Core 为我们提供了一种特殊的只读结构体 S…

多层感知机paddle

多层感知机——paddle部分 本文部分为paddle框架以及部分理论分析&#xff0c;torch框架对应代码可见多层感知机 import paddle print("paddle version:",paddle.__version__)paddle version: 2.6.1多层感知机&#xff08;MLP&#xff0c;也称为神经网络&#xff0…

有关JS下隐藏的敏感信息

免责声明&#xff1a;本文仅做分享&#xff01; 目录 JavaScript 介绍 核心组成 工具 FindSomething ** 浏览器检查 ** LinkFinder URLfinder ** SuperSearchPlus ** ffuf ParasCollector waymore Packer Fuzzer JS逆向 应用&#xff1a; 小结&#xff1a; Ja…

java-----IDE(集成开发环境)

IDE&#xff08;集成开发环境&#xff09; IDE&#xff08;集成开发环境&#xff09;-IDEA IDEA 介绍 1) IDEA 全称 IntelliJ IDEA2) 在业界被公认为最好的Java开发工具3) IDEA是JetBrains 公司的产品&#xff0c;总部位于捷克的首都布拉格4) 除了支持Java开发&#xff0c;还…

54.【C语言】 字符函数和字符串函数(strncpy,strncat,strncmp函数)

和strcpy,strcat,strcmp函数对应的是strncpy,strncat,strncmp函数 8.strncpy函数 *简单使用 cplusplus的介绍 点我跳转 翻译: 函数 strncpy char * strncpy ( char * destination, const char * source, size_t num ); 从字符串中复制一些字符 复制源(source)字符串的前num个…