单链表和双向链表

目录

目录

目录

一、链表种类

二、单链表概念

三、单链表实现

3.1 单链表创建结点

3.2 单链表销毁

3.3 单链表尾插

3.4 单链表尾删

3.5 单链表头插

3.6 单链表头删

3.7 单链表寻找值

3.8 单链表任意插（之前、之后）

3.9 单链表任意删（当前、后面）

四、双向链表概念

五、双向链表实现

4.1 双向链表创建结点

4.2 双向链表销毁

4.3 双向链表尾插

4.4 双向链表尾删

4.5 双向链表头插

4.6 双向链表头删

4.7 双向链表寻找值

4.8 双向链表任意插（之前、之后）

4.9 双向链表任意删

六、总结与反思（单双链表优缺点）

一、链表种类

        链表分为带头（不带头）、单向（双向）和循环（不循环）这几个分类。

二、单链表概念

        单链表是⼀种物理存储结构（不一定连续）上非连续、非顺序的存储结构，数据元素的逻辑顺序（连续）是通过链表中的指针链接次序实现的。他是不带头单向不循环链表，底层是结构体。

三、单链表实现

3.1 单链表创建结点

        创建结点时先写出单链表的结构体,如下：

//结构体
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;

创建结点

//创造节点
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;
}

3.2 单链表销毁

//销毁
void SListDestroy(SLTNode** pphead)//这里用二级指针是通过修改*phead这个指针地址来修改内部值（不带头）
{assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

3.3 单链表尾插

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* ptail = *pphead;//创建节点SLTNode* newnode = SLTbuyNode(x);//考虑没节点if (ptail == NULL){*pphead = newnode;}//找尾节点else{while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}}

3.4 单链表尾删

//尾删
void SLTPopBack(SLTNode** pphead)
{assert(*pphead);SLTNode* pcur = *pphead;SLTNode* prev = NULL;SLTNode* ptail = pcur;//考虑只有一个尾项删除if (ptail->next == NULL){free(*pphead);*pphead = NULL;}else {while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}}

3.5 单链表头插

//头插
void SLTPushFront(SLTNode** pphead,SLTDataType x)
{assert(pphead);//创造节点SLTNode* newnode = SLTbuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

3.6 单链表头删

//头删
void SLTPopFront(SLTNode** pphead)
{assert(*pphead);SLTNode* pcur = *pphead;SLTNode* next = (*pphead)->next;free(pcur);pcur = NULL;*pphead = next;
}

3.7 单链表寻找值

//查询
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

3.8 单链表任意插（之前、之后）

//任意位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(*pphead);SLTNode* pcur = *pphead;SLTNode* newnode = SLTbuyNode(x);//考虑重回时pcur和posif (pcur == pos){SLTPushFront(pphead, x);}//不重合时else{while (pcur->next != pos){pcur = pcur->next;}newnode->next = pcur->next;pcur->next = newnode;}
}//任意位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTbuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

3.9 单链表任意删（当前、后面）

//任意删
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(*pphead);SLTNode* pcur = *pphead;SLTNode* next = pos->next;//头删if (pcur == pos){*pphead = pcur->next;}else{while (pcur->next != pos){pcur = pcur->next;}pcur->next = next;free(pos);pos = NULL;}
}//任意删pos后面
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{assert(*pphead && pos->next != NULL);SLTNode* pcur = *pphead;SLTNode* next = pos->next;while (pcur != pos){pcur = pcur->next;}pcur->next = next->next;free(next);next = NULL;
}

四、双向链表概念

        双向链表是一种数据结构，每个节点包含三个部分：数据、指向前一个节点的指针（prev）和指向下一个节点的指针（next）。双向链表是带头的双向循环链表，底层是结构体。

五、双向链表实现

4.1 双向链表创建结点

        定义双向链表 

//双向链表结构定义
typedef int LTDataType;
typedef struct ListNode
{LTDataType Data;//数据struct ListNode* prev;struct ListNode* next;
}ListNode;

         创建头结点

//创建头结点
ListNode* ListCreate()
{ListNode* pHead = (ListNode*)malloc(sizeof(ListNode));if (pHead == NULL){perror("malloc1");exit(1);}pHead->Data = -1;pHead->next = pHead->prev = pHead;return pHead;
}

        创建结点

//创造新节点
ListNode* ListbuyNode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc2");exit(1);}newnode->Data = x;newnode->prev = newnode->next = newnode;return newnode;}

4.2 双向链表销毁

//销毁
void ListDestory(ListNode* pHead)//这里不用二级指针是由于不需要改变pHead这个头结点，只要通过pHead这个指针去访问并可修改下个指针即可
{ListNode* del = pHead->next;while (del != pHead){ListNode* next = del->next;free(del);del = next;}pHead = NULL;
}

4.3 双向链表尾插

//尾插
void ListPushBack(ListNode* pHead,LTDataType x)
{assert(pHead);ListNode* newnode = ListbuyNode(x);//newnodenewnode->next = pHead;newnode->prev = pHead->prev;//pHead pHead->prevpHead->prev->next = newnode;pHead->prev = newnode;
}

4.4 双向链表尾删

//尾删
void ListPopBack(ListNode* pHead)
{assert(!LTEmpty(pHead));ListNode* del = pHead->prev;//pHead del->prev deldel->prev->next = pHead;pHead->prev = del->prev;//释放free(del);del = NULL;
}

4.5 双向链表头插

//头插
void ListPushFront(ListNode* pHead,LTDataType x)
{ListNode* newnode = ListbuyNode(x);//newnodenewnode->next = pHead->next;newnode->prev = pHead;//pHead newnode pHead->nextpHead->next->prev = newnode;pHead->next = newnode;
}

4.6 双向链表头删

//头删
void ListPopFront(ListNode* pHead)
{assert(!LTEmpty(pHead));ListNode* del = pHead->next;//pHead->delpHead->next = del->next;//del-pHeaddel->prev = pHead;free(del);del = NULL;
}

4.7 双向链表寻找值

//查询
ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* pcur = pHead->next;while (pcur != pHead){if (pcur->Data == x){return pcur;}pcur = pcur->next;}return NULL;
}

