C++手写链表、反转链表、删除链表节点、遍历、为链表增加迭代器

  本篇博客介绍如何使用C++实现链表，首先编写一个简单的链表，然后增加模板，再增加迭代器。

简单链表的实现

  链表的结构如下：
在这里插入图片描述

  首先需要定义链表的节点：

struct ListNode
{int data;ListNode* pNext;ListNode(int value = 0):data(value), pNext(nullptr){}
};

  再定义链表类

class LinkedList
{
public:LinkedList():m_pHead(nullptr){}~LinkedList(){Clear();}void Add(int value){if(!m_pHead){m_pHead = new ListNode(value);}else{ListNode* current = m_pHead;while(current->pNext){current = current->pNext;}current->pNext = new ListNode(value);}}void PrintList(){if(!m_pHead){cout << "LinkedList is empty" << endl;return;}ListNode* current = m_pHead;while (current){cout << current->data << " ";current = current->pNext;}cout << endl;}// 反转链表void Reverse() {ListNode* prev = nullptr;ListNode* current = m_pHead;ListNode* next = nullptr;// 从头节点开始反转，让头节点指向空，让下一个节点指向头节点while (current != nullptr) {next = current->pNext;   // 保存下一个节点current->pNext = prev;   // 反转当前节点的指针prev = current;         // 更新prev到当前节点current = next;         // 移动到下一个节点}m_pHead = prev; // 更新头节点}// 删除第一个具有指定值的元素void Remove(int val) {if (!m_pHead)return;// 如果要删除的是头节点if (m_pHead->data == val) {ListNode* toDelete = m_pHead;m_pHead = m_pHead->pNext;delete toDelete;return;}ListNode* current = m_pHead;while (current->pNext && current->pNext->data != val) {current = current->pNext;}if (current->pNext) {ListNode* toDelete = current->pNext;current->pNext = current->pNext->pNext;delete toDelete;}}void Clear(){while (m_pHead){ListNode* pDelete = m_pHead;m_pHead = m_pHead->pNext;delete pDelete;pDelete = nullptr;}}private:ListNode* m_pHead;
};

  main代码测试：

#include <iostream>
#include "LinkedList0.h"using namespace std;int main()
{   LinkedList* pList = new LinkedList();pList->Add(1);pList->Add(4);pList->Add(7);pList->Add(10);pList->PrintList();pList->Reverse();pList->PrintList();pList->Remove(7);pList->PrintList();delete pList;pList = nullptr;return 0;
}

运行结果如下：
1 4 7 10
10 7 4 1
10 4 1

如何添加链表元素

  首先根据头指针的位置，将头指针移到末尾，当然这里使用的临时指针current 来移动，然后将头结点的next只想新的结点, 头指针m_pHead的地址并没有变化。

void Add(int value)
{if(!m_pHead){m_pHead = new ListNode(value);}else{ListNode* current = m_pHead;while(current->pNext){current = current->pNext;}current->pNext = new ListNode(value);}
}

如何清空链表

  从链表头开始依次清空

void Clear(){while (m_pHead){ListNode* pDelete = m_pHead;m_pHead = m_pHead->pNext;delete pDelete;pDelete = nullptr;}}

  这里也是移动头指针，知道达到尾结点的next.

如何删除链表节点

  删除链表节点会改变当前节点的指向，如果删除的是头结点，则比较简单，删除其它结点相对复杂

如何反转链表

  反转链表也是面试中的经常考察的点，需要非常熟练，主要是思路，从头结点开始原地反转，只是代码的写法相对复杂点，一旦操作顺序不对，很容易出错，代码如下：

// 反转链表
void Reverse() {ListNode* prev = nullptr;ListNode* current = m_pHead;ListNode* next = nullptr;// 从头节点开始反转，让头节点指向空，让下一个节点指向头节点while (current != nullptr) {next = current->pNext;   // 保存下一个节点current->pNext = prev;   // 反转当前节点的指针prev = current;         // 更新prev到当前节点current = next;         // 移动到下一个节点}m_pHead = prev; // 更新头节点
}

