数据结构——双向循环链表

目录

前言

一、链表的分类

二、双向循环链表

2.1 开辟新的节点

2.2 链表初始化

2.3 打印链表

2.4 链表的尾插

2.5 链表的头插

2.6 链表的尾删

2.7 链表的头删

2.8 查找链表

2.9 在pos位置之后插入数据

2.10 删除pos位置的数据

三、完整代码实现

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

总结

前言

我们之前讲了顺序表和单链表，它们但是线性表的一种，今天我们来讲链表中的双向循环链表。

一、链表的分类

链表的结构⾮常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构：
其中分为：

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

二、双向循环链表

我们之前讲了单链表，今天我们来实现双向带头循环链表。

接口实现：

//list.h

//链表初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit();

//打印链表
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);

//销毁链表 保持接口一致性
//void LTDesTroy(LTNode** pphead);

void LTDesTroy(LTNode* phead);

在实现代码前，我们要先用结构体来定义链表的类型。由于是循环链表，所以我们需要两个指针，分别指向节点的前驱节点和后继节点。

typedef int LTDataType;
//双向循环链表结构体类型
typedef struct ListNode {
	LTDataType data;
	struct ListNode* prev;//前驱节点
	struct ListNode* next;//后继节点
}LTNode;

2.1 开辟新的节点

在初始化之前，我们来实现开辟新的节点

//新的节点
LTNode* LTBuyNode(LTDataType x) {
	//为新的节点开辟空间
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
	if (newNode == NULL) {
		perror("malloc fail!");
		exit(1);
	}
	newNode->data = x;
	//让新节点头尾相连
	newNode->next = newNode->prev = newNode;
	return newNode;
}

2.2 链表初始化

链表的初始化我们可以有两种写法：

//写法一 传入头节点的地址
void LTInit(LTNode** pphead) {
	assert(pphead);
    //哨兵位
	*pphead = LTBuyNode(-1);
}
//写法二 返回哨兵位,不传入值
LTNode* LTInit() {
	LTNode* pphead = LTBuyNode(-1);
	return pphead;
}

我们给哨兵位的值赋为-1(任意都可以，哨兵位不作为有效数据)。

我们更推荐使用第二种方法，因为保持接口的一致性。

2.3 打印链表

如果我们往链表中插入数据，可以通过打印知道是否插入成功

