C++数据结构之——链表

红目香薰

发布于 2025-02-06 08:15:36

9500

代码可运行

文章被收录于专栏：CSDNToQQCodeCSDNToQQCode

运行总次数：0

代码可运行

重难点声明

动态内存分配与释放
循环引用问题的处理
链表与数组的区别

概述

链表是一种线性数据结构，由一系列节点组成，每个节点包含一个值和指向下一个节点的指针。其特点是通过指针实现动态扩展，无需预先分配内存空间。

背景介绍

链表最初用于模拟计算机中的内存管理，动态内存分配使得其成为高效的数据结构。在现代编程中，链表广泛应用于数据存储、缓存机制和算法实现中。

链表的基本概念与结构

单链表

单链表是一个节点序列，每个节点通过指针指向下一个节点。

struct Node {
    int data;
    Node* next;
};

示例代码：创建单链表

Node* head = nullptr;
head = (new Node){1};
if (head) {
    head->next = new Node(2);
}
if (head->next) {
    head->next->next = new Node(3);
}

双链表

双链表每个节点有两个指针，分别指向下一个和上一个节点。

struct Node {
    int data;
    Node* prev;
    Node* next;
};

示例代码：创建双链表

Node* head = nullptr;
head = (new Node){1, nullptr, nullptr};
if (head) {
    head->next = new Node(2, head, nullptr);
}
if (head->next) {
    head->next->prev = head;
    head->next->next = new Node(3, nullptr, head->next);
}

链表的操作与实现

插入操作

插入可分为空链表插入、尾插和中间插入。

示例代码：在链表末尾插入节点

void append(Node** headRef, const int data) {
    Node* newNode = new Node(data);
    if (*headRef == nullptr) {
        *headRef = newNode;
    } else {
        Node* last = *headRef;
        while (last->next != nullptr) {
            last = last->next;
        }
        last->next = newNode;
    }
}

删除操作

删除可分为空链表删除、尾节点删除和指定节点删除。

示例代码：删除链表末尾节点

void deleteEnd(Node** headRef) {
    if (*headRef == nullptr) return;

    Node* last = *headRef;
    while (last->next != nullptr) {
        last = last->next;
    }
    if (last == *headRef) {
        *headRef = nullptr;
    } else {
        last->next = nullptr;
    }
}

遍历操作

遍历时从头节点开始，逐个访问每个节点。

示例代码：链表遍历

void traverse(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        std::cout << "Node value: " << current->data << std::endl;
        current = current->next;
    }
}

高级链表操作

循环链表

最后一个节点的指针指向头节点，形成循环。

示例代码：创建循环链表

Node* head = nullptr;

void makeCycle(Node** headRef) {
    if (*headRef == nullptr) return;

    Node* new_node = (new Node){2};
    Node* last = *headRef;
    last->next = new_node;
    new_node.prev = last;
    while (new_node->next != nullptr) {
        new_node = new_node->next;
    }
    new_node.next = *headRef;
}

多层链表

多层链表使用不同的指针类型，如前向、反向和双向。

示例代码：创建前向多层链表

struct Node {
    int data;
    Node* forward;
    Node* backward;
};

应用场景

数据存储

链表用于实现堆栈、队列等数据结构，适合线性遍历操作。

缓存机制

链表实现LRU缓存算法，记录访问顺序以优化页面交换策略。

线程安全

在高并发场景中使用链表结构，结合互斥锁机制确保线程安全。

总结

链表是一种灵活的动态数据结构，在内存管理、缓存设计和算法实现中具有广泛应用。通过合理选择插入、删除和遍历操作，可以高效解决问题。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-05，如有侵权请联系 cloudcommunity@tencent.com 删除

指针

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度