链表(linked_list)的理解以及实现

devtools/2024/10/19 7:29:48/

链表的概念：

链表是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。 

可以看出：链表物理结构不是连续的

链表与数组：

链表(带头双向循环链表)与数组(顺序表)在功能，结构上的不同：

数组链表
存储方式连续内存空间分散内存空间
容量扩展长度不可变可灵活扩展
内存效率元素占用内存少、但可能浪费空间元素占用内存多
访问元素O(1)O(n)
添加元素O(n)O(1)
删除元素O(n)O(1)

链表的分类：

类型分类：

  • 单链表（Singly Linked List）:

   - 每个节点包含数据和指向下一个节点的指针。

   - 单向链表，只能从表头向表尾遍历。

  • 双链表（Doubly Linked List）:

   - 每个节点包含数据和两个指针，分别指向前一个节点和后一个节点。

   - 双向链表，可以从任一节点开始向前或向后遍历。

  • 循环链表（Circular Linked List）:

   - 单链表或双链表的变体，最后一个节点的指针指向表头或前一个节点。

   - 循环单链表：最后一个节点指向表头。

   - 循环双链表：最后一个节点的后指针指向表头，表头的前指针指向最后一个节点。

  • 双向循环链表（Doubly Circular Linked List）:

   - 双链表的循环版本，第一个节点的前指针和最后一个节点的后指针都指向表头。

  • 栈式链表（Stack Implementation Using Linked List）:

   - 使用链表实现的栈，遵循后进先出（LIFO）原则。

   - 通常使用单链表实现，新元素总是添加到链表的头部。

  • 队列式链表（Queue Implementation Using Linked List）:

   - 使用链表实现的队列，遵循先进先出（FIFO）原则。

   - 通常使用双链表实现，新元素添加到链表的尾部，移除元素从头部。

  • 有序链表（Ordered Linked List）:

   - 链表中的节点按照特定的顺序（如数值大小）进行排序。

  • 无序链表（Unordered Linked List）:

   - 链表中的节点没有特定的顺序。

  • 动态链表（Dynamic Linked List）:

   - 可以在运行时动态地添加或删除节点。

  • 静态链表（Static Linked List）:

    - 节点的数量在创建时就固定了，不能动态地添加或删除节点。

  • 哈希链表（Hash Linked List）:

    - 哈希表的实现方式之一，通过链表解决哈希冲突。

  • 索引链表（Indexed Linked List）:

    - 链表中包含指向特定节点的索引，可以快速访问链表中的元素。

结构分类：

其中：较为常见的整体结构还是单向，环形，双向连表：

 

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

 

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

实现图解：

在实现链表的过程中，主要还是还是数据得插入删除

插入：

删除： 

单链表的实现：

在此主要实现带头单向不循环链表

在这里，带头带的其实就是哨兵位，哨兵位是一种特殊的节点，通常被添加到链表的开始或末尾，以简化某些操作，比如避免对空链表的特殊情况处理。哨兵节点通常不存储有效的数据，或者存储一个默认值

#include <iostream>
#include <stdexcept> // 用于抛出异常// 定义节点模板结构体
template <typename T>
struct Node {T data; // 存储数据Node<T>* next; // 指向下一个节点的指针// 构造函数Node(T val = T()): data(val), next(nullptr){}
};// 定义带头结点的单向不循环链表类
template <typename T>
class LinkedListWithHead {
private:Node<T>* head; // 头结点，哨兵节点public:// 构造函数LinkedListWithHead(){head = new Node<T>(); // 创建哨兵节点}// 析构函数~LinkedListWithHead(){Node<T>* current = head->next;while (current != nullptr){Node<T>* next = current->next;delete current;current = next;}delete head; // 释放哨兵节点}// 在链表末尾添加新节点void append(const T& value){Node<T>* newNode = new Node<T>(value);Node<T>* last = head;while (last->next != nullptr){last = last->next;}last->next = newNode;}// 在链表头部添加新节点void prepend(const T& value){Node<T>* newNode = new Node<T>(value);newNode->next = head->next;head->next = newNode;}// 根据值删除节点void remove(const T& value){Node<T>* current = head;while (current->next != nullptr && current->next->data != value){current = current->next;}if (current->next != nullptr){Node<T>* toDelete = current->next;current->next = current->next->next;delete toDelete;}else{throw std::runtime_error("Value not found in the list.");}}// 查找节点是否存在bool contains(const T& value) const{Node<T>* current = head->next;while (current != nullptr){if (current->data == value){return true;}current = current->next;}return false;}// 打印链表中的所有元素void print() const{Node<T>* current = head->next;while (current != nullptr){std::cout << current->data << " -> ";current = current->next;}std::cout << "null" << std::endl;}
};
  • remove 方法：删除链表中第一个匹配值的节点。如果找不到该值，则抛出一个 std::runtime_error 异常。
  • contains 方法：检查链表中是否存在具有给定值的节点，并返回一个布尔值。

