双向链表专题

文章目录

  • 目录
    • 1. 双向链表的结构
    • 2. 双向链表的实现
    • 3. 顺序表和双向链表的优缺点分析

目录

  • 双向链表的结构
  • 双向链表的实现
  • 顺序表和双向链表的优缺点分析

1. 双向链表的结构

带头双向循环链表
注意：

这⾥的“带头”跟前面我们说的“头节点”是两个概念，带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的”。

“哨兵位”存在的意义：遍历循环链表避免死循环。

2. 双向链表的实现

  1. 定义双向链表中节点的结构
//定义双向链表中节点的结构
typedef int LTDataType;

typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;
  1. 初始化

注意，双向链表是带有哨兵位的，插入数据之前链表中必须要先初始化一个哨兵位

void LTInit(LTNode** pphead)
{
	*pphead = (LTNode*)malloc(sizeof(LTNode));

	if (NULL == *pphead)
	{
		perror("malloc fail!");
		exit(1);
	}

	(*pphead)->data = -1;
	(*pphead)->next = (*pphead)->prev = *pphead;
}

也可以这样写：

LTNode* LTInit()
{
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));

	if (NULL == phead)
	{
		perror("malloc fail!");
		exit(1);
	}

	phead->data = -1;
	phead->next = phead->prev = phead;

	return phead;
}
  1. 尾插

概念： 当链表中只有哨兵位节点的时候，我们称该链表为空链表；即哨兵位是不能删除的。

不需要改变哨兵位，则不需要传二级指针；如果需要修改哨兵位的话，则传二级指针。

尾插

LTNode* LTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));

	if (NULL == newnode)
	{
		perror("malloc fail!");
		exit(1);
	}

	newnode->data = x;
	newnode->next = newnode->prev = newnode;

	return newnode;
}

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* newnode = LTBuyNode(x);
	//phead phead->prev(ptail) newnode
	newnode->next = phead;
	newnode->prev = phead->prev;
	phead->prev->next = newnode;
	phead->prev = newnode;
}

因为写了申请新节点的函数，所以上面的初始化代码可以优化：

LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);

	return phead;
}
  1. 打印
void LTPrint(LTNode* phead)
{
	//phead不能为空
	assert(phead);

	LTNode* pcur = phead->next;

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

	printf("\n");
}
  1. 头插

头插

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

	LTNode* newnode = LTBuyNode(x);
	//phead newnode phead->next
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}
  1. 尾删

尾删

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	//链表为空：只有一个哨兵位节点
	assert(phead->next != phead);//若哨兵位节点的next指针或者prev指针指向的是自己，说明当前链表为空

	LTNode* del = phead->prev;
	LTNode* prev = del->prev;

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

	free(del);
	del = NULL;
}
  1. 头删

头删

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

	LTNode* del = phead->next;
	LTNode* next = del->next;

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

	free(del);
	del = NULL;
}
  1. 查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* pcur = phead->next;

	while (pcur != phead)
	{
		if (x == pcur->data)
		{
			return pcur;
		}

		pcur = pcur->next;
	}

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

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

	pos->next->prev = newnode;
	pos->next = newnode;
}
  1. 删除pos位置的数据

删除pos位置的数据

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

	//pos->prev pos pos->next
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;

	free(pos);
	pos = NULL;
}
  1. 销毁
void LTDesTroy(LTNode** pphead)
{
	assert(pphead);
	//哨兵位不能为空
	assert(*pphead);

	LTNode* pcur = (*pphead)->next;

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

	//链表中只有一个哨兵位
	free(*pphead);
	*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;
}

但是要注意：这样写要在调用完函数后再写一句 plist = NULL;

这两种写法我们更推荐第二种：推荐传一级指针**（保持接口一致性）**

完整代码：

//List.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//定义双向链表中节点的结构
typedef int LTDataType;

typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

//注意，双向链表是带有哨兵位的，插入数据之前链表中必须要先初始化一个哨兵位
//void LTInit(LTNode** pphead);
LTNode* LTInit();
//void LTDesTroy(LTNode** pphead);
void LTDesTroy(LTNode* phead);//推荐传一级指针（保持接口一致性）

void LTPrint(LTNode* phead);

//概念：当链表中只有哨兵位节点的时候，我们称该链表为空链表；即哨兵位是不能删除的
//不需要改变哨兵位，则不需要传二级指针
//如果需要修改哨兵位的话，则传二级指针
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);

//头删、尾删
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);

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

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置的数据
void LTErase(LTNode* pos);

//List.c

#include "List.h"

