C++链表详解：从基础概念到高级应用

embedded/2025/4/1 2:02:28/

C++链表详解：从基础概念到高级应用

链表是计算机科学中最基础也是最重要的数据结构之一，它在内存管理、算法实现和实际应用中扮演着关键角色。本文将详细介绍链表的概念、类型、C++实现以及实际应用场景，帮助读者全面理解这一重要的数据结构。

在这里插入图片描述

文章目录

  • C++链表详解：从基础概念到高级应用
    • 1. 链表的基本概念
    • 2. 链表的类型
    • 3. C++中的链表实现
    • 4. 链表的基本操作
      • 4.1 插入操作
      • 4.2 删除操作
      • 4.3 遍历操作
      • 4.4 搜索操作
    • 5. 链表的高级操作
      • 5.1 链表反转
      • 5.2 环检测
      • 5.3 查找中间节点
      • 5.4 合并有序链表
    • 6. 链表的实际应用
      • 6.1 音乐播放列表
      • 6.2 约瑟夫环问题
      • 6.3 多项式表示
      • 6.4 LRU缓存实现
    • 7. 链表与其他数据结构的比较
    • 8. 总结与进阶学习建议
    • 参考资料

1. 链表的基本概念

链表是一种线性数据结构，它由一系列节点组成，每个节点包含两个部分：数据部分和指针部分。与数组不同，链表中的元素在内存中不是连续存储的，而是通过指针连接在一起。这种结构允许在不移动其他元素的情况下进行高效的插入和删除操作。

在这里插入图片描述

如上图所示，链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的第一个节点称为头节点（HEAD），最后一个节点的指针指向NULL，表示链表的结束。

链表的核心特点

  1. 动态数据结构：链表可以根据需要动态增长和缩小，不需要预先分配固定大小的内存。

  2. 非连续内存分配：链表中的节点可以存储在内存的任何位置，通过指针相互连接。

  3. 插入和删除效率高：在已知位置插入或删除节点的时间复杂度为O(1)，而不需要像数组那样移动其他元素。

  4. 随机访问效率低：访问链表中的第n个元素需要从头开始遍历，时间复杂度为O(n)。

  5. 额外的内存开销：每个节点除了存储数据外，还需要存储指向其他节点的指针。

2. 链表的类型

链表根据节点之间的连接方式，可以分为四种主要类型：单向链表、双向链表、循环链表和双向循环链表。

2.1 单向链表

单向链表是最基本的链表形式，每个节点包含数据和一个指向下一个节点的指针。链表的最后一个节点的指针指向NULL，表示链表的结束。

在这里插入图片描述

特点：

  • 只能从头到尾遍历
  • 每个节点只有一个指针
  • 只能访问当前节点的下一个节点
  • 内存开销较小

C++节点定义：

struct Node {int data;       // 数据域，存储节点的值Node* next;     // 指针域，指向下一个节点
};

2.2 双向链表

双向链表中的每个节点包含数据和两个指针：一个指向前一个节点，一个指向后一个节点。链表的第一个节点的prev指针和最后一个节点的next指针都指向NULL。

特点：

  • 可以双向遍历（从头到尾或从尾到头）
  • 每个节点有两个指针
  • 可以访问当前节点的前一个和后一个节点
  • 内存开销较大
  • 插入和删除操作更灵活

结构示意图：

NULL ← [prev|数据|next] ⇄ [prev|数据|next] ⇄ [prev|数据|next] → NULL↑head

C++节点定义：

struct Node {int data;       // 数据域，存储节点的值Node* prev;     // 前驱指针，指向前一个节点Node* next;     // 后继指针，指向后一个节点
};

2.3 循环链表

循环链表是单向链表的变体，其中最后一个节点的指针不是指向NULL，而是指向链表的第一个节点，形成一个环。

特点：

  • 没有明确的结束点
  • 可以从任何节点开始遍历整个链表
  • 适用于需要循环处理的场景，如轮询调度

结构示意图：

    ┌───────────────────────────┐↓                           |
head → [数据|next] → [数据|next] → [数据|next]

C++节点定义：

struct Node {int data;       // 数据域，存储节点的值Node* next;     // 指针域，指向下一个节点
};

2.4 双向循环链表

双向循环链表结合了双向链表和循环链表的特点。第一个节点的prev指针指向最后一个节点，最后一个节点的next指针指向第一个节点。