链表模板的实现

  代码如下：

/*自定义链表 
添加迭代器*/#pragma once
#include <iostream>using namespace std;template<class T>
struct ListNode
{T data;ListNode<T>* pNext;ListNode(T value = 0):data(value), pNext(nullptr){}
};// 迭代器类
template<typename T>
class LinkedListIterator {
public:explicit LinkedListIterator(ListNode<T>* node) : m_node(node) {}T& operator*() const { cout << "run T& operator*() const " << endl;return m_node->data; }T* operator->() { cout << "run T* operator->()" << endl;return &m_node->data; }// 前缀递增LinkedListIterator& operator++() {cout << "run LinkedListIterator 前缀递增" << endl;m_node = m_node->pNext;return *this;}// 后缀递增LinkedListIterator operator++(int) {cout << "run LinkedListIterator 后缀递增" << endl;LinkedListIterator temp = *this;m_node = m_node->pNext;return temp;}friend bool operator==(const LinkedListIterator& a, const LinkedListIterator& b) {return a.m_node == b.m_node;};friend bool operator!=(const LinkedListIterator& a, const LinkedListIterator& b) {return a.m_node != b.m_node;};private:ListNode<T>* m_node;
};template<class T>
class LinkedList
{
public:using iterator = LinkedListIterator<T>;   // 先声明，并且是public, 不然在外部无法使用public:LinkedList():m_pHead(nullptr){}~LinkedList(){Clear();}void Add(T value){if(!m_pHead){m_pHead = new ListNode<T>(value);}else{ListNode<T>* current = m_pHead;while(current->pNext){current = current->pNext;}current->pNext = new ListNode<T>(value);}}void PrintList(){if(!m_pHead){cout << "LinkedList is empty" << endl;return;}ListNode<T>* current = m_pHead;while (current){cout << current->data << " ";current = current->pNext;}cout << endl;}// 反转链表void Reverse() {ListNode<T>* prev = nullptr;ListNode<T>* current = m_pHead;ListNode<T>* next = nullptr;// 从头节点开始反转，让头节点指向空，让下一个节点指向头节点while (current != nullptr) {next = current->pNext;   // 保存下一个节点current->pNext = prev;   // 反转当前节点的指针prev = current;         // 更新prev到当前节点current = next;         // 移动到下一个节点}m_pHead = prev; // 更新头节点}// 删除第一个具有指定值的元素void Remove(T val) {if (!m_pHead)return;// 如果要删除的是头节点if (m_pHead->data == val) {ListNode<T>* toDelete = m_pHead;m_pHead = m_pHead->pNext;delete toDelete;return;}ListNode<T>* current = m_pHead;while (current->pNext && current->pNext->data != val) {current = current->pNext;}if (current->pNext) {ListNode<T>* toDelete = current->pNext;current->pNext = current->pNext->pNext;delete toDelete;}}void Clear(){while (m_pHead){ListNode<T>* pDelete = m_pHead;m_pHead = m_pHead->pNext;delete pDelete;pDelete = nullptr;}}iterator begin() {return iterator(m_pHead);}iterator end() {return iterator(nullptr);}private:ListNode<T>* m_pHead;
};

  在简单链表的基础上增加模板，这个不难，难得是如何给链表增加迭代器。

  main函数测试：

int main()
{   LinkedList<int>* pList = new LinkedList<int>();pList->Add(10);pList->Add(40);pList->Add(70);pList->Add(100);pList->PrintList();pList->Reverse();pList->PrintList();pList->Remove(70);pList->PrintList();cout << "使用迭代器" << endl;//for(LinkedList<int>::iterator it = pList->begin(); it != pList->end(); it++)for(auto it = pList->begin(); it != pList->end(); it++){cout << *it << " ";}cout << endl;delete pList;pList = nullptr;return 0;
}

运行结果如下：
10 40 70 100
100 70 40 10
100 40 10
使用迭代器
run T& operator*() const
100 run LinkedListIterator 后缀递增
run T& operator*() const
40 run LinkedListIterator 后缀递增
run T& operator*() const
10 run LinkedListIterator 后缀递增