//void LTInit(LTNode** pphead)
//{
//	*pphead = (LTNode*)malloc(sizeof(LTNode));
//
//	if (NULL == *pphead)
//	{
//		perror("malloc fail!");
//		exit(1);
//	}
//
//	(*pphead)->data = -1;
//	(*pphead)->next = (*pphead)->prev = *pphead;
//}

LTNode* LTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));

	if (NULL == newnode)
	{
		perror("malloc fail!");
		exit(1);
	}

	newnode->data = x;
	newnode->next = newnode->prev = newnode;

	return newnode;
}

//LTNode* LTInit()
//{
//	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
//
//	if (NULL == phead)
//	{
//		perror("malloc fail!");
//		exit(1);
//	}
//
//	phead->data = -1;
//	phead->next = phead->prev = phead;
//
//	return phead;
//}

LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);

	return phead;
}

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* newnode = LTBuyNode(x);
	//phead phead->prev(ptail) newnode
	newnode->next = phead;
	newnode->prev = phead->prev;
	phead->prev->next = newnode;
	phead->prev = newnode;
}

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

	LTNode* newnode = LTBuyNode(x);
	//phead newnode phead->next
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}

void LTPrint(LTNode* phead)
{
	//phead不能为空
	assert(phead);

	LTNode* pcur = phead->next;

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

	printf("\n");
}

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	//链表为空：只有一个哨兵位节点
	assert(phead->next != phead);//若哨兵位节点的next指针或者prev指针指向的是自己，说明当前链表为空

	LTNode* del = phead->prev;
	LTNode* prev = del->prev;

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

	free(del);
	del = NULL;
}

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

	LTNode* del = phead->next;
	LTNode* next = del->next;

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

	free(del);
	del = NULL;
}

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

	LTNode* pcur = phead->next;

	while (pcur != phead)
	{
		if (x == pcur->data)
		{
			return pcur;
		}

		pcur = pcur->next;
	}

	return NULL;
}

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

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

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

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

	//pos->prev pos pos->next
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;

	free(pos);
	pos = NULL;
}

//void LTDesTroy(LTNode** pphead)
//{
//	assert(pphead);
//	//哨兵位不能为空
//	assert(*pphead);
//
//	LTNode* pcur = (*pphead)->next;
//
//	while (pcur != *pphead)
//	{
//		LTNode* next = pcur->next;
//		free(pcur);
//		pcur = next;
//	}
//
//	//链表中只有一个哨兵位
//	free(*pphead);
//	*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;
}

//Test.c

#include "List.h"

void ListTest01()
{
	//LTNode* plist = NULL;
	//LTInit(&plist);

	LTNode* plist = LTInit();
	//尾插
	//LTPushBack(plist, 1);
	//LTPushBack(plist, 2);
	//LTPushBack(plist, 3);
	//LTPushBack(plist, 4);
	//LTPrint(plist);

	//头插
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPrint(plist);

	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);

	//头删
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);

	LTNode* findRet = LTFind(plist, 3);

	//if (NULL == findRet)
	//{
	//	printf("未找到！\n");
	//}
	//else
	//{
	//	printf("找到了！\n");
	//}

	//在指定位置之后插入数据
	//LTInsert(findRet, 66);
	//LTPrint(plist);

	//删除pos位置的节点
	LTErase(findRet);
	LTPrint(plist);

	//LTDesTroy(&plist);
	LTDesTroy(plist);
	plist = NULL;
}

int main()
{
	ListTest01();

	return 0;
}

3. 顺序表和双向链表的优缺点分析

顺序表和双向链表的优缺点分析

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

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

相关文章

Redis 实战1

Redis 实战1

SDS Redis 只会使用 C 字符串作为字面量&#xff0c; 在大多数情况下&#xff0c; Redis 使用 SDS &#xff08;Simple Dynamic String&#xff0c;简单动态字符串&#xff09;作为字符串表示。 比起 C 字符串&#xff0c; SDS 具有以下优点&#xff1a; 常数复杂度获取字符串…
阅读更多...
JavaEE ＞＞ Spring MVC(2)

JavaEE ＞＞ Spring MVC(2)

接上文 本文介绍如何使用 Spring Boot/MVC 项目将程序执行业务逻辑之后的结果返回给用户&#xff0c;以及一些相关内容进行分析解释。 返回静态页面 要返回一个静态页面&#xff0c;首先需要在 resource 中的 static 目录下面创建一个静态页面&#xff0c;下面将创建一个静态…
阅读更多...
[嵌入式系统-53]：嵌入式系统集成开发环境大全 ( IAR Embedded Workbench（通用）、MDK（ARM）比较 )

