代码随想录

C++ 算法编程指南

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

1. 链表的概念

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

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

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

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

前链：指向前驱元素的指针
后链：指向后继元素的指针
元素的值和它的前后链组合在一起形成一个元素节点，简称节点
节点才是链表的基本存储单元，所有元素的节点通过前后链串接起来形成链表。
单链表：链表中的每一个元素节点都只有一个后链
双链表：每一个元素节点同时有一个后链和一个前链

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

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

1.1 链表的定义

单链表的定义：

struct Node {
        int value;   // 元素值
        Node *next;  // 后链指针

        Node(int val = 0) { value = val; next = NULL; } // 构造函数
};

如果希望让链表能像STL库的那些容器一样，可以支持任意数据类型，那么可以将节点定义为模板结构，比如下面这个双向链表节点的结构

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

链表基础知识