如何为链表添加迭代器

  迭代器可以理解为是一个类，在类里封装了对象的++操作之类的方法，声明迭代器类，然后在链表类里声明begin()和end()来获取迭代器，begin()返回指向容器第一个元素的迭代器，而end()返回指向容器末尾的下一个位置的迭代器。比如上面的迭代器声明如下：

// 迭代器类
template<typename T>
class LinkedListIterator {
public:explicit LinkedListIterator(ListNode<T>* node) : m_node(node) {}T& operator*() const { cout << "run T& operator*() const " << endl;return m_node->data; }T* operator->() { cout << "run T* operator->()" << endl;return &m_node->data; }// 前缀递增LinkedListIterator& operator++() {cout << "run LinkedListIterator 前缀递增" << endl;m_node = m_node->pNext;return *this;}// 后缀递增LinkedListIterator operator++(int) {cout << "run LinkedListIterator 后缀递增" << endl;LinkedListIterator temp = *this;m_node = m_node->pNext;return temp;}friend bool operator==(const LinkedListIterator& a, const LinkedListIterator& b) {return a.m_node == b.m_node;};friend bool operator!=(const LinkedListIterator& a, const LinkedListIterator& b) {return a.m_node != b.m_node;};private:ListNode<T>* m_node;
};

  然后再链表类里声明begin和end方法：

using iterator = LinkedListIterator<T>;   // 先声明，并且是public, 不然在外部无法使用iterator begin() {return iterator(m_pHead);
}iterator end() {return iterator(nullptr);
}

  需要注意的是在迭代器类里重写了“前加加”和“后加加”运算符，他们二者有区别

前加加

// 前缀递增
LinkedListIterator& operator++() {cout << "run LinkedListIterator 前缀递增" << endl;m_node = m_node->pNext;return *this;
}

注意这里返回的是引用。

问题：重写"前加加"为什么返回引用？

  在C++中，迭代器的前缀递增（++it）操作符通常返回一个到自身的引用，这样做有几个原因：

  1. 链式操作：返回引用允许连续调用操作符或方法。例如，++(++it)或(*++it).method()。如果不返回自身的引用，这样的操作将无法执行，因为递增操作将不会在原始迭代器上进行。
  2. 性能：通过返回自身的引用，可以避免不必要的对象复制。如果递增操作返回一个新的迭代器实例而不是引用，那么每次递增操作都会产生一个临时迭代器对象，这将增加额外的构造和析构开销。返回引用避免了这些潜在的性能问题。
  3. 一致性和期望：在STL（Standard Template Library，标准模板库）中，迭代器遵循一定的惯例和模式，其中前缀递增返回引用就是这些标准操作之一。遵循这些惯例可以使自定义迭代器的行为与STL中的迭代器保持一致，从而减少使用时的困惑。
  4. 语义清晰：返回自身的引用清楚地表明了前缀递增操作是在修改迭代器本身，而不是创建一个新的迭代器实例。这使得代码的意图更加明确，有助于代码的阅读和维护。

  考虑到这些理由，迭代器设计时通常会使得前缀递增操作符返回迭代器的引用。这是一种约定，也是一种优化设计和实现的方法。而后缀递增（it++）通常返回迭代器的值，这需要创建当前迭代器的一个副本，然后对原迭代器进行递增操作，最后返回副本。这种区别设计允许区分前缀和后缀递增的语义和性能特点。

后加加

代码如下

// 后缀递增
LinkedListIterator operator++(int) {cout << "run LinkedListIterator 后缀递增" << endl;LinkedListIterator temp = *this;m_node = m_node->pNext;return temp;
}

