数据结构系列之链表（Java）

leetcode链表专题

链表分别都对应了那些Java类？

java.util.ArrayList
java.util.LinkedList
java.util.concurrent.CopyOnWriteArrayList

单向链表

单向链表包含两个域：

信息域（上图的data，存放结点数据）
指针域（上图的next，链接指向列表中的下一个结点，而最后一个结点则指向一个空值）

每个结点只有一个指针的链表也叫单向链表，或者单链表。

在链表表头插入新结点

此时只需要变更Head的指向。

在链表中间插入新结点

此时需要变更front node的next值，将其指向new node，new node的next值指向next node。

带头结点和尾结点的单链表

在不带头结点的单链表中，插入和删除都需要区分操作的结点下标，在链表表头插入新结点与在链表中间插入新结点是不同的。
而在带头结点的单链表中，就不再需要做这样的区分。
在带头结点的链表表头插入新结点：

在带头结点的链表中间插入新结点：

上面操作都是变更front node的next值，将其指向new node，new node的next值指向next node。
删除结点同理。

尾部插入

为了使链表在尾部插入时也和上面的头部、中间插入一直，以及达到更加高效，可在链表增加一个尾部指向的尾结点，这样一来，在尾部添加结点时，只要通过尾结点直接操作即可，无需从表头遍历到表尾。

如上图，通过尾结点可能快速定位到front node，然后操作依然是变更front node的next值，将其指向new node，new node的next值指向next node（尾结点）。

这样一来，头部、中间和尾部插入就可以视为同一种操作逻辑了。

循环单链表

循环链表在实现遍历的时候要注意避免死循环，判断遍历到尾结点即可停止。

单链表 vs 顺序表

由于不必须按顺序存储，链表在插入的时候可以达到 O(1) 的复杂度，比另一种线性表 —— 顺序表快得多，但是查找一个结点或者访问特定编号的结点则需要 O(n) 的时间，而顺序表相应的时间复杂度分别是 O(log n) 和 O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串结点组成，每个结点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个结点的位置的链接（links）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。

来源：https://leetcode-cn.com/tag/linked-list/

单链表的弊端

指针域中没有前驱指针，无法知道前驱结点，假如指针this指向某个结点，想要在this的前面插入一个结点或删除this所在结点时，必须从链表的表头遍历至this的前一个结点再执行插入或者删除操作，这种情况使用双链表就更为高效了。

双向链表

信息域（存放结点数据）
指针域（有两个链接）
- 前链接：指向前一个结点，当此“前链接”为第一个时，指向空值或者空列表；
- 后链接：指向下一个结点，当此“后连接”为最后一个时，指向空值或者空列表；

双向链表也叫双链表。双链表可以从任何一个结点访问前一个结点，当然也可以访问后一个结点，

java.util.LinkedList双链表的实现逻辑

分析java.util.LinkedList的源码可以发现有成员变量transient Node<E> first;和transient Node<E> last;。

初始化状态：

java.util.LinkedList插入数据的代码：

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}