数据结构：链表详解 (c++实现)

前言

对于数据结构的线性表，其元素在逻辑结构上都是序列关系，即数据元素之间有前驱和后继关系。
在这里插入图片描述

但在物理结构上有两种存储方式：

  • 顺序存储结构：

    • 使用此结构的线性表也叫 顺序表
    • 物理存储上是连续的，因此可以随机访问，时间复杂度为 O(1)
      在这里插入图片描述

  • 链式存储结构：

    • 使用此结构的线性表也叫 链表
    • 物理存储上不连续，因此不支持随机访问
      在这里插入图片描述

接下来要介绍的就是 链表。
链表分为 单向链表（单链表）与 双向链表（双链表），理解了单链表，双链表自然也明白了。

1. 什么是单链表

1.1 定义

链表由一系列的节点组成（链表中的每个元素都可称为节点），对于单链表而言，它的节点包含两部分：

  • 数据域：存储当前节点的数据
  • 指针域：存储当前节点的下一个节点（后继节点）的地址

在这里插入图片描述

那么现在定义单链表 SingleList 的节点 Node：

1.2 创建 Node

struct Node {int val;		// 数据域Node* next;		// 指针域：指向的是 Node，所以类型为 Node*
};

这么定义的 Node 类只能接收数据类型为 int 的数据，对于其他类型的数据当前的类不能处理，因此为了代码的通用性，将 Node 定义为模版类：

template <typename T>
struct Node
{T val;		// 数据域Node* next;		// 指针域Node(T v, Node* n = nullptr) :val{ v }, next{ n } { }
};

为了方便初始化，Node 还增加了构造函数：一个节点肯定必须有数据域，但指针域可以为空（表示没有后继节点了）

那么我们可以如下创建节点：

Node<int> node2(2);		// 数据域为：2 (int)，指针域为空
Node<int> node1(1, &node2);		// 数据域为：1，指针域为 node2 的地址

在这里插入图片描述

1.3 创建 SingleList

从单链表的定义可以看出，单链表都会有：

  • 头结点（head）：第一个节点
  • 尾结点（rear）：最后一个节点
    在这里插入图片描述

对于 SingleList 来说，我们显然需要能够访问链表中的所有节点。
对于一个节点来说，我们能得到两部分信息：

  • 当前节点自身的值（数据域）
  • 当前节点的下一个节点（指针域）

也就是说，我们只需要通过头结点，就可以访问该链表上的所有节点，并且不会越界。

当某一节点的后继节点为空时，说明当前节点是尾结点，不能在继续访问下一节点。

因此你可以在 SingleList 类中保存头结点，但是这会有一个问题：
如果当前单链表没有节点怎么办？

之前已经说明节点不能为空：一个节点肯定必须有数据域，但指针域可以为空。

显然保存头结点不是一个好的方法，那么我们可以保存 头指针。

头指针：指向头结点的指针

此时就可以

  • 通过 头指针 访问 头结点，进而访问所有节点。
  • 当 头指针 为 nullptr 时，说明当前单链表没有节点。
    在这里插入图片描述

由于 Node 为模版类，因此 SingleList 也为模板类：

template <typename T>
class SingleList {
public:SingleList() = default;	   // 默认构造空单链表private:Node<T>* head = nullptr;
};

下面来实现一些单链表经常会用到的操作：

2 SingleList 的操作

接下来的操作会涉及到指针的相关操作，使用不当很容易导致 bug

补充 SingleList 类：

template <typename T>
class SingleList {
public:SingleList() = default;// 成员变量为指针，析构时需要释放内存~SingleList();	  // 返回节点数int size() const;// 返回 i 位置的节点值int get(int i) const;// 头插法void push_front(T t);// 尾插法void push_back(T t);// 删除头结点void pop_front();// 删除尾结点void pop_back();// 在 i 位置插入void insert(int i, T t);// 删除 i 位置的节点void erase(int i);private:Node<T>* head = nullptr;
};

2.1 size()