问题：为什么“后加加不返回引用”？

  后缀递增操作符（it++）不返回引用的原因是它的语义和行为要求。后缀递增操作的预期行为是先返回迭代器当前的值，然后再对其进行递增。这意味着必须先创建当前状态的一个副本，然后递增原迭代器，最后返回那个副本。这个过程涉及到以下几个关键点：

  1. 值的保留：后缀递增需要保留迭代器递增前的状态。为了实现这一点，它通过创建当前迭代器的一个副本来保存当前状态，然后递增原迭代器，最后返回副本。如果后缀递增返回了引用，那么它将无法满足“先返回当前状态然后递增”的语义要求。
  2. 避免修改返回的迭代器：由于后缀递增返回的是递增前的状态，如果这个返回值是引用，使用者可能会错误地认为对返回的迭代器进行修改会影响到原始迭代器，这与后缀递增的预期行为不符。返回一个副本可以明确表明返回的迭代器是一个全新的、与原迭代器无关的实例。
  3. 语义清晰性：通过返回一个副本而不是引用，后缀递增明确表示了它和前缀递增的不同。前缀递增(++it)表示对原迭代器自身的修改并返回修改后的自身，更适合效率要求较高的场合；而后缀递增(it++)则强调返回原始状态的副本，适用于先使用当前值再递增的场景，即使这意味着可能有额外的性能开销。
  4. 性能考虑：后缀递增的性能通常比前缀递增低，因为它涉及到复制操作。这是设计选择的一部分，开发者在意识到这一点的情况下会倾向于在不需要副本的场景中使用前缀递增，以提高代码的效率。

  综上所述，后缀递增不返回引用是为了满足其特定的语义需求，保证操作的正确性，同时也是为了与前缀递增明确区分，让两者的用途和性能特点更加清晰。

迭代时如何取值

  在使用迭代器中，会有“*it”的取值方法，代码如下：

//for(LinkedList<int>::iterator it = pList->begin(); it != pList->end(); it++)for(auto it = pList->begin(); it != pList->end(); it++){cout << *it << " ";}

  这种“*it”写法，需要重写星号操作符来实现，代码如下：

T& operator*() const { cout << "run T& operator*() const " << endl;return m_node->data; 
}

  以上是本篇博客的主要内容，这是链表的基本实现，当然还可以增加锁来实现线程安全，如果在多线程环境担心std容器的安全性，大家可以使用线程安全的容器，比如TBB库提供的容器。TBB链接如下： https://www.intel.com/content/www/us/en/developer/tools/oneapi/onetbb.html

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

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

相关文章

使用STM32+ESP8266（ESP-01S）+点灯科技（手机端Blinker）实现远程控制智能家居

使用STM32+ESP8266（ESP-01S）+点灯科技（手机端Blinker）实现远程控制智能家居

硬件准备&#xff1a;STM32单片机、ESP8266&#xff08;ESP-01S&#xff09;、CH340C下载烧录器 软件准备&#xff1a;STM32CubeMX、Keil uVision5、Arduino IDE、 点灯科技&#xff08;手机端APP Blinker&#xff09;点灯科技 (diandeng.tech)点击进入 值得注意的是&#x…
阅读更多...
Redis：ClassCastException【bug】

Redis：ClassCastException【bug】

Redis&#xff1a;ClassCastException【bug】 前言版权Redis&#xff1a;ClassCastException【bug】错误产生相关资源控制器&#xff1a;UserController("/user")配置&#xff1a;RedisConfiguration实体类&#xff1a;User数据表&#xff1a;User 解决 最后 前言 2…
阅读更多...
R语言语法基础（说人话版）

R语言语法基础（说人话版）

在Rstudio中使用ctrl回车来执行某一行的代码 在R语言中&#xff0c;通常不需要像C语言一样在每条语句的结尾添加分号来表示语句结束。R语言是一种脚本语言&#xff0c;它使用换行符来分隔语句&#xff0c;因此分号通常是可选的&#xff0c;除非你想在同一行上写多个语句。在R中…
阅读更多...
03-java基础-运算符（数据类型转换）、原码、补码、反码

03-java基础-运算符（数据类型转换）、原码、补码、反码

