当前位置: 首页 > news >正文

C++数据结构之:链List

摘要:

  it人员无论是使用哪种高级语言开发东东,想要更高效有层次的开发程序的话都躲不开三件套:数据结构,算法和设计模式。数据结构是相互之间存在一种或多种特定关系的数据元素的集合,即带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系,分为逻辑结构和存储结构。

  此系列专注讲解数据结构数组、链表、队列、栈、树、哈希表、图,通过介绍概念以及提及一些可能适用的场景,并以C++代码简易实现,多方面认识数据结构,最后为避免重复造轮子会浅提对应的STL容器。本文介绍的是链List。

(开发环境:VScode,C++17)

关键词C++数据结构链表List

声明:本文作者原创,转载请附上文章出处与本文链接。

文章目录

      • 摘要:
      • 正文:
        • 介绍:
          • 特性:
          • 应用:
        • 代码实现:
        • 对应STL:
      • 推荐阅读

正文:

介绍:

  链表(Linked List)是一种常见的数据结构,它通过一系列的节点(Node)来存储数据,每个节点包含两个部分:一个是数据域(Data Field),用于存储数据;另一个是链接域(Link Field),用于存储指向下一个节点的引用(在单链表中)或前一个节点和下一个节点的引用(在双向链表中)。链表数据一般都是分散存储于内存中 的,无须存储在连续空间内。

双向链表:

在这里插入图片描述

特性:
  • 动态性:链表不需要在内存中预先分配固定大小的空间,可以根据需要动态地创建和删除节点。这使得链表在处理不确定大小的数据集合时非常灵活。
  • 多种类型:链表有多种类型,包括单向链表、双向链表、循环链表等。每种类型的链表都有其特定的应用场景和优缺点。
  • 插入和删除效率高:在链表中插入或删除一个节点时,只需要修改相关节点的指针(或引用)即可,而不需要移动大量数据。
  • 非连续性:链表中的节点在内存中不一定是连续存储的。每个节点都包含一个指向下一个节点的指针(或引用),这些指针(或引用)将节点连接在一起。
应用:
  • 实现堆栈(Stack)和队列(Queue)等抽象数据类型。
  • 在数据库中实现邻接列表来表示图(Graph)。
  • 在浏览器中表示历史记录或书签。
  • 在操作系统中表示进程列表或文件列表。
  • 在许多算法中,如归并排序(Merge Sort)和快速排序(Quick Sort)的链表实现等。
