链式实现

1. 单链表

头节点

一般通过头指针来表示一个链表
在链表的头部增加一个头节点，头节点不存储数据

/* 链表节点的定义 */
struct Node {
    int val = 0;
    Node *next = nullptr;
};
/* 使用头指针来表示一个链表 */
typedef Node *LinkList;
LinkList list1 = new Node();     // 这里创建了一个空的头节点

使用头节点的好处：

• 可以统一空链表和非空链表的处理
• 可以统一头节点和一般节点的处理

在头部插入节点时，使用头节点和不使用头节点的区别：
注意到：

• 不使用头节点时，操作有些怪异
• 不使用头节点时，需要传头指针的引用进去（我更希望保持头指针不变） ```cpp / 使用头节点 / void insert(LinkList list, int value) { Node *node = new Node(); node->val = value; node->next = list->next; list->next = node; }

/ 不使用头节点 / void insert(LinkList &list, int value) { Node *node = new Node(); node->value = value; node->next = list; // 这两句感觉挺怪的 list = node; } ```

前插操作

已知单链表的一个节点，想要在该节点之前插入另一个节点

方法1: 找到前驱节点
从链表头部开始，找到该节点的前驱节点，然后将元素插入到前驱节点的后面，时间复杂度为：

方法2: 在后方插入，并交换内容
将元素插入到该节点的后面，然后调换两个节点的值，时间复杂度为：

删除操作

已知某个节点 *p，想要删除这个节点。
和前插类似，也有两种方法

方法1: 找到这个节点的前驱节点，然后执行删除操作，时间复杂度：

方法2: 将后继节点的值赋值给当前节点，然后删除后继节点，时间复杂度为：

注：如果要删除的节点是最后一个节点，由于需要将前驱节点的 next 置为 NULL，时间复杂度只能是：

2. 双链表

双链表也可以有头节点，同样可以简化操作

3. 循环单链表

使用头节点的循环单链表情形：

使用尾指针的好处：
由于是单链表，如果使用头指针，那么在尾部插入的时间复杂度就是；使用尾指针可以让头部插入和尾部插入的时间复杂度都是

判断循环单链表是否空：头节点的后继是否是头节点

4. 循环双链表

。。。

5. 静态链表

借助数组来描述链表的静态结构：