作用：求链表的节点个数

在此之前先来看如何遍历链表：

head 为 类指针（'Node<...>*'），
可以通过 '->' 去访问类的成员
'head->next' <==> '(*head).next'

对于下面的链表有：
在这里插入图片描述
换言之可以通过 head 访问所有节点，那么用一个临时变量 node 来拷贝一份 head，用 node 来遍历链表：

auto node = head;
while (node != nullptr) {	// node == nullptr 说明 node 为尾结点的下一个节点（空）cout << node->val << endl;node = node->next;		// 将 node 后移一个节点
}

用上面的例子来分析此程序：

  • 首先拷贝 head

    auto node = head;

    在这里插入图片描述

  • 因为 node != nullptr，故进入 while 循环

  • 此时 node 指向第一个节点，node->val = 0，此时有
    在这里插入图片描述

  • node = node->next
    在这里插入图片描述

  • 由于 node != nullptr，进入下一次循环

  • 此时 node 指向第二个节点，node->val = 1，此时有
    在这里插入图片描述

  • 执行 node = node->next
    在这里插入图片描述

  • 此时 node == nullptr，退出循环

因此可以 size() 函数实现如下：

下面的所有成员函数都是在类内部实现的

int size() const 
{auto node = head;int res = 0;while (node != nullptr) {res++;node = node->next;}return res;
}

【注】为什么不直接用 head 进行遍历，而用一个临时指针？

如果用 head 进行遍历：

while (head != nullptr) {cout << node->val << endl;head = head->next;		
}

根据前面的分析，如果链表中有节点，采用此方法会造成最后 head 指向链表的尾结点的下一个节点（nullptr），那么之后 head 就无法用来遍历此链表了，即此链表 “丢失” 了。

在链表的插入与删除操作，需要特别注意先后顺序。

2.2 push_front(T t)

作用：头插法，在链表的头部插入一个节点

设待插入节点为 node
在这里插入图片描述

  • node->next = head
    在这里插入图片描述

  • head = node

    新加入的节点现在成为头结点了

    在这里插入图片描述

void push_front(T t)
{Node<T>* node = new Node<T>(t);   // 创建的是指针，需要 new 一块内存 node->next = head;head = node;
}

为了用户更易于理解此单链表，从用户视角来看：他关心的仅仅是数据域；指针域用户不需要关心，由类的设计者来管理。因此函数 push_front 的参数应该是节点的数据域（ push_front(T t) ），而不应该是节点 （ push_front(Node n) ），后面的几个函数也是如此。

【易错】 node->next = head 与 head = node 的顺序不能颠倒。

如果颠倒了，那么：
初始状态：
在这里插入图片描述

  • head = node
    在这里插入图片描述

  • node->next = head

显然结果不对

不需要死记硬背，自己画图分析即可

2.3 push_back(T t)

作用：尾插法，在尾结点后面插入一个节点

只需要：将尾结点的 next 指向待插入节点即可
在这里插入图片描述