请注意，remove 方法中，我们首先遍历链表直到找到要删除的节点。如果找到，我们将其从链表中移除并释放内存。如果链表中没有该值，我们抛出一个异常。contains 方法则是遍历链表检查是否存在具有给定值的节点。

双向链表的实现：

在此主要实现带头双向循环链表：

实现一个带头结点的双向循环链表涉及到创建一个链表，其中每个节点除了包含数据外，还有两个指针分别指向前一个节点和后一个节点。头结点是一个哨兵节点，它的 next 和 prev 指针都指向链表的第一个实际数据节点，而链表的最后一个数据节点的 next 指向头结点，prev 指向最后一个数据节点自身。

下面是C++模板实现带头结点的双向循环链表的示例代码：

#pragma once
#include <iostream>
#include <stdexcept> // 用于抛出异常// 定义节点模板结构体
template <typename T>
struct Node {T data;Node<T>* prev;Node<T>* next;// 构造函数，为data提供默认参数值Node(T val = T()) : data(val), prev(nullptr), next(nullptr) {}
};// 定义带头结点的双向循环链表类
template <typename T>
class CircularDoublyLinkedList {
private:Node<T>* head; // 头结点，哨兵节点public:// 构造函数CircularDoublyLinkedList() {head = new Node<T>(); // 创建哨兵节点head->next = head->prev = head; // 哨兵节点形成循环}// 析构函数~CircularDoublyLinkedList() {Node<T>* current = head->next;while (current != head) {Node<T>* temp = current;current = current->next;delete temp;}delete head; // 释放哨兵节点}// 在链表末尾添加新节点void append(const T& value) {Node<T>* newNode = new Node<T>(value);newNode->prev = head->prev;newNode->next = head;head->prev->next = newNode;head->prev = newNode;}// 删除链表中的指定节点void remove(Node<T>* node) {if (node == head) {head = head->next; // 哨兵节点指向下一个节点}node->prev->next = node->next;node->next->prev = node->prev;delete node;}// 打印链表中的所有元素void print() const {Node<T>* current = head->next;if (head->next == head) {std::cout << "List is empty." << std::endl;return;}do {std::cout << current->data << " ";current = current->next;} while (current != head->next);std::cout << std::endl;}// 根据值查找节点，如果找到则返回节点指针，否则返回nullptrNode<T>* find(const T& value) const {Node<T>* current = head->next;if (head->next == head) {return nullptr; // 链表为空}do {if (current->data == value) return current;current = current->next;} while (current != head->next);return nullptr;}// 根据值删除节点void removeByValue(const T& value) {Node<T>* nodeToDelete = find(value);if (nodeToDelete != nullptr) {remove(nodeToDelete);}}
};

在这个实现中，定义了 Node 结构体和 CircularDoublyLinkedList 类。CircularDoublyLinkedList 类包括添加节点到头部和末尾、删除节点、打印链表、查找节点以及根据值删除节点的方法。链表使用哨兵节点简化了头部和末尾的操作。

请注意，remove 方法接受一个 Node 指针作为参数，它将该节点从链表中移除并释放内存。removeByValue 方法使用 find 方法来查找具有给定值的节点，如果找到了就调用 remove 方法来删除它。


http://www.ppmy.cn/devtools/95081.html

相关文章

MySQL 管理

MySQL 管理