特点：

  • 可以双向循环遍历
  • 每个节点都可以访问其前一个和后一个节点
  • 没有明确的开始和结束点
  • 内存开销最大
  • 最灵活的链表结构

结构示意图：

    ┌─────────────────────────────────────┐|                                     |↓                                     ↑
[prev|数据|next] ⇄ [prev|数据|next] ⇄ [prev|数据|next]↑                                     |└─────────────────────────────────────┘

C++节点定义：

struct Node {int data;       // 数据域，存储节点的值Node* prev;     // 前驱指针，指向前一个节点Node* next;     // 后继指针，指向后一个节点
};

3. C++中的链表实现

在C++中，我们可以使用结构体或类来实现链表。下面将详细介绍各种链表的C++实现。

3.1 节点结构定义

链表的基本组成单位是节点，我们首先需要定义节点的结构：

// 单向链表节点结构
struct Node {int data;       // 数据域，存储节点的值Node* next;     // 指针域，指向下一个节点// 默认构造函数Node() : data(0), next(nullptr) {}// 带参数的构造函数Node(int val) : data(val), next(nullptr) {}
};// 双向链表节点结构
struct DNode {int data;       // 数据域，存储节点的值DNode* prev;    // 前驱指针，指向前一个节点DNode* next;    // 后继指针，指向后一个节点// 默认构造函数DNode() : data(0), prev(nullptr), next(nullptr) {}// 带参数的构造函数DNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};

3.2 单向链表实现

下面是一个完整的单向链表类实现，包括常见的操作如插入、删除、遍历等：

// 单向链表类
class SinglyLinkedList {
private:Node* head;     // 头指针，指向链表的第一个节点public:// 构造函数SinglyLinkedList() : head(nullptr) {}// 析构函数，释放所有节点内存~SinglyLinkedList() {Node* current = head;while (current != nullptr) {Node* temp = current;current = current->next;delete temp;}head = nullptr;}// 在链表头部插入节点void insertAtHead(int value) {// 创建新节点Node* newNode = new Node(value);// 如果链表为空，新节点就是头节点if (head == nullptr) {head = newNode;return;}// 否则，将新节点插入到头部newNode->next = head;head = newNode;}// 在链表尾部插入节点void insertAtTail(int value) {// 创建新节点Node* newNode = new Node(value);// 如果链表为空，新节点就是头节点if (head == nullptr) {head = newNode;return;}// 找到链表的最后一个节点Node* current = head;while (current->next != nullptr) {current = current->next;}// 将新节点连接到最后一个节点current->next = newNode;}// 在指定位置插入节点void insertAtPosition(int position, int value) {// 如果位置为0，相当于在头部插入if (position == 0) {insertAtHead(value);return;}// 创建新节点Node* newNode = new Node(value);// 找到要插入位置的前一个节点Node* current = head;for (int i = 0; i < position - 1 && current != nullptr; i++) {current = current->next;}// 如果位置超出链表长度，或链表为空if (current == nullptr) {std::cout << "位置无效" << std::endl;delete newNode;return;}// 插入新节点newNode->next = current->next;current->next = newNode;}// 删除头部节点void deleteFromHead() {// 如果链表为空，无法删除if (head == nullptr) {std::cout << "链表为空，无法删除" << std::endl;return;}// 保存头节点Node* temp = head;// 更新头指针head = head->next;// 释放原头节点的内存delete temp;}// 删除尾部节点void deleteFromTail() {// 如果链表为空，无法删除if (head == nullptr) {std::cout << "链表为空，无法删除" << std::endl;return;}// 如果链表只有一个节点if (head->next == nullptr) {delete head;head = nullptr;return;}// 找到倒数第二个节点Node* current = head;while (current->next->next != nullptr) {current = current->next;}// 删除最后一个节点delete current->next;current->next = nullptr;}// 删除指定位置的节点void deleteFromPosition(int position) {// 如果链表为空，无法删除if (head == nullptr) {std::cout << "链表为空，无法删除" << std::endl;return;}// 如果要删除头节点if (position == 0) {deleteFromHead();return;}// 找到要删除位置的前一个节点Node* current = head;for (int i = 0; i < position - 1 && current != nullptr && current->next != nullptr; i++) {current = current->next;}// 如果位置无效if (current == nullptr || current->next == nullptr) {std::cout << "位置无效" << std::endl;return;}// 保存要删除的节点Node* temp = current->next;// 更新链接current->next = temp->next;// 释放节点内存delete temp;}// 打印链表void display() {Node* current = head;if (current == nullptr) {std::cout << "链表为空" << std::endl;return;}std::cout << "链表内容: ";while (current != nullptr) {std::cout << current->data << " -> ";current = current->next

http://www.ppmy.cn/embedded/177611.html

相关文章

Selenium测试框架快速搭建

Selenium测试框架快速搭建

一、介绍 Selenium目前主流的web自动化测试框架&#xff1b;支持多种编程语言Java、pythan、go、js等&#xff1b;selenium 提供一系列的api 供我们使用&#xff0c;因此在web测试时我们要点页面中的某一个按钮&#xff0c;那么我们只需要获取页面&#xff0c;然后根据id或者n…
阅读更多...
MYTOOL-记事本

MYTOOL-记事本

一、前言 目录 1.原型设计 2.程序实现 3.最终界面说明 二、环境 windows10 每个软件工具前期会设计大概的原型&#xff0c;我设计的原型工具使用Axure RP9&#xff0c;很不错的一个设计工具 三、正文 1.原型设计 2.程序实现 3.最终界面说明 四、结语
阅读更多...
【Linux】深度解析Linux进程间通信：匿名管道原理、实战进程池与高频问题排查。

【Linux】深度解析Linux进程间通信：匿名管道原理、实战进程池与高频问题排查。

命名管道在下一篇进行讲解&#xff1a; 【Linux】深入解析Linux命名管道&#xff08;FIFO&#xff09;&#xff1a;原理、实现与实战应用-CSDN博客 deepseek总结全文 1. 进程间通信&#xff08;IPC&#xff09;的核心目的 数据传输&#xff1a;进程间交换数据。 资源共享&…
阅读更多...
探索高性能 Web 服务的未来 —— Hyperlane 框架

探索高性能 Web 服务的未来 —— Hyperlane 框架

在当今高并发、低延时的 Web 服务开发中&#xff0c;高性能、轻量级的 HTTP 服务器成为关键竞争力。Hyperlane 框架 基于 Rust 开发&#xff0c;充分利用 Rust 的内存安全和高效运行时&#xff0c;提供了灵活、易扩展且性能卓越的 HTTP 服务器解决方案。无论是构建 API 网关、实…
阅读更多...
第P8周：YOLOv5-C3模块实现

第P8周：YOLOv5-C3模块实现

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 &#x1f680;我的环境&#xff1a; 语言环境&#xff1a;python 3.12.6编译器&#xff1a;jupyter lab深度学习环境&#xff1a;Pytorch 前期准备 import…
阅读更多...
每天认识一个设计模式-桥接模式：在抽象与实现的平行宇宙架起彩虹桥

每天认识一个设计模式-桥接模式：在抽象与实现的平行宇宙架起彩虹桥

一、前言&#xff1a;虚拟机桥接的启示 使用过VMware或者Docker的同学们应该都接触过网络桥接&#xff0c;在虚拟机网络配置里&#xff0c;桥接模式是常用的网络连接方式。选择桥接模式时&#xff0c;虚拟机会通过虚拟交换机与物理网卡相连&#xff0c;获取同网段 IP 地址&…
阅读更多...
【PySpark大数据分析概述】01 大数据分析概述

【PySpark大数据分析概述】01 大数据分析概述

【作者主页】Francek Chen 【专栏介绍】 ⌈ ⌈ ⌈PySpark大数据分析与应用 ⌋ ⌋ ⌋ PySpark作为Apache Spark的Python API&#xff0c;融合Python易用性与Spark分布式计算能力&#xff0c;专为大规模数据处理设计。支持批处理、流计算、机器学习 (MLlib) 和图计算 (GraphX)&am…
阅读更多...
Pyside6介绍和开发第一个程序

Pyside6介绍和开发第一个程序

Pyside6介绍 PySide6 是一个用于创建 图形用户界面&#xff08;GUI&#xff09; 的 Python 库&#xff0c;它是 Qt 框架的官方 Python 绑定。Qt 是一个功能强大的跨平台 C 框架&#xff0c;广泛用于开发桌面应用程序、移动应用程序和嵌入式系统。PySide6 允许开发者使用 Pytho…
阅读更多...
最新文章

Copyright @ 2022~2023