4.8 双向链表任意插（之前、之后）

//任意之前插
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* mid = ListbuyNode(x);//midmid->prev = pos->prev;mid->next = pos;//pos->prev mid pospos->next->prev = mid;pos->prev->next = mid;
}//任意之后插
void ListAfter(ListNode* pos, LTDataType x)
{assert(pos);ListNode* mid = ListbuyNode(x);//midmid->prev = pos;mid->next = pos->next;//pos mid pos->nextpos->next->prev = mid;pos->next = mid;
}

4.9 双向链表任意删

//任意删
void ListErase(ListNode* pos)
{assert(!LTEmpty(pos));ListNode* del = pos;//del->prev --- del->nextdel->prev->next = del->next;//del->next->prev --- del->prevdel->next->prev = del->prev;free(pos);pos = NULL;
}

六、总结与反思（单双链表优缺点）

对于单链表的优缺点

对于双向链表优缺点 

双向链表优点缺点
查询比单链表效率高，虽然都是o（N），但是可以利用双向特性，进行左右开始查询（类似二分法）内存占用大（两个指针和一个数据，3个元素）
双向遍历代码实现向较为单链表复杂
插入删除方便

总结：对于双向链表和单链表，当需要频繁存入大量数据并查询时，可以首先考虑单链表（内存和代码实现）。当需要频繁插入和删除并频繁遍历时，可以考虑双向链表（时间效率高）。

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

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

相关文章

A模块 系统与网络安全 第三门课 网络通信原理-3

A模块 系统与网络安全 第三门课 网络通信原理-3

今日目标 IP数据包格式IP地址解析网络层常见协议路由原理和配置路由器转发数据分析配置默认路由 1 IP数据包格式 1.1 网络层概述 位于OSI模型第三层作用 √定义网络设备的逻辑地址，俗称网络层地址（如P地址） √在不同的网段之间选择最佳数据…
阅读更多...
笔记/计算机网络

笔记/计算机网络

Content 计算机网络部分核心概念十大网络协议一览 计算机网络部分核心概念 1. 什么是计算机网络？它最基本的功能是什么？ 计算机网络是指通过某种传输介质将多台独立的计算机或设备连接起来，实现数据交换和资源共享的系统。其最基本的功能是数…
阅读更多...
反射，枚举和lambda表达式

