代码随想录

C++ 算法编程指南

仅作个人学习笔记使用,读者如需详细深入学习,请点击上方链接

1. 链表的概念

注意一下相关名词,还有链表的特点。

链表采用链式存储结构来实现线性表。

  • 特点:
    • 每一个元素都至多有一个唯一确定的前驱,也至多有一个唯一确定的后继;
    • 链表中的元素在实际的物理存储上并不要求一个接一个存放,链表可以在任意内存位置随意存放各个元素。

为了维持元素之间逻辑上的前驱后继关系,链表为每一个元素附加上表示其前后关系的指针,

  • 前链:指向前驱元素的指针

  • 后链:指向后继元素的指针

  • 元素的值和它的前后链组合在一起形成一个元素节点,简称节点

  • 节点才是链表的基本存储单元,所有元素的节点通过前后链串接起来形成链表。

  • 单链表:链表中的每一个元素节点都只有一个后链

  • 双链表:每一个元素节点同时有一个后链和一个前链

示例:有一个整数序列[1,2,3],其物理地址可以存放在内存的任意位置,通过链来维持前后关系。(双链表中:红色为后链,蓝色为前链)

../../_images/317_linkedlist_mem.png

1.1 链表的定义

  • 单链表的定义:

    1
    2
    3
    4
    5
    6
    struct Node {
    int value; // 元素值
    Node *next; // 后链指针

    Node(int val = 0) { value = val; next = NULL; } // 构造函数
    };
  • 如果希望让链表能像STL库的那些容器一样,可以支持任意数据类型,那么可以将节点定义为模板结构,比如下面这个双向链表节点的结构

    1
    2
    3
    4
    5
    6
    7
    8
    9
    template <typename T>
    struct Node {
    T value; // 元素值
    Node *next; // 后链指针
    Node *prev; // 前链指针

    Node() { next = NULL; prev = NULL; } // 默认构造函数
    Node(const T &val) { value = val; next = NULL; prev = NULL; } // 指定元素值的构造函数
    };

1.2 头指针、尾指针

链表只能沿着链的方向迭代遍历节点,无法根据下标直接访问指定位置上的元素,需要按下标访问时要从头节点开始逐个向后寻找,这是一个线性时间 𝑂(𝑛) 的操作。

因此,我们需要告诉链表链表头和链表尾在哪里,自然而然的出现了“头指针(head)”和“尾指针(tail)

../../_images/317_linkedlist_2.png

1.3 循环链表

挺好理解的,就是首尾相连

  • 循环单链表中尾节点的后继不再是空指针而是指向头指针
  • 循环双链表中尾节点的后继指向头节点,头节点的前驱指向尾节点。
  • 这样一来,表被改造成了一个环,
  • 从而也就没有了严格意义上的头尾节点,所以这种循环链表中我们通常会用一个当前指针(current)来代替原来的头尾指针。

2. 元素的插入与删除

链表最大的优势是可以实现常数时间 𝑂(1) 的元素增删操作。

代码操作看这里:链表的C++实现

插入

向链表中指定位置插入一个元素的操作如下图:

../../_images/317_linkedlist_ins.png

删除

../../_images/317_linkedlist_era.png


© 2024 Montee | Powered by Hexo | Theme stellar


Static Badge