链表：单链表、双链表和循环链表

一、什么是链表

通过「指针」串联起来的内存空间。如图下链表概念图，有 3 个字符串存储在一个链表中，每个数据都有一个指针指向下一个数据的内存地址。

二、优缺点

• 优点：插入和删除高效，时间复杂度为 O(1)。
• 缺点：查询低效，时间复杂度为 O(n)。

插入数据和删除数据操作都是改变一下指针方向便可。

查找数据低效是因为要从第 1 个数据开始顺着指针寻找。比如说要查询「Red」，那么就得从「Blue」开始，通过指针指向的内存地址找到「Yellow」，然后才能找到「Red」。

三、3 种常用链表结构

• 单链表：头结点是记录链表的基地址，尾结点是指向 NULL。

• 双链表：两个空间存储前后结点地址，能双向遍历。但因为指针的增加导致存储空间增加，增删操作需要改变更多指针的指向。

• 循环链表：尾结点指向头结点，适合处理环形结构的数据。

四、例子

LeetCode 上的一个例子：删除链表中的节点。假设我们要删除「Yellow」这个结点，时间和空间复杂度都是：O(1)。

class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

1、首先我们把「Yellow」的值（node.next.val）赋值给「Green」（node.val）。

2、这时「Green」因为得到了「Yellow」的值，所以能修改方向指向结点「Red」。

3、最后链表变成了：「Blue」->「Green」->「Red」。