一、运算符 一、1、算术运算符 在代码中如果有小数参与运算&#xff0c;结果有可能会不精确。 一、1.1、数字相加 一、1.1.1、类型转换的分类&#xff08;2种&#xff09; 一、1.1.1.1、类型转换的分类1-----隐式转换 一、1.1.1.1、类型转换的分类2-----强制转换 一、1.2、字符…
阅读更多...
EtherCAT开源主站 IGH 介绍及主站伺服控制过程

EtherCAT开源主站 IGH 介绍及主站伺服控制过程

目录 前言 IGH EtherCAT主站介绍 主要特点和功能 使用场景 SOEM 主站介绍 SOEM 的特点和功能 SOEM 的使用场景 IGH 主站 和 SOEM对比 1. 功能和复杂性 2. 资源消耗和移植性 3. 使用场景 EtherCAT 通信原理 EtherCAT主站控制伺服过程 位置规划模式 原点复归模式…
阅读更多...
ASP.NET Mvc+FFmpeg+Video实现视频转码

ASP.NET Mvc+FFmpeg+Video实现视频转码

目录 首先&#xff0c;做了视频上传的页面&#xff1a; FFmpeg&#xff1a;视频转码 FFmpegHelper工作类&#xff1a; 后台控制器代码&#xff1a; 前端视图代码&#xff1a; 参考文章&#xff1a; 首先&#xff0c;做了视频上传的页面&#xff1a; 借鉴了这篇文章 ASP.…
阅读更多...
应用层_HTTPHTTPS

应用层_HTTPHTTPS

在应用层中&#xff0c;协议一般是程序员定制的&#xff0c;但现在已经有了许多非常好用的协议&#xff0c;我们可以直接参考使用。其中http和https便是其中最常用的协议之一。 一.HTTP 超文本传输协议&#xff08;Hypertext Transfer Protocol&#xff0c;HTTP&#xff09;…
阅读更多...
腾讯春招后端一面（八股篇）

腾讯春招后端一面（八股篇）

前言 前几天在网上发了腾讯面试官问的一些问题&#xff0c;好多小伙伴关注&#xff0c;今天对这些问题写个具体答案&#xff0c;博主好久没看八股了&#xff0c;正好复习一下。 面试手撕了三道算法&#xff0c;这部分之后更&#xff0c;喜欢的小伙伴可以留意一下我的账号。 1…
阅读更多...
【C语言】—— 指针二 ： 初识指针（下）

【C语言】—— 指针二 ： 初识指针（下）

【C语言】——函数栈帧 一、 c o n s t const const 修饰指针1.1、 c o n s t const const 修饰变量1.2、 c o n s t const const 修饰指针 二、野指针2.1野指针的成因&#xff08;1&#xff09;指针未初始化&#xff08;2&#xff09;指针越界访问&#xff08;3&#xff09;指…
阅读更多...
HNU-计算机系统-实验1-原型机vspm1.0-（二周目玩家视角）

HNU-计算机系统-实验1-原型机vspm1.0-（二周目玩家视角）

前言 二周目玩家&#xff0c;浅试一下这次的原型机实验。总体感觉跟上一年的很相似&#xff0c;但还是有所不同。 可以比较明显地感觉到&#xff0c;这个界面越来越好看了&#xff0c;可操作与可探索的功能也越来越多了。 我们HNU的SYSTEM真的越来越好了&#xff01;&#x…
阅读更多...
5 个适用于 Windows 10 和 11 的最佳 PDF 转 Word 转换器

5 个适用于 Windows 10 和 11 的最佳 PDF 转 Word 转换器

PDF 文件是共享文档的首选格式&#xff0c;但是此类文件存在一些限制&#xff0c;导致难以修改或编辑。因此&#xff0c;您可能会发现自己正在寻找一种将 PDF 文件转换为 Word 或其他可编辑格式的方法。 有许多不同的 PDF 转换器&#xff0c;每种转换器提供的功能略有不同。本…
阅读更多...
个人简历主页搭建系列-03：Hexo+Github Pages 介绍，框架配置