代码实现:
#clist.h
#ifndef CLIST_H
#define CLIST_H
#include <iostream>
#include <cstdlib>using namespace std;
// 链表结点
template <class T>
class DNode
{
public:DNode<T> *next;DNode<T> *prev;T data;
};// 双向列表类
template <class T>
class CList
{
public:CList();                     // 默认构造函数CList(const CList& ln);      // 拷贝构造函数~CList();                    // 析构函数void add(T e);               // 向链表添加数据void remove(T index);        // 移除某个结点T find(int index);           // 查找结点bool empty();                // 判断是否为空int size();                  // 链表长度void print();                // 显示链表void print_reverse();        // 链表反向显示void clear();                // 删除全部结点
private:DNode<T> *head;DNode<T> *tail;int length;
};// 默认构造函数
template <typename T>
CList<T>::CList()
{head = new DNode<T>;tail = new DNode<T>;head->next = tail;head->prev = nullptr;tail->next = nullptr;tail->prev = head;length = 0;
}// 拷贝构造函数
template <typename T>
CList<T>::CList(const CList &ln)
{head = new DNode<T>;head->prev = nullptr;tail = new DNode<T>;head->next = tail;tail->prev = head;length = 0;DNode<T>* temp = ln.head;while (temp->next != ln.tail){temp = temp->next;tail->data = temp->data;DNode<T> *p = new DNode<T>;p->prev = tail;tail->next = p;tail = p;length++;}tail->next = nullptr;
}// 析构函数
template <typename T>
CList<T>::~CList()
{if (length == 0){delete head;delete tail;head = nullptr;tail = nullptr;return;}while (head->next != nullptr){DNode<T> *temp = head;head = head->next;delete temp;}delete head;head = nullptr;
}// 向链表添加数据
template <typename T>
void CList<T>::add(T e)
{DNode<T>* temp = this->tail;tail->data = e;tail->next = new DNode<T>;DNode<T> *p = tail;tail = tail->next;tail->prev = p;tail->next = nullptr;length++;
}// 查找结点
template <typename T>
T CList<T>::find(int index)
{if (length == 0){cout << "CList is empty";return -1;}if (index >= length){cout << "Out of bounds";return -1;}int x = 0;DNode<T> *p;p = head->next;while (p->next != nullptr && x++ != index){p = p->next;}return p->data;
}// 删除结点
template <typename T>
void CList<T>::remove(T index)
{if (length == 0){cout << "CList is empty";return;}DNode<T> *p = head;while (p->next != nullptr){p = p->next;if (p->data == index){DNode<T> *temp = p->prev;temp->next = p->next;p->next->prev = temp;delete p;length--;return;}}
}// 删除所有结点
template <typename T>
void CList<T>::clear()
{if (length == 0){return;}DNode<T> *p = head->next;while (p != tail){DNode<T>* temp = p;p = p->next;delete temp;}head->next = tail;tail->prev = head;length = 0;
}// 判断是否为空
template <typename T>
bool CList<T>::empty()
{if (length == 0){return true;}else {return false;}
}// 链表长度
template <typename T>
int CList<T>::size()
{return length;
}// 输出链表
template <typename T>
void CList<T>::print()
{if (length == 0){cout << "CList is empty" << endl;return;}DNode<T> *p = head->next;while (p != tail){cout << p->data << " ";p = p->next;}cout << endl;
}// 反向输出链表
template <typename T>
void CList<T>::print_reverse()
{if (length == 0)return;DNode<T> *p = tail->prev;while (p != head){cout << p->data << " ";p = p->prev;}cout << endl;
}#endif // !CLIST_H
#clist.cpp
#include "clist.h"
#include <iostream>
using namespace std;int main(int argc, char**argv)
{CList<int> list;list.add(6);list.add(443);list.add(767);list.add(56);CList<int> list2(list);list2.print_reverse();list2.print();cout << "list2.size(): " << list2.size() << endl;cout << "list2.find(2): " << list2.find(2) << endl;list2.remove(443);list2.print();return 0;
}

在这里插入图片描述

对应STL:
  • list:

    双向循环链表。使用起来很高效,对于任意位置的插入和删除都很快,在操作过后,以后指针、迭代器、引用都不会失效。

  • forward_list:

    单向链表。只支持单向访问,在链表的任何位置进行插入/删除操作都非常快

推荐阅读

C/C++专栏:https://blog.csdn.net/weixin_45068267/category_12268204.html
(包含其它数据结构即对应的STL容器使用)

相关文章:

C++数据结构之:链List

摘要&#xff1a; it人员无论是使用哪种高级语言开发东东&#xff0c;想要更高效有层次的开发程序的话都躲不开三件套&#xff1a;数据结构&#xff0c;算法和设计模式。数据结构是相互之间存在一种或多种特定关系的数据元素的集合&#xff0c;即带“结构”的数据元素的集合&am…...

10.Redis之set类型

谈到一个术语,这个术语很可能有多种含义~~ 1.Set 1) 集合. 2)设置 (和 get 相对应) 集合就是把一些有关联的数据放到一起~~ 1.集合中的元素是无序的! 【此处说的无序和 前面list这里的有序 是对应的, 有序: 顺序很重要. 变换一下顺序, 就是不同的 list 了 无序: 顺序不…...

SpringBoot + mongodb 删除集合中的数据

MongoTemplate是Spring Data MongoDB提供的一个工具类&#xff0c;用于与MongoDB进行交互。它提供了许多方法来执行数据库操作&#xff0c;包括删除数据。 本文将介绍如何使用Java MongoTemplate删除集合内的数据&#xff0c;并提供相应的代码示例。 1. 引入MongoTemplate 首…...

【日常记录】【JS】前端预览图片的两种方式,Base64预览和blob预览

文章目录 1、前言1、FileReader3、window.URL.createObjectURL4、参考链接 1、前言 一般来说&#xff0c;都是 后端返回给前端图片的url&#xff0c;前端直接把这个值插入到 img 的src 里面即可还有一种情况是前端需要预览一下图片&#xff0c;比如&#xff1a;上传头像按钮&a…...