启动及关闭 MySQL 服务器 Windows 系统下 启动 MySQL 服务器&#xff1a; 1、通过 “服务” 管理工具&#xff1a; 打开“运行”对话框&#xff08;Win R&#xff09;&#xff0c;输入 services.msc&#xff0c;找到“MySQL”服务&#xff0c;右击选择“启动”。 2、通过命…
阅读更多...
绘唐科技为什么是全网最强AI推文应用

绘唐科技为什么是全网最强AI推文应用

绘唐科技之所以被称为全网最强AI推文应用&#xff0c;主要有以下几个原因&#xff1a; 绘唐AIGC阿祖https://qvfbz6lhqnd.feishu.cn/wiki/D3YLwmIzmivZ7BkDij6coVcbn7W 先进的AI技术&#xff1a;绘唐科技采用了最先进的自然语言处理和机器学习算法&#xff0c;能够快速准确地生…
阅读更多...
案例分享：Zabbix数据可视化在物联网监控领域的应用分享

案例分享：Zabbix数据可视化在物联网监控领域的应用分享

QU!CK Scan & Go(以下简称QU)是一家自助服务市场的初创公司&#xff0c;它需要一个能够全面了解并查看运营情况的监控系统&#xff0c;Zabbix为它们提供了一整套监控运维解决方案并对他们的运营和财务产生了积极的影响&#xff0c;极大降低财务成本&#xff0c;提升运营效能…
阅读更多...
星露谷模组开发教程#6 烹饪和制造配方

星露谷模组开发教程#6 烹饪和制造配方

首发于Enaium的个人博客 在上篇文章中我们添加了一个新的食物&#xff0c;但是这个食物并没有配方&#xff0c;所以我们今天来添加一个配方。 烹饪配方 我们在Data/CookingRecipes.json中可以看到所有的食物配方&#xff0c;所以我们需要修改这个配置文件来添加我们的食物配方…
阅读更多...
项目沟通的艺术：从素描中汲取灵感

项目沟通的艺术：从素描中汲取灵感

项目沟通的艺术&#xff1a;从素描中汲取灵感 前言观察与聚焦&#xff1a;确定沟通的核心勾勒轮廓&#xff1a;构建沟通结构一次只描述一个主题&#xff1a;保持沟通的清晰性填充细节&#xff1a;深化沟通内容反馈与调整&#xff1a;持续优化沟通结语 前言 在项目管理的世界里&…
阅读更多...
程序员的最爱，FRP实现无公网IP的内网穿透，搭建远程服务：http、ssh、samba，基于最新FRP0.59.0版本

程序员的最爱，FRP实现无公网IP的内网穿透，搭建远程服务：http、ssh、samba，基于最新FRP0.59.0版本

文章目录 一、前言二、FRP 内网穿透2.1 配置需求2.2 Github FRP2.3 外网aws配置(frps)2.3.1 frps 配置说明2.3.2 开放aws端口2.3.3 frps.toml2.3.4 运行frps2.4 内网主机配置(frpc)2.4.1 内网主机端口说明2.4.2 frpc 配置说明2.4.3 frpc.toml2.4.4 运行frpc2.5 ssh 连接测试2.5…
阅读更多...
探索Ubuntu网络监控：安装与使用流行工具的指南

探索Ubuntu网络监控：安装与使用流行工具的指南

网络监控工具对于系统管理员来说是不可或缺的&#xff0c;它们可以帮助监控网络流量、诊断问题并优化网络性能。Ubuntu提供了多种网络监控工具&#xff0c;从命令行工具到图形界面应用程序&#xff0c;应有尽有。本文将详细介绍在Ubuntu中安装和使用网络监控工具的过程。 一、…
阅读更多...
JavaScript 详解——Vue基础

JavaScript 详解——Vue基础

第一章 JavaScript简介 为什么学习javascript &#xff1f; JavaScript 是全球最流行的编程语言。 JavaScript 是属于 Web 的编程语言。 JavaScript 是 web 开发者必学的三种语言之一&#xff1a; HTML 定义网页的内容 CSS 规定网页的布局 JavaScript 对网页行为进行编程 …
阅读更多...
最新文章

Copyright @ 2022~2023