个人简历主页搭建系列-03：Hexo+Github Pages 介绍，框架配置

今天的更新内容主要是了解为什么选择这个网站搭建方案&#xff0c;以及一些前置软件的安装。 Why Hexo? 首先我们了解一下几种简单的网站框架搭建方案&#xff0c;看看对于搭建简历网站的需求哪个更合适。 在 BuiltWith&#xff08;网站技术分析工具&#xff09;上我们可以…
阅读更多...
微信小程序（一）

微信小程序（一）

WebView app.是全局配置&#xff0c;app.json是全局配置文件&#xff0c;在页面的.json配置文件中的配置会覆盖我们全局的配置 快捷键&#xff1a; .box 敲回车 ----- <view class"box"></view> .row*8 敲回车&#xff1a; .row{$}*8 敲回车 案例1&…
阅读更多...
信雅纳网络测试的二次开发集成：XOA（Xena Open-Source Automation）开源自动化测试

信雅纳网络测试的二次开发集成：XOA（Xena Open-Source Automation）开源自动化测试

目录 XOA是什么 XOA CLI XOA Python API ​XOA Python Test Suite/测试套件 XOA Converter Source Code XOA是什么 XOA&#xff08;Xena Open-Source Automation&#xff09;是一个开源的测试自动化框架&#xff0c;追求“高效、易用、灵活”的跨操作系统的开发框架。能…
阅读更多...
Android SystemServer进程解析

Android SystemServer进程解析

SystemServer进程在android系统中占了举足轻重的地位&#xff0c;系统的所有服务和SystemUI都是由它启动。 一、SystemServer进程主函数流程 1、主函数三部曲 //frameworks/base/services/java/com/android/server/SystemServer.java /** * The main entry point from zy…
阅读更多...
Docker使用(四)Docker常见问题分析和解决收集整理

Docker使用(四)Docker常见问题分析和解决收集整理

Docker使用(四)Docker常见问题分析和解决收集整理 五、常见问题 1、 启动异常 【描述】&#xff1a; 【分析】&#xff1a;[rootlocalhost ~]# systemctl status docker 【解决】&#xff1a; &#xff08;1&#xff09;卸载后重新安装&#xff0c;不能解决这个问题。 …
阅读更多...
基于正点原子潘多拉STM32L496开发板的简易示波器

基于正点原子潘多拉STM32L496开发板的简易示波器

一、前言 由于需要对ADC采样性能的评估&#xff0c;重点在于对原波形的拟合性能。 考虑到数据的直观性&#xff0c;本来计划采集后使用串口导出&#xff0c;并用图形做数据拟合&#xff0c;但是这样做的效率低下&#xff0c;不符合实时观察的需要&#xff0c;于是将开发板的屏幕…
阅读更多...
oracle基础-子查询 备份

oracle基础-子查询 备份

一、什么是子查询 子查询是在SQL语句内的另外一条select语句&#xff0c;也被称为内查询活着内select语句。在select、insert、update、delete命令中允许是一个表达式的地方都可以包含子查询&#xff0c;子查询也可以包含在另一个子查询中。 【例1.1】在Scott模式下&#xff0…
阅读更多...
AJAX学习（四）

AJAX学习（四）

版权声明 本文章来源于B站上的某马课程&#xff0c;由本人整理&#xff0c;仅供学习交流使用。如涉及侵权问题&#xff0c;请立即与本人联系&#xff0c;本人将积极配合删除相关内容。感谢理解和支持&#xff0c;本人致力于维护原创作品的权益&#xff0c;共同营造一个尊重知识…
阅读更多...
github 中的java前后端项目整合到本地运行

github 中的java前后端项目整合到本地运行

前言: 本文章中所有内容仅供学习交流使用&#xff0c;不用于其他任何目的&#xff0c;不提供完整代码&#xff0c;抓包内容、敏感网址、数据接口等均已做脱敏处理&#xff0c;严禁用于商业用途和非法用途&#xff0c;否则由此产生的一切后果均与作者无关&#xff01; 本文章未…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023