每日刷题——杭电2156.分数矩阵和杭电2024.C语言合法标识符

杭电2156.分数矩阵 原题链接&#xff1a;Problem - 2156 题目描述 Problem Description&#xff1a;我们定义如下矩阵: 1/1 1/2 1/3 1/2 1/1 1/2 1/3 1/2 1/1 矩阵对角线上的元素始终是1/1&#xff0c;对角线两边分数的分母逐个递增。请求出这个矩阵的总和。 Input&#xf…...

爬虫学习--18.反爬斗争 selenium(3)

操作多窗口与页面切换 有时候窗口中有很多子tab页面。这时候肯定是需要进行切换的。selenium提供了一个叫做switch_to.window来进行切换&#xff0c;具体切换到哪个页面&#xff0c;可以从driver.window_handles中找到。 from selenium import webdriver from selenium.webdri…...

如何评价GPT-4o?

GPT-4o是OpenAI为聊天机器人ChatGPT发布的一款新语言模型&#xff0c;其名称中的“o”代表Omni&#xff0c;即全能的意思&#xff0c;凸显了其多功能的特性。这款模型在多个方面都有着显著的优势和进步。 首先&#xff0c;GPT-4o具有极强的多模态能力&#xff0c;它能够接受文本…...

算能BM1684+FPGA+AI+Camera推理边缘计算盒

搭载算丰智算芯片BM1684&#xff0c;是面向AI推理的边缘计算盒。高效适配市场上所有AI算法&#xff0c;实现视频结构化、人脸识别、行为分析、状态监测等应用&#xff0c;为智慧城市、智慧交通、智慧能源、智慧金融、智慧电信、智慧工业等领域进行AI赋能。 产品规格 处理器芯片…...

不同厂商SOC芯片在视频记录仪领域的应用

不同SoC公司芯片在不同产品上的应用信息&#xff1a; 大唐半导体 芯片型号: LC1860C (主控) LC1160 (PMU)产品应用: 红米2A (399元)大疆晓Spark技术规格: 28nm工艺&#xff0c;4个ARM Cortex-A7处理器&#xff0c;1.5GHz主频&#xff0c;2核MaliT628 GPU&#xff0c;1300万像…...

【Python入门学习笔记】Python3超详细的入门学习笔记,非常详细(适合小白入门学习)

Python3基础 想要获取pdf或markdown格式的笔记文件点击以下链接获取 Python入门学习笔记点击我获取 1&#xff0c;Python3 基础语法 1-1 编码 默认情况下&#xff0c;Python 3 源码文件以 UTF-8 编码&#xff0c;所有字符串都是 unicode 字符串。 当然你也可以为源码文件指…...

通用代码生成器应用场景三,遗留项目反向工程

通用代码生成器应用场景三&#xff0c;遗留项目反向工程 如果您有一个遗留项目&#xff0c;要重新开发&#xff0c;或者源代码遗失&#xff0c;或者需要重新开发&#xff0c;但是希望复用原来的数据&#xff0c;并加快开发。 如果您的项目是通用代码生成器生成的&#xff0c;…...

轻量级动态可监控线程池 - DynamicTp

一、背景介绍 使用线程池ThreadPoolExecutor的过程中你是否有以下痛点呢&#xff1f; 代码中创建了一个 ThreadPoolExecutor&#xff0c;但是不知道那几个核心参数设置多少比较合适凭经验设置参数值&#xff0c;上线后发现需要调整&#xff0c;改代码重新发布服务&#xff0c…...

对于vsc中的vue命令 vue.json

打开vsc 然后在左下角有一个设置 2.点击用户代码片段 3.输入 vue.json回车 将此代码粘贴 &#xff08;我的不一定都适合&#xff09; { "vue2 template": { "prefix": "v2", "body": [ "<template>", " <…...

Spring Boot 官方不再支持 Spring Boot 的 2.x 版本!新idea如何创建java8项目

idea现在只能创建最少jdk17 使用 IDEA 内置的 Spring Initializr 创建 Spring Boot 新项目时&#xff0c;没有 Java 8 的选项了&#xff0c;只剩下了 > 17 的版本 是因为 Spring Boot 官方不再支持 Spring Boot 的 2.x 版本了&#xff0c;之后全力维护 3.x&#xff1b;而 …...

