【数据结构】-- 单链表 vs 双向链表

🌈 个人主页：白子寰
🔥 分类专栏：python从入门到精通，魔法指针，进阶C++，C语言，C语言题集，C语言实现游戏👈 希望得到您的订阅和支持~
💡 坚持创作博文(平均质量分82+)，分享更多关于深度学习、C/C++，python领域的优质内容！（希望得到您的关注~） 

目录

 单链表和双向链表的比较

链表的打印

单链表

双向链表 

初始化

双向链表

开辟空间，写入新数据

单链表

双向链表

尾部插入数据

单链表

双向链表

头部插入数据

单链表 

双向链表

尾部删除数据

单链表

双向链表

头部删除数据

单链表

双向链表

查找

单链表 

双向链表 

在指定位置之前插入数据 

单链表

在指定位置之后插入数据

单链表

双向链表 

 删除指定位置数据

单链表

双向链表

删除指定位置后的数据

单链表

销毁链表

单链表

双向链表

 单链表和双向链表的比较

单向链表双向链表
指代不同链表的链接方向是单向的，访问链表时时要顺序读取从头开始访问每个数据的节点都有两个指针，即直接前驱和直接后驱
优点不同单个节点创建方便，普通的线性内存通常在创建的时候就需要设定数据的大小，节点的访问方便，可以通过循环/递归的方法访问到任意数据从双向链表中的任意一个节点开始，方便访问前驱节点和后继节点
缺点不同增加/删除节点复杂，需要多分配一个指针存储空间平均访问效率低于线性表，只能从头到尾遍历，只能找到后继，无法找到前驱（只能前进）

链表的打印

单链表

//链表的打印
void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

双向链表 

//打印
void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->dada);
		pcur = pcur->next;
	}
	printf("\n");
}

初始化

双向链表

//双向链表初始化
LTNode* LTInit()
{
	//哨兵位设置为-1
	LTNode* phead = SLTBuyNode(-1);
	return phead;
}

开辟空间，写入新数据

单链表

//开辟空间，写入新数据
SLTNode* SLTbuyNode(SLTDatatype x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}

	//先插入，后数据为空（后为空）
	newnode->data = x;
	newnode->next = NULL;

	return newnode;//返回数据
}

双向链表

//扩容，申请新节点
LTNode* SLTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//扩容
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	//数据赋值
	newnode->dada = x;
	//指向自己
	newnode->next = newnode->prev = newnode;

	return newnode;
}

尾部插入数据

单链表

//尾插
void SLTPushBack(SLTNode** pphead, SLTDatatype x)
{
	//传的参数不为空
	assert(pphead);

	SLTNode*newnode = SLTbuyNode(x);
	//链表为空，新节点作为phead
	//*pphead是指向第一个节点的指针
	if (*pphead == NULL)//头节点为空
	{
		*pphead = newnode;
		return;
	}

	//链表不为空，找尾节点
	//ptail作为尾节点
	SLTNode* ptail = *pphead;
	//先方向，后数据
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	ptail->next = newnode;
}

双向链表

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = SLTBuyNode(x);
	
	newnode->next = phead;
	newnode->prev = phead->prev;

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

头部插入数据

单链表 

//头插
void SLTPushFront(SLTNode** pphead, SLTDatatype x)
{
	//传参有效
	assert(pphead);
	//开辟空间，新数据进入
	SLTNode* newnode = SLTbuyNode(x);

	//先方向，后数据
	newnode->next = *pphead;
	*pphead = newnode;
}

双向链表

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = SLTBuyNode(x);

	newnode->next = phead->next;
	newnode->prev = phead;

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

尾部删除数据

单链表

//尾删
void SLTPopBack(SLTNode** pphead)
{
	//保证传参数据有效
	assert(pphead);
	//链表不能为空
	assert(*pphead);

	//链表不为空
	//链表只有一个节点
	if ((*pphead)->next==NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}

	//有多个节点
	SLTNode* prev = NULL;
	SLTNode* ptail = *pphead;
	while (prev->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}
	prev = NULL;

	//销毁尾节点
	free(ptail);
	ptail = NULL;
}