void push_back(T t)
{Node<T>* node = new Node<T>(t);auto rear = head;while (rear->next != nullptr) {		// 遍历找到尾结点rear = rear->next;	}rear->next = node;	// 将尾结点的 next 指向待插入节点
}

2.4 pop_front()

作用：删除头结点

在这里插入图片描述
你可能直接如下实现：

 void pop_front(){head = head->next;}

但是这存在 内存泄露 问题：被删除的指针所指的内存没有被释放。

 void pop_front(){auto node = head;head = head->next;delete node;	// 释放旧头指针}

【注】 注意 delete node 的时机

来看下面代码：

 void pop_front(){auto node = head;delete node;	head = head->next;}

如果这样做，那么相当于

 void pop_front(){delete head;	head = head->next;}

先 delete head，那么此时 head 所指的内存已经被释放了，此时 head 的值就是一个随机值，之后再使用 head 就是没有意义的，会导致未定义行为，产生逻辑错误甚至程序直接崩溃。

后面涉及到 delete 的函数也需要考虑此问题

2.5 pop_back()

作用：删除尾结点

在这里插入图片描述

void pop_back()
{auto rsecond = head;while (rsecond->next->next != nullptr) {   // 得到尾结点的前一个节点 rsecond = rsecond->next;}delete rsecond->next;	// 释放尾结点rsecond->next = nullptr;
}

需要注意释放完尾结点后，需要将现在的尾结点的 next 指向 nullptr，否则它将指向一块未定义的内存（随机值）。

insert 与 erase 函数涉及到中间节点的插入与删除，因此下面只讲解方法，所有的代码在文章最后

2.6 中间节点的插入

【例】在位置 1 插入节点 node

  • node1 代指图中值为 1 的节点，以此类推… …
  • 默认头结点的下标为 0，那么插入前的位置 1 就是下面的 node2，node1 为待插入节点

在这里插入图片描述

  • node1->next = node2

在这里插入图片描述

  • node0->next = node1
    在这里插入图片描述

2.7 中间节点的删除

【例】删除位置 1 的节点
初始状态：

在这里插入图片描述
你可以直接 node0->next = node2，逻辑上没有问题，但是代码上存在 内存泄漏
在这里插入图片描述
因此在执行 node0->next = node2 前，需要保存被删除的节点，在后续以释放内存。

3. 双向链表

3.1 什么是双链表

在单链表中，你会发现一个问题：单链表只能朝一个方向上（从头到尾）进行遍历，此外由于只存储了头指针，因此在尾结点的插入与删除的时间复杂度都是 O(n)。
为了解决这些问题，双链表就此诞生：
双链表在单链表的基础上增加了尾指针，节点增加了一个指针域（pre）用于指向当前节点的前驱节点。

  • 尾指针：指向尾结点的指针
  • 前驱节点：某节点的前一个节点

在这里插入图片描述

因此你会发现：

  • 头节点的前驱节点为空
  • 尾节点的后继节点为空
  • 其余节点的前驱、后继节点都不为空

由于增加了尾指针，因此在尾结点的插入与删除时间复杂度变为 O(1)，因为此时可以通过尾指针直接在尾结点进行操作。
同时由于加入了 pre 指针，因此可以对链表进行双向遍历。

你理解了单链表的操作，双链表的操作也很容易理解，下面讲解较难的中间节点的插入与删除

3.2 中间节点的插入

【例】在位置 1 插入节点
在这里插入图片描述
看起来比较复杂，其实只需要从目标反推即可。
我们的目标是：
在这里插入图片描述
在之前的单链表中，你可以发现 对于节点的插入：

一般是 先给 待插入节点 的指针域进行赋值，否则可能会丢失某些节点。

比如如果我们先执行 node0->next = node1，会导致 node2 丢失
在这里插入图片描述
因此需要先对待插入节点的指针域进行赋值

当然针对上面的操作，你可以在执行 node0->next = node1 之前，将 node2 进行保存，就不会丢失 node2。
这也是可以的，但是比较浪费空间。

  • node1->pre = node0
  • node1->next = node2

在这里插入图片描述

  • node0->next = node1
  • node2->pre = node1
    在这里插入图片描述

上面的代码有的可以交换位置，有的不可以，所以还是那句话：没必要死记硬背，自己画图分析即可。（在这里重点分析是否是丢失对某节点的指针）

3.3 中间节点的删除

【例】删除位置 1 上的节点
在这里插入图片描述
同理从目标反推：
在这里插入图片描述
因此我们需要

  • node0->next = node2
  • node2->pre = node0

两者可以交换顺序。但这只是就逻辑层面上可以，在代码层面上还需要考虑 内存泄漏，node1 需要被释放。

4. 循环链表

首尾相连 的链表。分为：

  • 单循环链表

    • rear->next = head
      在这里插入图片描述

  • 双循环链表

    • head->pre = rear
    • rear->next = head

在这里插入图片描述

5. 线性表 与 链表 的比较

优点缺点使用场景
顺序表（1）程序设计简单；（2）能随机访问，时间复杂度为O(1)；（3）存储空间利用率高（1）需事先知道表长；（2）插入元素需移动元素；（3）多次插入元素后可能会造成溢出（1）事先确定表长；（2）很少在非尾部位置进行插入和删除；
链表（1）存储空间动态分配，不需事先确定表长；（2）插入与删除只引起指针的变化；（1）程序设计较为复杂；（2）不能随机访问，读取的时间复杂度为O(n)；（3）存在结构性开销；（1）事先不确定表长；（2）需要经常进行插入与删除

【解释】

  • 访问元素的时间复杂度
    • 线性表：由于它的物理存储空间是连续的，所以元素的下标与实际的内存地址存在线性关系，可以直接计算得出，即可以随机访问，因此时间复杂度为 O(1)
    • 链表：物理存储空间一般不连续，故不能随机访问，时间复杂度为 O(n)
  • 不管是线性表还是链表，核心目的都是存储数据。

    • 线性表：它的元素就是所需要存储的数据，所以存储空间利用率高；

    • 链表：它的元素除了所需要存储的数据，还存在指针域以保存额外的信息，但是这部分信息在用户层面上是没必要的。

      尽管底层设计需要维护指针，但是使用它的人只关心链表所存储的数据

      故存在结构性开销，存储空间利用率较低。

最后

单链表实现代码见：SingleList

源码仅一个头文件，将其包含即可进行使用以及测试，如代码有 bug，敬请指正。

本文参考教科书以及网上资料，并加入自己的一些理解。
如有错误或者不足，欢迎指出。

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

CAS详解

CAS详解

文章目录 CAS使用示例Unsafe类实现原理CAS问题 CAS CAS全称为Compare and Swap被译为比较并交换&#xff0c;是一种无锁算法。用于实现并发编程中的原子操作。CAS操作检查某个变量是否与预期的值相同&#xff0c;如果相同则将其更新为新值。CAS操作是原子的&#xff0c;这意味…
阅读更多...
美团收银Android一面凉经(2024)

美团收银Android一面凉经(2024)

美团收银Android一面凉经(2024) 笔者作为一名双非二本毕业7年老Android, 最近面试了不少公司, 目前已告一段落, 整理一下各家的面试问题, 打算陆续发布出来, 供有缘人参考。今天给大家带来的是《美团收银Android一面凉经(2024)》。 应聘岗位: 美团餐饮PaaS平台Android开发工程师…
阅读更多...
使用offset explorer 3.0连接单机版kafka

使用offset explorer 3.0连接单机版kafka

一、目标 使用kafka图形化工具offset explorer 3.0连接单机版的kafka 二、windows下载安装offset explorer 3.0 1、kafka tool工具官方下载页面 Offset Explorer https://www.kafkatool.com/download.html 2、安装offset explorer 3.0 下一步&#xff0c;下一步&#xff0…
阅读更多...
【微信小程序知识点】手机号验证组件

【微信小程序知识点】手机号验证组件

手机验证组件&#xff0c;用于帮助开发者向用户发起手机号申请&#xff0c;必须经过用户同意后&#xff0c;才能获得由平台验证后的手机号&#xff0c;进而为用户提供相应的服务。 手机号验证组件分为两种&#xff1a;手机号快速验证组件以及手机号实时验证组件。 1.手机号快速…
阅读更多...
3D工艺大师快速生成装配动画，驱动汽车工业装配流程革新

3D工艺大师快速生成装配动画，驱动汽车工业装配流程革新

在现代制造业的一般生产流程中&#xff0c;车间装配环节是产品由蓝图迈向市场前至关重要的一道工序。随着产品结构的日益复杂化和个性化需求的不断增长&#xff0c;车间装配工作面临着前所未有的挑战。高精密度的装配要求、错综复杂的组件关系以及频繁变更的生产计划&#xff0…
阅读更多...
羧基聚乙二醇生物素的制备方法；COOH-PEG-Biotin

羧基聚乙二醇生物素的制备方法；COOH-PEG-Biotin

羧基聚乙二醇生物素&#xff08;COOH-PEG-Biotin&#xff09;是一种常见的生物分子聚合物&#xff0c;具有多种应用&#xff0c;特别是在生物实验、药物研发和生物技术等领域。以下是对该化合物的详细解析&#xff1a; 一、基本信息 名称&#xff1a;羧基聚乙二醇生物素&#x…
阅读更多...
小程序创建与项目初始化(构建 npm + 集成 Sass)

小程序创建与项目初始化(构建 npm + 集成 Sass)

一、打开微信开发者工具 确认 左侧导航栏是否选中的 小程序点击 【】创建小程序 二、创建小程序 三、初始化 清空 app.wxss、app.js 去掉 rendererOptions 和 componentFramework 不需要最新的搜索引擎 留下以下文件 四、自定义构建 npm 集成 Sass 首先 先把小程序源…
阅读更多...
Mysql的语句执行很慢，如何分析排查？

Mysql的语句执行很慢，如何分析排查？

1、检查服务器性能是否存在瓶颈 如果系统资源使用率比较高&#xff0c;比如CPU,硬盘&#xff0c;那访问肯定会慢&#xff0c;如果你发现是Mysl占比比较高&#xff0c;说明Mysql的读写频率高&#xff0c;如果本身网站访问量不大&#xff0c;说明你的sql参数&#xff0c;sql语句查…
阅读更多...
WIN10开机突然，过一会就自动重启蓝屏DRIVER_IRQL_NOT_LESS_OR_EQUAL

WIN10开机突然，过一会就自动重启蓝屏DRIVER_IRQL_NOT_LESS_OR_EQUAL

环境&#xff1a; Win10 专业版 DELL7080 问题描述&#xff1a; WIN10开机突然&#xff0c;过一会就自动重启蓝屏DRIVER_IRQL_NOT_LESS_OR_EQUAL 事件日志 解决方案&#xff1a; 1.找到MEMORY.DMP文件内容&#xff0c;分析一下 Microsoft (R) Windows Debugger Version 10…
阅读更多...
.Net Core 微服务之Consul（二）-集群搭建

.Net Core 微服务之Consul（二）-集群搭建

引言： 集合上一期.Net Core 微服务之Consul（一）(.Net Core 微服务之Consul（一）-CSDN博客) 。 目录 一、 Consul集群搭建 1. 高可用 1.1 高可用性概念 1.2 高可用集群的基本原理 1.3 高可用集群的架构设计 1.3.1 主从复制架构 1.3.2 共享存储架构 1.3.3 负载均衡…
阅读更多...
k8s核心操作_k8s中的存储抽象_基本概念与NFS搭建_Deployment使用NFS进行挂载---分布式云原生部署架构搭建028

k8s核心操作_k8s中的存储抽象_基本概念与NFS搭建_Deployment使用NFS进行挂载---分布式云原生部署架构搭建028

然后我们继续开始看 如果我们使用容器部署,比如我们有三个节点,一个是master,一个node1 一个是node2 那么pod 中我们可以看到,容器中的 /data 等各个目录都映射了出来了,但是 如果比如上面红色的部分,有个pod,原来在node2上,最右边那个,但是这个pod宕机了 那么,k8s会在node…
阅读更多...
【开源 Mac 工具推荐之 1】gibMacOS：方便快捷的 macOS 完整包下载 Shell 工具

【开源 Mac 工具推荐之 1】gibMacOS：方便快捷的 macOS 完整包下载 Shell 工具

简介 gibMacOS 是由 GitHub 开发者 corpnewt 编写的一款 Shell 工具。它采用 Python 编程语言&#xff0c;可以让用户打开后在纯文本页面中轻松选择并下载来源于 Apple 官方的 macOS 完整安装包。 Repo 地址&#xff1a;https://github.com/corpnewt/gibMacOS &#xff08;其…
阅读更多...
MATLAB Gazebo联合仿真

MATLAB Gazebo联合仿真

准备仿真环境&#xff1a;在Gazebo中设置仿真场景&#xff0c;包括机器人模型、环境布局、传感器和执行器等。编写MATLAB脚本&#xff1a;在MATLAB中编写控制算法和数据处理脚本&#xff0c;用于接收Gazebo中的传感器数据&#xff0c;并生成控制命令。建立通信&#xff1a;通过…
阅读更多...
（视频演示）基于OpenCV的实时视频跟踪火焰识别软件V1.0源码及exe下载

（视频演示）基于OpenCV的实时视频跟踪火焰识别软件V1.0源码及exe下载

本文介绍了基于OpenCV的实时视频跟踪火焰识别软件&#xff0c;该软件通过先进的图像处理技术实现对实时视频中火焰的检测与跟踪&#xff0c;同时支持导入图片进行火焰识别。主要功能包括相机选择、实时跟踪和图片模式。软件适用于多种场合&#xff0c;用于保障人民生命财产安全…
阅读更多...
细说MCU用定时器控制ADC采样频率的实现方法

细说MCU用定时器控制ADC采样频率的实现方法

目录 一、工程依赖的硬件及背景 二、设计目的 三、 建立工程 1.选择时钟源和Debug模式 2.配置系统时钟和ADC时钟 3.配置串口 4.配置ADC 5.设置TIM3 6.设置TIM4 7.配置中断 8.GPIO 四、代码修改 1.重新定义ADC回调函数 2.在主程序中编写数据发送代码 3.使能ADC和…
阅读更多...
C++ 数据结构探索：构建高效程序的基础

C++ 数据结构探索：构建高效程序的基础

C 数据结构探索&#xff1a;构建高效程序的基础 在C编程的广阔领域中&#xff0c;数据结构是理解和实现高效、可维护程序的核心。数据结构是计算机存储、组织数据的方式&#xff0c;它们使得数据访问和修改操作更加高效。本文将带您走进C中几种常见且重要的数据结构&#xff0…
阅读更多...
关键路径-matlab

关键路径-matlab

路径上边的数目称为路径长度 图的基本知识 求最短路径&#xff08;Dijkstra算法&#xff09; 2. 待继续尝试 ①Dijkstra ②floyd_all.m 一 二 ③ LeetCode [329. 矩阵中的最长递增路径]
阅读更多...
ROS2 + 科大讯飞 初步实现机器人语音控制

ROS2 + 科大讯飞 初步实现机器人语音控制

环境配置&#xff1a; 电脑端&#xff1a; ubuntu22.04实体机作为上位机 ROS版本&#xff1a;ros2-humble 实体机器人&#xff1a; STM32 思岚A1激光雷达 科大讯飞语音SDK 讯飞开放平台-以语音交互为核心的人工智能开放平台 实现步骤&#xff1a; 1. 下载和处理科大讯飞语音模…
阅读更多...
npm install 报错：PhantomJS not found on PATH

npm install 报错：PhantomJS not found on PATH

npm install 报错&#xff1a;PhantomJS not found on PATH 整体报错内容 npm ERR! code 1 npm ERR! path G:\work-learn\open-coding\bruno\node_modules\phantomjs-prebuilt npm ERR! command failed npm ERR! command C:\Windows\system32\cmd.exe /d /s /c node install.…
阅读更多...
Python应用爬虫下载QQ音乐歌曲！

Python应用爬虫下载QQ音乐歌曲！

目录&#xff1a; 1.简介怎样实现下载QQ音乐的过程&#xff1b; 2.代码 1.下载QQ音乐的过程 首先我们先来到QQ音乐的官网&#xff1a; https://y.qq.com/&#xff0c;在搜索栏上输入一首歌曲的名称&#xff1b; 如我在上输入最美的期待&#xff0c;按回车来到这个画面 我们首…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发