分享一个 ASP.NET Web Api 上传和读取 Excel的方案

前言 许多业务场景下需要处理和分析大量的数据&#xff0c;而 Excel 是业务人员常用的数据表格工具&#xff0c;因此&#xff0c;将 Excel 表格中内容上传并读取到网站&#xff0c;是一个很常见的功能&#xff0c;目前有许多成熟的开源或者商业的第三方库&#xff0c;比如 NPO…...

【算法实战】每日一题:将某个序列中内的每个元素都设为相同的值的最短次数(差分数组解法,附概念理解以及实战操作)

题目 将某个序列中内的每个元素都设为相同的值的最短次数 1.差分数组&#xff08;后面的减去前面的值存储的位置可以理解为中间&#xff09; 差分数组用于处理序列中的区间更新和查询问题。它存储序列中相邻元素之间的差值&#xff0c;而不是直接存储每个元素的值 怎么对某…...

EXCEL数据透视图中的日期字段,怎样自动分出年、季度、月的功能?

在excel里&#xff0c;这个果然是有个设置的地方&#xff0c;修改后就好了。 点击文件选项卡&#xff0c;选项&#xff0c;在高级里&#xff0c;将图示选项的勾选给取消&#xff0c;然后再创建数据透视表或透视图&#xff0c;日期就不会自动组合了&#xff1a; 这个选项只对新…...

【设计模式深度剖析】【1】【行为型】【模板方法模式】| 以烹饪过程为例加深理解

&#x1f448;️上一篇:结构型设计模式对比 文章目录 模板方法模式定义英文原话直译如何理解呢&#xff1f; 2个角色类图代码示例 应用优点缺点使用场景 示例解析&#xff1a;以烹饪过程为例类图代码示例 模板方法模式 模板方法模式&#xff08;Template Method Pattern&…...

JAVA:异步任务处理类CompletableFuture让性能提升一倍

一、前言 CompletableFuture 是 Java 8 引入的一个功能强大的类&#xff0c;用于异步编程。它表示一个可能尚未完成的计算的结果&#xff0c;你可以对其添加回调函数来在计算完成时执行某些操作。在 Spring Boot 应用中&#xff0c;CompletableFuture 可以用于提高应用的响应性…...

10Linux 进程管理学习笔记

Linux 进程管理 目录 文章目录 Linux 进程管理一.进程1.显示当前进程状态(ps)进程树(pstree)1.1实时显示进程信息(top)顶部概览信息&#xff1a;CPU 状态&#xff1a;内存状态&#xff1a;进程信息表头&#xff1a;进程列表&#xff1a;1.2(htop) 2.终止进程(kill)2.1通过名称…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

游戏开发中常见的战斗数值英文缩写对照表

游戏开发中常见的战斗数值英文缩写对照表 基础属性&#xff08;Basic Attributes&#xff09; 缩写英文全称中文释义常见使用场景HPHit Points / Health Points生命值角色生存状态MPMana Points / Magic Points魔法值技能释放资源SPStamina Points体力值动作消耗资源APAction…...

Yolo11改进策略:Block改进|FCM,特征互补映射模块|AAAI 2025|即插即用

1 论文信息 FBRT-YOLO&#xff08;Faster and Better for Real-Time Aerial Image Detection&#xff09;是由北京理工大学团队提出的专用于航拍图像实时目标检测的创新框架&#xff0c;发表于AAAI 2025。论文针对航拍场景中小目标检测的核心难题展开研究&#xff0c;重点解决…...

持续交付的进化:从DevOps到AI驱动的IT新动能

文章目录 一、持续交付的本质&#xff1a;从手动到自动的交付飞跃关键特性案例&#xff1a;电商平台的高效部署 二、持续交付的演进&#xff1a;从CI到AI驱动的未来发展历程 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/101f72defaf3493ba0ba376bf09367a2.png)中国…...

记一次spark在docker本地启动报错

1&#xff0c;背景 在docker中部署spark服务和调用spark服务的微服务&#xff0c;微服务之间通过fegin调用 2&#xff0c;问题&#xff0c;docker容器中服务器来后&#xff0c;注册中心都有&#xff0c;调用服务也正常&#xff0c;但是调用spark启动任务后报错&#xff0c;报错…...