[嵌入式系统-53]：嵌入式系统集成开发环境大全 ( IAR Embedded Workbench（通用）、MDK（ARM）比较 )

目录 一、嵌入式系统集成开发环境分类 二、由MCU芯片厂家提供的集成开发工具 三、由嵌入式操作提供的集成开发工具 四、由第三方工具厂家提供的集成开发工具 五、开发工具的整合 5.1 Keil MDK for ARM 5.2 IAR Embedded Workbench&#xff08;通用&#xff09;、MDK&…
阅读更多...
01.本地工作目录、暂存区、本地仓库三者的工作关系

01.本地工作目录、暂存区、本地仓库三者的工作关系

1.持续集成 1.持续集成CI 让产品可以快速迭代&#xff0c;同时还能保持高质量。 简化工作 2.持续交付 交付 3.持续部署 部署 4.持续集成实现的思路 gitjenkins 5.版本控制系统 1.版本控制系统概述2.Git基本概述3.Git基本命令 2.本地工作目录、暂存区、本地仓库三者的工作关系…
阅读更多...
抖音评论区精准获客自动化获客释放双手

抖音评论区精准获客自动化获客释放双手

挺好用的&#xff0c;评论区自动化快速获客&#xff0c;如果手动点引流涨&#xff0c;那就很耗费时间了&#xff0c;不是吗&#xff1f; 网盘自动获取 链接&#xff1a;https://pan.baidu.com/s/1lpzKPim76qettahxvxtjaQ?pwd0b8x 提取码&#xff1a;0b8x
阅读更多...
leetcode84柱状图中最大的矩形

leetcode84柱状图中最大的矩形

题解&#xff1a; - 力扣&#xff08;LeetCode&#xff09; class Solution {public int largestRectangleArea(int[] heights) {Stack<Integer> stack new Stack<>();int maxArea Integer.MIN_VALUE;for(int i 0;i < heights.length;i){int curHeight hei…
阅读更多...
YOLOV8添加SKATTENTION

YOLOV8添加SKATTENTION

修改ultralytics.nn.modules._init_.py https://zhuanlan.zhihu.com/p/474599120?utm_sourcezhihu&utm id0 https://blog.csdn.net/weixin 42878111/article/details/136060087 https://blog.csdn.net/gg 51511878/aricle/details/138002223 . 最后输出层不一样。
阅读更多...
JAVA面试之MQ

JAVA面试之MQ

如何保证消息的可靠传输&#xff1f;如果消息丢了怎么办 数据的丢失问题&#xff0c;可能出现在生产者、MQ、消费者中。 &#xff08;1&#xff09;生产者发送消息时丢失&#xff1a; ①生产者发送消息时连接MQ失败 ②生产者发送消息到达MQ后未找到Exchange(交换机) ③生产者发…
阅读更多...
一对一WebRTC视频通话系列（一）—— 创建页面并显示摄像头画面

一对一WebRTC视频通话系列（一）—— 创建页面并显示摄像头画面

本系列博客主要记录WebRtc实现过程中的一些重点&#xff0c;代码全部进行了注释&#xff0c;便于理解WebRTC整体实现。 一、创建html页面 简单添加input、button、video控件的布局。 <html><head><title>WebRTC demo</title></head><h1>…
阅读更多...
单片机编程实例400例大全（100-200）

单片机编程实例400例大全（100-200）

今天继续分享单片机编程实例第100-200例。 今天的实例会比前面100复杂一些&#xff0c;我大概看了下&#xff0c;很多都具备实际产品的参考价值。 今天继续分享单片机编程实例第100-200例。 今天的实例会比前面100复杂一些&#xff0c;我大概看了下&#xff0c;很多都具备实际…
阅读更多...
计算机毕业设计hadoop+spark+hive知识图谱音乐推荐系统 音乐数据分析可视化大屏 音乐爬虫 LSTM情感分析 大数据毕设 深度学习 机器学习

计算机毕业设计hadoop+spark+hive知识图谱音乐推荐系统 音乐数据分析可视化大屏 音乐爬虫 LSTM情感分析 大数据毕设 深度学习 机器学习

黄河科技学院本科毕业设计 任务书 工 学部 大数据与计算机应用 科教中心 计算机科学与技术 专业 2018 级普本1/专升本1班 学号 学生 指导教师 毕业设计题目 基于实时音乐数据挖掘的个性化推荐系统设计与优化 毕业设计工作内容与基本…
阅读更多...
频分复用系统设计及其MATLAB实现

频分复用系统设计及其MATLAB实现