void LTPrint(LTNode* phead) {
	assert(phead);
	//从哨兵位下一个节点开始打印
	LTNode* pcur = phead->next;
	while (pcur != phead) {
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

其中要注意的是循环开始是从哨兵位下一个节点开始的，结束条件是pcur走到哨兵位，即遍历了整个链表。

2.4 链表的尾插

void LTPushBack(LTNode* phead, LTDataType x) {
	assert(phead);
    //要插入的新的节点
	LTNode* newNode = LTBuyNode(x);
	
    //phead phead->prev newNode
	
	newNode->next = phead;
	newNode->prev = phead->prev;

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

尾插入一个节点，我们要改变的是哨兵位，哨兵位的前驱节点(即尾节点)，新节点三个节点的指向

2.5 链表的头插

void LTPushFront(LTNode* phead, LTDataType x) {
	assert(phead);
    //插入的新节点
	LTNode* newNode = LTBuyNode(x);

	//phead phead->next newNode

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

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

头插入一个节点，我们要改变的是哨兵位，哨兵位的后继节点(即第一个有效数据节点)，新节点三个节点的指向

2.6 链表的尾删

void LTPopBack(LTNode* phead) {
	assert(phead);
    //链表不为空
	assert(phead->next != phead);

	//phead phead->prev->prev(prev) phead->prev(del)
	LTNode* prev = phead->prev->prev;
	LTNode* del = phead->prev;

	phead->prev = prev;
	prev->next = phead;
	free(del);
	del = NULL;
}

尾部删除一个节点，我们要改变的是删除元素的前驱节点，哨兵位的指向，最后释放删除节点

2.7 链表的头删

void LTPopFront(LTNode* phead) {
	assert(phead);
    //链表不为空
	assert(phead->next != phead);

	//phead phead->next(del) phead->next->next(next)
	LTNode* del = phead->next;
	LTNode* next = phead->next->next;

	phead->next = next;
	next->prev = phead;
	free(del);
	del = NULL;
}

头部删除一个节点，我们要改变的是哨兵位，删除节点的后继节点，最后释放删除节点

2.8 查找链表

如果我们要指定位置插入或者删除，我们就要找到这个位置，我们进行链表的查找

LTNode* LTFind(LTNode* phead, LTDataType x) {
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead) {
		if (pcur->data == x) {
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

如果存在返回当前节点，不存在返回空。

2.9 在pos位置之后插入数据

void LTInsert(LTNode* pos, LTDataType x) {
	assert(pos);
	LTNode* newNode = LTBuyNode(x);

	//newNode pos pos->next

	newNode->next = pos->next;
	newNode->prev = pos;

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

我们要改变新节点，pos节点，pos节点的后继节点的指向。

注意：我们要先把pos的后继节点的前驱节点指向新节点，才能把pos的后继节点指向新节点，不然反过来会找不到pos节点后继节点的位置。

2.10 删除pos位置的数据

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

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

我们要改变新节点，pos节点的前驱，pos节点的后继节点的指向。

2.11 销毁链表

因为每个节点都是单独开辟的空间，所以我们要依次销毁。

//方法一
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;
}

与链表的初始化一样，我们有两种方法，但是我们一般选择第二种方法，为了保持接口的一致性，但是第二种方法我们要在函数外面手动给链表置为空。

三、完整代码实现

list.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#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 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);

//销毁链表 保持接口一致性
//void LTDesTroy(LTNode** pphead);

void LTDesTroy(LTNode* phead);

list.c

#include"list.h"

//新的节点
LTNode* LTBuyNode(LTDataType x) {
	//为新的节点开辟空间
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
	if (newNode == NULL) {
		perror("malloc fail!");
		exit(1);
	}
	newNode->data = x;
	//让新节点头尾相连
	newNode->next = newNode->prev = newNode;
	return newNode;
}

//链表初始化
//写法一 传入头节点的地址
//void LTInit(LTNode** pphead) {
//	assert(pphead);
//   哨兵位
//	*pphead = LTBuyNode(-1);
//}
//写法二 返回哨兵位,不传入值
LTNode* LTInit() {
	LTNode* pphead = LTBuyNode(-1);
	return pphead;
}

//打印链表
void LTPrint(LTNode* phead) {
	assert(phead);
	//从哨兵位下一个节点开始打印
	LTNode* pcur = phead->next;
	while (pcur != phead) {
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

//尾插	
void LTPushBack(LTNode* phead, LTDataType x) {
	assert(phead);
	LTNode* newNode = LTBuyNode(x);
	//phead phead->prev 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 phead->next newNode

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

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

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

	//phead phead->prev->prev(prev) phead->prev(del)
	LTNode* prev = phead->prev->prev;
	LTNode* del = phead->prev;

	phead->prev = prev;
	prev->next = phead;
	free(del);
	del = NULL;
}

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

	//phead phead->next(del) phead->next->next(next)
	LTNode* del = phead->next;
	LTNode* next = phead->next->next;

	phead->next = next;
	next->prev = phead;
	free(del);
	del = NULL;
}

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

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

	//newNode pos 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->next = pos->next;
	pos->next->prev = pos->prev;
	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;
}

listest.c

#include"list.h"

void Listest() {
	//LTNode* plist = NULL;
	//LTInit(&plist);
	LTNode* plist=LTInit();
	//尾插
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);//1 2 3 4;
	LTPrint(plist);

	//头插
	/*LTPushFront(plist, 8);
	LTPushFront(plist, 7);
	LTPushFront(plist, 6);
	LTPushFront(plist, 5);
	LTPrint(plist);*/

	//尾删
	/*	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	//删除失败，链表为空
	//LTPopBack(plist);*/

	//头删
	/*LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	//删除错误链表为空
	//LTPopFront(plist);*/

	//查找
	LTNode* retFInd = LTFind(plist,1);
	/*if (retFInd) {
		printf("找到了\n");
	}
	else {
		printf("没找到\n");
	}*/

	//在pos后面插入数据
	/*LTInsert(retFInd, 50);
	LTPrint(plist);*/

	//删除pos位置上的数据
	/*LTErase(retFInd);
	LTPrint(plist);*/

	//销毁链表
	//LTDesTroy(&plist);
	//保持接口一致性
	LTDesTroy(plist);
	plist = NULL;
}


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

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

不同点
顺序表
链表（单链表）
存储空间上
物理上⼀定连续
逻辑上连续，但物理上不⼀定连续
随机访问
⽀持O(1)
不⽀持：O(N)
任意位置插⼊或删除元素
可能需要搬移元素，效率低O(N)
只需修改指针指向
插⼊
动态顺序表，空间不够时需要扩
容
没有容量的概念
应⽤场景
元素⾼效存储+频繁访问
任意位置插⼊和删除频繁

总结

上述文章我们讲了链表的双向带头循环链表的实现，希望对你有所帮助

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

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

相关文章

获取CDS View名字的表：get CDS View name by SQL View Name

获取CDS View名字的表：get CDS View name by SQL View Name

table: DDLDEPENDENCY
阅读更多...
使用 R.swift(生成不了R.generated.swift）

使用 R.swift(生成不了R.generated.swift）

今天算是正儿八经创建第一个swift工程&#xff0c;照着视频引用R.swift pod R.swift 工程配置 "$PODS_ROOT/R.swift/rswift" generate "$SRCROOT/R.generated.swift" $TEMP_DIR/rswift-lastrun $SRCROOT/R.generated.swift * 注意 Run角本要放在 Che…
阅读更多...
半导体的主要四大应用

半导体的主要四大应用

半导体是现代信息社会的基石&#xff0c;是现代工业的“粮食”&#xff0c;是电子设备产品生产制造的核心&#xff0c;它与我们的生活紧密相关。涉及到方方面面&#xff0c;半导体芯片、智能汽车、智慧电网、5G通信、航空航天、国防军工、医疗卫生等等。半导体的主要应用都有哪…
阅读更多...
大型语言模型如何助力推荐系统：综述研究

大型语言模型如何助力推荐系统：综述研究

论文地址&#xff1a;https://arxiv.org/pdf/2306.05817.pdf 这篇论文主要探讨了推荐系统&#xff08;RS&#xff09;如何从大型语言模型&#xff08;LLM&#xff09;中获益。论文首先指出&#xff0c;随着在线服务和网络应用的快速发展&#xff0c;推荐系统已成为缓解信息过载…
阅读更多...
药店药品进销存管理系统软件可以对有效期管理查询以及对批号库存管理

药店药品进销存管理系统软件可以对有效期管理查询以及对批号库存管理

药店药品进销存管理系统软件可以对有效期管理查询以及对批号库存管理 一、前言 以下软件操作教程以&#xff0c;佳易王药店药品进销存管理软件为例说明 软件文件下载可以点击最下方官网卡片——软件下载——试用版软件下载 软件可以对药品有效期进行管理查询&#xff0c;可以…
阅读更多...
Python构建复杂数据管道库之luigi使用详解

Python构建复杂数据管道库之luigi使用详解

概要 在大数据时代，处理海量数据已经成为许多应用和业务的基本需求。为了有效地管理和处理这些数据，需要强大的工具来构建可靠的数据管道。Python Luigi 就是这样一种工具，它提供了一个简单而强大的框架，用于构建复杂的数据处理流程。本文将深入探讨 Python Luigi 的核心概…
阅读更多...
使用yolov8实现自动车牌识别（教程+代码）

使用yolov8实现自动车牌识别（教程+代码）

该项目利用了一个被标记为“YOLOv8”的目标检测模型&#xff0c;专门针对车牌识别任务进行训练和优化。整个系统通常分为以下几个核心步骤&#xff1a; 数据准备&#xff1a; 收集包含车牌的大量图片&#xff0c;并精确地标记车牌的位置和文本信息。数据集可能包含各种环境下的…
阅读更多...
基于java+springboot+vue实现的旅游管理系统（文末源码+Lw）23-234

基于java+springboot+vue实现的旅游管理系统（文末源码+Lw）23-234

摘 要 如今社会上各行各业&#xff0c;都喜欢用自己行业的专属软件工作&#xff0c;互联网发展到这个时候&#xff0c;人们已经发现离不开了互联网。新技术的产生&#xff0c;往往能解决一些老技术的弊端问题。因为传统旅游管理系统信息管理难度大&#xff0c;容错率低&#…
阅读更多...
设计模式之解释器模式（上）

设计模式之解释器模式（上）

解释器模式 1&#xff09;概述 1.定义 定义一个语言的文法&#xff0c;并且建立一个解释器来解释该语言中的句子&#xff0c;这里的“语言”是指使用规定格式和语法的代码。 2.结构图 3.角色 AbstractExpression&#xff08;抽象表达式&#xff09;&#xff1a;在抽象表达…
阅读更多...
PQMII-T20-C-A的控制功能

PQMII-T20-C-A的控制功能

PQMII-T20-C-A 是一款电力质量监测仪器&#xff0c;它能够提供三相系统的连续监控。 以下是关于PQMII-T20-C-A的一些详细信息&#xff1a; 多参数测量&#xff1a;该设备具备测量电流、电压、有功功率、无功功率、能源使用、电力成本、功率因数和频率等关键电力参数的能力。波…
阅读更多...
阿里云2024年优惠券获取方法及使用教程详解

阿里云2024年优惠券获取方法及使用教程详解

阿里云是阿里巴巴集团旗下的云计算服务提供商&#xff0c;是全球领先的云计算及人工智能科技公司之一。提供免费试用、云服务器、云数据库、云安全、云企业应用等云计算服务&#xff0c;以及大数据、人工智能服务、精准定制基于场景的行业解决方案。 阿里云2024年优惠券的获取方…
阅读更多...
jeecg-boot 3.6使用微服务启动详细配置

jeecg-boot 3.6使用微服务启动详细配置

1&#xff1a;运行sql文件 2&#xff1a;配置host 路径如下 127.0.0.1 jeecg-boot-redis 127.0.0.1 jeecg-boot-mysql 127.0.0.1 jeecg-boot-nacos 127.0.0.1 jeecg-boot-gateway 127.0.0.1 jeecg-boot-system 127.0.0.1 jeecg-boot-xxljob 127.0.0.1 jeecg-boot-rabbitmq 3…
阅读更多...
基于springboot现服装销售平台系统项目【项目源码+论文说明】

基于springboot现服装销售平台系统项目【项目源码+论文说明】

基于springboot实现服装销售平台系统演示 摘要 随着信息互联网购物的飞速发展&#xff0c;一般企业都去创建属于自己的电商平台以及购物管理系统。本文介绍了“衣依”服装销售平台的开发全过程。通过分析企业对于“衣依”服装销售平台的需求&#xff0c;创建了一个计算机管理“…
阅读更多...
系统架构评估_3.ATAM方法

系统架构评估_3.ATAM方法

架构权衡分析方法&#xff08;Architecture Tradeoff Analysis Method&#xff0c;ATAM&#xff09;是在SAAM的基础发展起来的&#xff0c;主要针对性能、实用性、安全性和可修改性&#xff0c;在系统开发之前&#xff0c;对这些质量属性进行评价和折中。 &#xff08;1&#x…
阅读更多...
uniapp请求后端接口

uniapp请求后端接口

新建文件夹utils const request (config) > {// 拼接完整的接口路径config.url http://mm.test.cn config.url;//这里拼接的是访问后端接口的地址&#xff0c;http://mm.test.cn/prod-api/testconsole.log(config.url)//判断是都携带参数if(!config.data){config.data …
阅读更多...
【御控物联】 JavaScript JSON结构转换（20）：数组To对象——转换映射方式

【御控物联】 JavaScript JSON结构转换（20）：数组To对象——转换映射方式

文章目录 一、JSON结构转换是什么&#xff1f;二、术语解释三、案例之《JSON数组 To JSON对象》四、代码实现五、在线转换工具六、技术资料 一、JSON结构转换是什么&#xff1f; JSON结构转换指的是将一个JSON对象或JSON数组按照一定规则进行重组、筛选、映射或转换&#xff0…
阅读更多...
AI识别技术详解 --在windows环境中部署基于YOLO v8模型的目标检测

AI识别技术详解 --在windows环境中部署基于YOLO v8模型的目标检测

首先 YOLO是一个端到端的目标检测算法&#xff0c;一次前向传播计算&#xff0c;实现图像的多目标检测任务&#xff0c;我么可以在ultralytics官网上查看YOLO的各个版本&#xff08;v1-v8&#xff09;以及源码 使用YOLO v8提供的python接口&#xff0c;训练一个佩戴安全帽的目标…
阅读更多...
简介：基于Web的产品3D

简介：基于Web的产品3D

基于 Web 的产品 3D 通过可视化界面获得各种选项来个性化他们的产品&#xff0c;例如颜色、材料、尺寸、文字、徽标、零件等。 在过去几年中&#xff0c;随着 3D 建模和渲染软件的出现&#xff0c;3D 渲染现在更常用于营销和促销目的。设计师、制造商和营销人员使用 3D 产品渲…
阅读更多...
Windows 11安装Radialix 3

Windows 11安装Radialix 3

Radialix 3软件可以实现软件汉化&#xff0c;能够制作汉化补丁和语言包文件。 接下来详细介绍安装过程&#xff0c;亲测有效。 一、下载安装包并本地解压 安装包资源和破解软件都上传到了文章顶部。 本地解压&#xff1a; 二、开始安装Radialix 双击Radialix_3.00.00.486.…
阅读更多...
RuleEngine规则引擎底层改造AviatorScript 之公式规则

RuleEngine规则引擎底层改造AviatorScript 之公式规则

前情提要&#xff0c;看上一个文章&#xff0c;具体要实现的效果就是 当然上来的问题就是前端的问题&#xff0c;这个框首先他们用的是富文本&#xff0c;富文本传到后台的结果是前端脚本&#xff0c;带着h5的标签&#xff0c;后面改成了这个&#xff0c;当时这个东西其实和后…
阅读更多...
最新文章

Copyright @ 2022~2023