双向链表

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);

	LTNode* del = phead->prev;

	del->prev->next = phead;
	phead->prev = del->prev;

	free(del);
	del = NULL;
}

头部删除数据

单链表

//头删
void SLTPopFront(SLTNode** pphead)
{
	//保证传参有效
	assert(pphead);
	//保证链表有效
	assert(*pphead);

	//让第二个节点成为新的头
	SLTNode* next = (*pphead)->next;
	//把旧的头节点释放掉
	free(*pphead);

	*pphead = next;//第一个节点 = 原来第二个节点
}

双向链表

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);

	LTNode* del = phead->next;

	phead->next = del->next;
	del->next->prev = phead;

	free(del);
	del = NULL;
}

查找

单链表 

SLTNode* SLTFind(SLTNode** pphead, SLTDatatype x)
{
	//保证传参有效
	assert(pphead);

	//遍历链表
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有找到
	return NULL;
}

双向链表 

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

	LTNode* pcur = phead->next;

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

在指定位置之前插入数据 

单链表

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDatatype x)
{
	//保证传参有效
	assert(pphead);
	//保证指定位置数据有效
	assert(pos);
	//链表也不能为空
	assert(*pphead);

	//新节点，开辟新空间
	SLTNode* newnode = SLTbuyNode(x);
	//pos刚好是头节点
	if (newnode->next = *pphead)
	{
		//头插
		SLTPushFront(pphead, x);
		return;
	}

	//pos不是头节点的情况
	SLTNode* prev = *pphead;
	if (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = newnode;
	newnode->next = pos;
}

在指定位置之后插入数据

单链表

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDatatype x)
{
	//保证目标数据有效
	assert(pos);

	//创建新节点
	SLTNode* newnode = SLTbuyNode(x);

	//先方向，后数据
	newnode->next = pos->next;
	pos->next = newnode;
}

双向链表 

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* newnode = SLTBuyNode(x);
	newnode->prev = pos;
	newnode->next = pos->next;

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

 删除指定位置数据

单链表

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	//保证传的参数有效
	assert(pphead);
	//保证单链表有效
	assert(*pphead);
	//保证目标数据有效
	assert(pos);

	//pos刚好是头节点，没有前驱节点
	if (*pphead == pos)
	{
		//头删
		SLTPopFront(pphead);
		return;
	}

	//pos不是头节点
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}

	//释放
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}

双向链表

//删除pos位置的数据
void LTErase(LTNode* pos)
{
	assert(pos);

	LTNode* del = pos;
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;

	free(del);
	del = NULL;
}

删除指定位置后的数据

单链表

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
	//保证目标数据有效
	assert(pos);
	//pos->next数据有效
	assert(pos->next);

	SLTNode* del = pos->next;
	pos->next = pos->next->next;

	//释放
	free(del);
	del = NULL;
}

销毁链表

单链表

