本文介绍: 内存空间是所有程序公共资源,在一个复杂系统运行环境下,空闲内存空间可能散落在内存各处。我们知道存储数组内存空间必须是连续的,而当数组非常大时,内存可能无法提供如此大的连续空间。此时链表的灵活性优势就体现出来了。链表(linked list)是一种线性数据结构,其中的每个元素都是一个节点对象各个节点通过引用”相连接引用记录了下一个节点的内存地址通过可以当前节点访问到下一个节点。链表设计使得各个节点可以被分散存储在内存各处,它们的内存地址是无须连续的。

内存空间是所有程序公共资源,在一个复杂系统运行环境下,空闲的内存空间可能散落在内存各处。我们知道存储数组的内存空间必须是连续的,而当数组非常大时,内存可能无法提供如此大的连续空间。此时链表的灵活性优势就体现出来了。

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

链表的设计使得各个节点可以被分散存储在内存各处,它们的内存地址是无须连续的。

观察上图 ,链表的组成单位是节点 (node)对象。每个节点都包含两项数据:节点的“值”和指向一节点的“引用”。

 如以下代码所示,链表节点 ListNode 除了包含值,还需额外保存一个引用(指针)。因此在相同数据量下,链表比数组占用更多的内存空间

/* 链表节点结构体 */
struct ListNode {
    int val;         // 节点值
    ListNode *next;  // 指向一节点的指针
    ListNode(int x) : val(x), next(nullptr) {}  // 构造函数
};

5.1 链表常用操作

5.1.1 初始化链表

 建立链表分为两步,第一步初始化各个节点对象,第二步是构建引用指向关系初始化完成后,我们可以从链表的头节点出发,通过引用指向 next 依次访问所有节点。

/* 初始化链表 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各个节点
ListNode* n0 = new ListNode(1);
ListNode* n1 = new ListNode(3);
ListNode* n2 = new ListNode(2);
ListNode* n3 = new ListNode(5);
ListNode* n4 = new ListNode(4);
// 构建引用指向
n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;

数组整体是一个变量比如数组 nums 包含元素 nums[0] 和 nums[1] 等,而链表是由多个独立的节点对象组成的。我们通常将头节点当作链表的代称比如以上代码中的链表可被记做链表 n0 。

5.1.2 插入节点

在链表中插入节点非常容易。如下图所示假设我们想在相邻两个节点 n0 和 n1 之间插入一个新节点 P ,则只需要改变两个节点引用(指针即可时间复杂度为O(1)。

相比之下,在数组插入元素时间复杂度为O(n),在大数据量下的效率较低。

/* 在链表的节点 n0 之后插入节点 P */
void insert(ListNode *n0, ListNode *P) {
    ListNode *n1 = n0->next;
    P->next = n1;
    n0->next = P;
}

5.1.3 删除节点

下图所示,在链表中删除节点也非常方便,只需改变一个节点的引用(指针即可。请注意,尽管在删除操作完成后节点 P 仍然指向 n1 ,但实际上遍历此链表已经无法访问到 P ,这意味着 P 已经不再属于该链表了。

/* 删除链表的节点 n0 之后的首个节点 */
void remove(ListNode *n0) {
    if (n0->next == nullptr)
        return;
    // n0 -> P -> n1
    ListNode *P = n0->next;
    ListNode *n1 = P->next;
    n0->next = n1;
    // 释放内存
    delete P;
}

5.1.4 访问节点

在链表访问节点的效率较低。如上节所述,我们可以在 (O(1)) 时间下访问数组中的任意元素。链表则不然,程序需要从头节点出发,逐个向后遍历,直至找到目标节点。也就是说,访问链表的第 i个节点需要循环i – 1轮,时间复杂度为 O(n) 。

/* 访问链表中索引index 的节点 */
ListNode *access(ListNode *head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == nullptr)
            return nullptr;
        head = head->next;
    }
    return head;
}

5.1.5 查找节点

遍历链表,查找链表内值为 target 的节点,输出节点在链表中索引。此过程属于线性查找

/* 在链表中查找值为 target 的首个节点 */
int find(ListNode *head, int target) {
    int index = 0;
    while (head != nullptr) {
        if (head->val == target)
            return index;
        head = head->next;
        index++;
    }
    return -1;
}

5.2 数组 VS 链表

下表总结对比了数组和链表的各项特点与操作效率。由于它们采用两种相反的存储策略,因此各种性质和操作效率也呈现对立的特点。

5.3 常见链表类型

下图所示,常见的链表类型包括三种

  • 单向链表:即上述介绍的普通链表。单向链表的节点包含值和指向一节点的引用两项数据。我们将首个节点称为头节点,将最后一个节点称为尾节点,尾节点指向空 (text{None}) 。
  • 环形链表:如果我们令单向链表的尾节点指向头节点(即首尾相接),则得到一个环形链表。在环形链表中,任意节点都可以视作头节点。
  • 双向链表:与单向链表相比,双向链表记录两个方向的引用。双向链表的节点定义同时包含指向后继节点(下一个节点)和前驱节点(上一个节点)的引用(指针)。相较于单向链表,双向链表更具灵活性,可以朝两个方向遍历链表,但相应地也需要占用更多的内存空间
/* 双向链表节点结构体 */
struct ListNode {
    int val;         // 节点值
    ListNode *next;  // 指向后继节点的指针
    ListNode *prev;  // 指向前驱节点的指针
    ListNode(int x) : val(x), next(nullptr), prev(nullptr) {}  // 构造函数
};

5.4 链表典型应用

单向链表通常用于实现栈、队列哈希表和图等数据结构

双向链表常被用于需要快速查找前一个和下一个元素场景

循环链表常被用于需要周期性操作场景比如操作系统的资源调度

原文地址:https://blog.csdn.net/zeyeqianli/article/details/134626785

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_22010.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除!

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注