引言 随着通信技术的飞速发展&#xff0c;通信系统的容量需求不断增长。频分复用&#xff08;Frequency Division Multiplexing, FDM&#xff09;作为一种重要的多路复用技术&#xff0c;被广泛应用于现代通信系统中。本文将介绍频分复用系统的设计原理&#xff0c;并展示如何…
阅读更多...
【Docker学习】docker start深入研究

【Docker学习】docker start深入研究

docker start也是很简单的命令。但因为有了几个选项&#xff0c;又变得复杂&#xff0c;而且... 命令&#xff1a; docker container start 描述&#xff1a; 启动一个或多个已停止的容器。 用法&#xff1a; docker container start [OPTIONS] CONTAINER [CONTAINER...] 别名&…
阅读更多...
UE4_Niagara_两个模型之间的粒子幻化

UE4_Niagara_两个模型之间的粒子幻化

学习笔记&#xff0c;仅供参考&#xff01; 操作步骤&#xff1a; 1、新建niagara system&#xff0c;添加空的发射器&#xff0c;渲染改为网格体渲染器&#xff0c;网格体为1M_Cube. 2、创建粒子材质重载。 3、渲染网格体的材质设置&#xff1a; 4、在发射器属性面板&#x…
阅读更多...
数据分析：基于DESeq2的转录组功能富集分析

数据分析：基于DESeq2的转录组功能富集分析

介绍 DESeq2常用于识别差异基因&#xff0c;它主要使用了标准化因子标准化数据&#xff0c;再根据广义线性模型判别组间差异&#xff08;组间残差是否显著判断&#xff09;。在获取差异基因结果后&#xff0c;我们可以进行下一步的富集分析&#xff0c;常用方法有基于在线网站…
阅读更多...
【二等奖水平论文】2024五一数学建模C题22页保奖论文+22页matlab和13页python完整建模代码、可视图表+分解结果等（后续会更新）

【二等奖水平论文】2024五一数学建模C题22页保奖论文+22页matlab和13页python完整建模代码、可视图表+分解结果等（后续会更新）

一定要点击文末的卡片&#xff0c;那是资料获取的入口&#xff01; 点击链接加入群聊【2024五一数学建模】&#xff1a;http://qm.qq.com/cgi-bin/qm/qr?_wv1027&khoTDlhAS5N_Ffp-vucfG5WjeeJFxsWbz&authKey7oCSHS25VqSLauZ2PpiewRQ9D9PklaCxVS5X6i%2BAkDrey992f0t15…
阅读更多...
Spark RDD的分区与依赖关系

Spark RDD的分区与依赖关系

Spark RDD的分区与依赖关系 RDD分区 RDD&#xff0c;Resiliennt Distributed Datasets&#xff0c;弹性式分布式数据集&#xff0c;是由若干个分区构成的&#xff0c;那么这每一个分区中的数据又是如何产生的呢&#xff1f;这就是RDD分区策略所要解决的问题&#xff0c;下面我…
阅读更多...
音视频开发之旅——实现录音器、音频格式转换器和播放器（PCM文件转换为WAV文件、使用LAME编码MP3文件）（Android）

音视频开发之旅——实现录音器、音频格式转换器和播放器（PCM文件转换为WAV文件、使用LAME编码MP3文件）（Android）

本文主要讲解的是实现录音器、音频转换器和播放器&#xff0c;在实现过程中需要把PCM文件转换为WAV文件&#xff0c;同时需要使用上一篇文章交叉编译出来的LAME库编码MP3文件。本文基于Android平台&#xff0c;示例代码如下所示&#xff1a; AndroidAudioDemo Android系列&am…
阅读更多...
Golang | Leetcode Golang题解之第64题最小路径和

Golang | Leetcode Golang题解之第64题最小路径和

题目&#xff1a; 题解&#xff1a; func minPathSum(grid [][]int) int {if len(grid) 0 || len(grid[0]) 0 {return 0}rows, columns : len(grid), len(grid[0])dp : make([][]int, rows)for i : 0; i < len(dp); i {dp[i] make([]int, columns)}dp[0][0] grid[0][0]…
阅读更多...
服务器IP选择

服务器IP选择

可以去https://ip.ping0.cc/查看IP的具体情况 1.IP位置--如果是国内用&#xff0c;国外服务器的话建议选择日本&#xff0c;香港这些比较好&#xff0c;因为它们离这里近&#xff0c;一般延时低&#xff08;在没有绕一圈的情况下&#xff09;。 不过GPT的话屏蔽了香港IP 2. 企…
阅读更多...
最新文章

Copyright @ 2022~2023