//销毁链表
void SListDesTroy(SLTNode** pphead)
{
	//保证传的参数有效
	assert(pphead);
	//保证链表有效
	assert(*pphead);

	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

双向链表

//销毁
void LTDesTroy(LTNode* phead)
{
	//哨兵位不能为空
	assert(phead);

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

***********************************************************分割线*****************************************************************************
完结！！！
感谢浏览和阅读。
等等等等一下，分享最近喜欢的一句话:

“成为正确答案的第一步，相信自己会是正确答案”。

我是白子寰，如果你喜欢我的作品，不妨你留个点赞+关注让我知道你曾来过。
你的点赞和关注是我持续写作的动力！！！ 
好了划走吧。

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

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

相关文章

基于SSM+Jsp+Mysql的二手车交易网站

基于SSM+Jsp+Mysql的二手车交易网站

开发语言：Java框架：ssm技术：JSPJDK版本：JDK1.8服务器：tomcat7数据库：mysql 5.7（一定要5.7版本）数据库工具：Navicat11开发软件：eclipse/myeclipse/ideaMaven包…
阅读更多...
浏览器工作原理与实践--虚拟DOM：虚拟DOM和实际的DOM有何不同

浏览器工作原理与实践--虚拟DOM：虚拟DOM和实际的DOM有何不同

虚拟DOM是最近非常火的技术，两大著名前端框架React和Vue都使用了虚拟DOM，所以我觉得非常有必要结合浏览器的工作机制对虚拟DOM进行一次分析。当然了，React和Vue框架本身所蕴含的知识点非常多，而且也不是我们专栏的重点&#xff0c…
阅读更多...
WPS 365开启企业一站式AI办公；联发科推出生成式AI服务平台；马斯克：AI 明年或超越人类智力

WPS 365开启企业一站式AI办公；联发科推出生成式AI服务平台；马斯克：AI 明年或超越人类智力

WPS 365 升级一站式 AI 办公 昨日，金山办公生产力大会举行，现场发布了面向组织和企业的办公新质生产力平台 WPS 365，其包含升级的 WPS Office、最新发布的 WPS AI 企业版和 WPS 协作。 WPS 365 将能覆盖一个组织日常办公基本需求&#xff0c…
阅读更多...
加密软件如何给文件加密

加密软件如何给文件加密

加密软件如何给文件加密 市面上有很多给文件加密的软件，它是如何给文件加密的呢？加密过程是否安全，效果是否理想呢？下面以安企神软件为例给大家介绍 给文件加密的关键步骤和技术。 1、选择加密算法 安企神软件可能会采用国际公…
阅读更多...
设计模式之迭代器模式（上）

设计模式之迭代器模式（上）

迭代器模式 1）概述 1.概念 存储多个成员对象（元素）的类叫聚合类(Aggregate Classes)，对应的对象称为聚合对象。 聚合对象有两个职责，一是存储数据，二是遍历数据。 2.概述 迭代器模式(Iterator Patter…
阅读更多...
Linux系统之——Elasticsearch企业级日志分析系统

Linux系统之——Elasticsearch企业级日志分析系统

目录 前言 一、ELK概述 1.ELK简介 2.ELK特点 3.为什么要使用ELK 4.完整日志系统基本特征 5.ELK工作原理 6.Elasticsearch介绍 6.1Elasticsearch概述 6.2Elasticsearch核心概念 7.Logstash介绍 7.1Logstash简介 7.2Logstash主要组件 8.Kibana介绍 8.1Kibana简介 …
阅读更多...
生成随机图片验证码

生成随机图片验证码

随着互联网的不断发展，安全性问题日益突出。为了保障用户账号的安全性，很多网站都引入了验证码机制。验证码是一种区分用户是计算机还是人的公共全自动程序，可以有效防止恶意攻击和自动化脚本的滥用。本文将介绍如何使用Python生成随机图片验…
阅读更多...
技术小课堂：100％CC防护是怎么实现的？

技术小课堂：100％CC防护是怎么实现的？

大家好，今天我们深入探讨的是如何有效地实现CC攻击的100%防护，以及传统防护手段存在的局限性和我们的定制化解决方案的优势。 传统的CC防护措施通常依赖于全局性的访问频率控制或在防火墙级别设置固定的访问次数限制。这种方式看似简单直接，…
阅读更多...
数据挖掘实战-基于机器学习的垃圾邮件检测模型（文末送书）

数据挖掘实战-基于机器学习的垃圾邮件检测模型（文末送书）

🤵‍♂️ 个人主页：艾派森的个人主页 ✍🏻作者简介：Python学习者 🐋 希望大家多多支持，我们一起进步！😄 如果文章对你有帮助的话， 欢迎评论 💬点赞&#x1f4…
阅读更多...
day13-实战：商城首页（上）

day13-实战：商城首页（上）

个人主页：学习前端的小z 个人专栏：HTML5和CSS3悦读 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结，欢迎大家在评论区交流讨论！ 文章目录 作业 作业 .bg-backward {width: 60px; height: 60px;background: url(../ima…
阅读更多...
超越常规：用PHP抓取招聘信息

超越常规：用PHP抓取招聘信息

在人力资源管理方面，有效的数据采集可以为公司提供宝贵的人才洞察。通过分析招聘网站上的职位信息，人力资源专员可以了解市场上的人才供给情况，以及不同行业和职位的竞争状况。这样的数据分析有助于企业制定更加精准的招聘策略，从…
阅读更多...
springboot+jsp幼儿园综合管理系统1m341

springboot+jsp幼儿园综合管理系统1m341

jdk版本：1.8 及以上 ide工具：IDEA 或者eclipse 数据库: mysql 编程语言: java 框架：SSM/springboot都有 maven: 3.6.1 前端：layuibootstrapjsp 详细技术：HTMLCSSJSjspspringmvcmybatisMYSQLMAVENtomcat贝儿米幼儿教育…
阅读更多...
vue2实现wangEditor富文本便捷器的封装使用--真实项目

vue2实现wangEditor富文本便捷器的封装使用--真实项目

基于wangEditor 5实现一个简单的富文本编辑器组件，实现自定义上传图片。 官网地址：https://www.wangeditor.com/v5/for-frame.html#%E9%85%8D%E7%BD%AE 1. 安装依赖包： npm i wangeditor/editor --save npm i wangeditor/editor-for-vue --…
阅读更多...
windows组播发不出去解决办法

windows组播发不出去解决办法

由于开启了虚拟网卡，安装VMWare虚拟化软件，可能会通过虚拟网卡发送组播，需要禁用虚拟化网卡。
阅读更多...
c++作业day4

c++作业day4

头文件&#xff1a; #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QTimer> #include <QTime> #include <QTextToSpeech> #include <QMessageBox> QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass…
阅读更多...
通过Telnet访问网络设备

通过Telnet访问网络设备

要通过 Telnet 访问网络设备&#xff0c;需要通过Console端口对网络设备进行基本配置&#xff0c;例如&#xff0c;IP地址、子网掩码、用户名和登录密码等。本实验以路由器为例&#xff0c;交换机远程管理只是接口名字不同而已&#xff0c;路由器用物理接口&#xff0c;交换机用…
阅读更多...
自己写的组件中使用v-model双向绑定

自己写的组件中使用v-model双向绑定

这里的时间选择表单是我写的一个组件&#xff0c;我想用v-model获取到实时的ref值。 代码&#xff1a; //父组件<TimePickerModal v-model:value"time" label-text"计划客面时间" /> const time ref(2024-04-09 15:20:00);//子组件<template>…
阅读更多...
虚拟化性能计数器需要至少一个可正常使用的计数器

虚拟化性能计数器需要至少一个可正常使用的计数器

VMware 虚拟机报错&#xff1a;虚拟化性能计数器需要至少一个可正常使用的计数器。 截图如下&#xff1a; 解决方式参考下图操作即可
阅读更多...
飞桨Ai（一）基于训练后的模型进行信息提取

飞桨Ai（一）基于训练后的模型进行信息提取

基准 本博客基于如下视频&#xff1a; 发票抬头信息抽取之环境搭建 - 基于飞浆开源项目发票抬头信息抽取之数据标准模型训练 - 基于飞浆开源项目 步骤 1、准备工作 下载python&#xff1a;【Python】Windows&#xff1a;Python 3.9.2 下载和安装&#xff08;建议3.9&#…
阅读更多...
蓝桥杯真题 字串简写 前缀和

蓝桥杯真题 字串简写 前缀和

&#x1f468;‍&#x1f3eb; Acwing 字串简写 输入 4 abababdb a b输出 6&#x1f496; 前缀和 import java.util.Scanner;public class Main {static int N (int) 5e5 10;static int[] l new int[N];// l[i] 表示 i 以及 i 左边包含多少个字符 apublic static void …
阅读更多...
最新文章

Copyright @ 2022~2023