反射，枚举和lambda表达式

1. 反射 1. Java 的反射机制 Java 的反射机制是在运行状态，对于任意一个类，都能够直到它所有的属性和方法； 对于任意一个对象，都能调用它的方法和属性； 这种动态获取信息及调用对象方法的功能，称为Java…
阅读更多...
关于 java：8. Java 内存模型与 JVM 基础

关于 java：8. Java 内存模型与 JVM 基础

一、堆 Java 堆是 JVM 中所有线程共享的运行时内存区域，用于存放所有对象实例、数组以及类的实例字段值。 在 Java 中： String str new String("abc");new String("abc") 创建的对象就分配在堆中。 1.1 堆的特点 特性说明共享…
阅读更多...
大语言模型 API 进阶指南：DeepSeek 与 Qwen 的深度应用与封装实践

大语言模型 API 进阶指南：DeepSeek 与 Qwen 的深度应用与封装实践

在昨天小宁已经教大家怎么去获取各个平台的API-kEY,然后也带大家了解了最简单的大模型的调用，那么今天就带大家进阶了解一些更加详细的功能。 在大语言模型的实际应用中，除了基础的问答功能，深度思考能力、推理过程的获取以及灵活的对话模式…
阅读更多...
算法与数据结构：解决问题的黄金搭档

算法与数据结构：解决问题的黄金搭档

1. 算法的定义 算法（Algorithm） 是解决特定问题的精确步骤序列，本质是“解决问题的方法论”。 核心特征： 输入：接受数据（如零个、多个参数）。输出：必须产生明确结果（如…
阅读更多...
【MySQL】JDBC编程

【MySQL】JDBC编程

MySQL(七)JDBC编程 一、驱动包 1.性质 1.1底层差异性 1.2JDBC接口统一性 2.导入 2.1复制导包 2.2标记作库 二、JDBC编程 1.寻找资源 1.1URL 1.1.1网址作用 1.1.2主机IP 1.1.3端口号 1.1.4数据库名 1.1.5访问资源参数 2.访问认证 2.1身份 2.2密码 3.连接通道…
阅读更多...
RAG 架构地基工程-Retrieval 模块的系统设计分享

RAG 架构地基工程-Retrieval 模块的系统设计分享

目录 一、知识注入的关键前奏——RAG 系统中的检索综述 （一）模块定位：连接语言模型与知识世界的桥梁 （二）核心任务：四大关键问题的协调解法 （三）系统特征：性能、精度…
阅读更多...
浅谈AI大模型-MCP

浅谈AI大模型-MCP

MCP简介 MCP（Model Context Protocol，模型上下文协议 ），24年11月初的时候Anthropic发了一篇技术博客，推出了他们的模型上下文协议MCP，介绍了一种规范：应用如何为LLM提供上下文。官网称MCP为AI应…
阅读更多...
ROS常用的路径规划算法介绍

ROS常用的路径规划算法介绍

在ROS中，常用的路径规划算法主要有以下几种： 全局路径规划算法 A*算法：在Dijkstra算法基础上加入启发式函数，如曼哈顿距离或欧氏距离，优先探索靠近目标的节点，效率更高。需使用可容许的启发式函数以保证最…
阅读更多...
基于springboot+vue的数字科技风险报告管理系统

基于springboot+vue的数字科技风险报告管理系统

开发语言：Java框架：springbootJDK版本：JDK1.8服务器：tomcat7数据库：mysql 5.7数据库工具：Navicat12开发软件：eclipse/myeclipse/ideaMaven包：Maven3.3.9 系统展示 管理员登录 管理…
阅读更多...
docker compose基本使用以及示例

docker compose基本使用以及示例

一、docker-compose模板文件 字段含义build指定Dockerfile所在的文件夹路径image指定为镜像名称或镜像IDcontainer_name指定容器模式depends_on指定多个服务之间的依赖关系ports端口映射command覆盖容器启动后默认执行的命令entrypoint覆盖容器中默认的入口命令env_file从文件…
阅读更多...
最新文章

Copyright @ 2022~2023