【最完整系列】JAVA-容器篇-LinkedList源码解析

简介

LinkedList 顾名思义其本质是一个链表，具体来说是一个双向链表，同时还有2个指针分别对应链表的头和尾。

源码

源码还是跟 ArrayList 一样，从我们常用的代码出发：

List<String> a = new LinkedList<>();
a.add("sidfate");

进入初始化源码：

// LinkedList 长度
transient int size = 0;

// 指向头结点
transient Node<E> first;

// 指向尾节点
transient Node<E> last;

public LinkedList() {
}

可以看到默认的构造函数空空如也，需要注意的是链表是以 Node 为基础连接起来的，Node 的结构如下：

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;
    }
}

Node 结构也很简单，prev 和 next 说明它是一个双向的链表，保存前后 Node 的指针。接下来进入 add 的过程：

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++;
}

简单来说，添加一个元素就是往链表尾插入一个新的 Node。那么如果是往链表中插入一个元素呢：

public void add(int index, E element) {
    // 检查index合法性
    checkPositionIndex(index);

    if (index == size)
        // 如果index就是尾部则直接添加
        linkLast(element);
    else
        // 在 index 所在的 Node 前插入
        linkBefore(element, node(index));
}

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

node 函数用来查找对应 index 的 Node 节点，比较有意思的是 2 将遍历降低成了链表长度的一半：

如果 index 在头和中点之间，那么就从头开始遍历到中点。
如果 index 在中点和尾之间，那么就从尾开始遍历到中点。

双向链表的优势就凸显出来的，相对而言插入的效率比 ArrayList 高，毕竟 ArrayList 需要拷贝 index 后的数组。但是查询效率就低了，ArrayList 根据下标能直接取出元素，而且因为是数组所以内存空间上是连续的，不像 LinkedList是根据指针串联，内存地址上可能是不连续的。

LinkedList 的还有个优势时它既能当队列也能当栈来使用。