LinkedList介绍

和ArrayList不同的是，ArrayList使用数组作为数据载体，而LinkedList使用双向链表的形式保存数据。种种数据结构适用于频繁添加和删除数据的场景，但是随机访问的性能不佳。

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的结构比较简单，其中item负责存储数据，还有next和prev两个引用类型，分别指向链表下一个和上一个节点。通过这两个指针，多个node串联在一起，形成了一个双向链表。

下图展示了LinkedList的结构：

LinkedList结构

LinkdedList的成员变量

成员变量的解释在代码注释中标出，如下所示：

// LinkedList中共有多少个节点（存了多少个元素）
transient int size = 0;

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
// 指向队首Node的指针
transient Node<E> first;

/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
// 指向队尾Node的指针
transient Node<E> last;

LinkedList的构造函数

除了无参数的构造函数外，LinkedList也支持使用另一个集合的元素构建新的LinkedList。下面我们分析下相关源码。

public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
    // 创建一个空的LinkedList
    this();
    // 把c的所有元素添加到LinkedList
    addAll(c);
}

这里的addAll方法又间接调用了里一个重载方法，表示在LinkedList的size这个index之后追加集合c的元素。

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

addAll方法源码解读放在后面的小节中。

LinkedList的重要方法

add(E e)方法

向LinkedList末尾添加一个元素。代码如下：

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

上面调用了linkLast方法，创建一个新的Node，添加在LinkedList末尾。

// 在双向链表末尾增加一个新的Node，包含元素e
void linkLast(E e) {
    // 获取链表最后一个Node
    final Node<E> l = last;
    创建一个新的Node，该node前一个节点为原先最后的node，后一个节点为null
    final Node<E> newNode = new Node<>(l, e, null);
    将链表末尾节点设置为新节点
    last = newNode;
    // 如果l为null，说明链表为空，那么链表的首节点赢设置为新添加的节点
    if (l == null)
        first = newNode;
    else
        // 否则需要设置链表原先末尾节点的下一个节点为新添加的节点
        l.next = newNode;
    // 链表长度加一
    size++;
    // 修改次数增加，fail-fast特性
    modCount++;
}

add(int index, E element)方法

在index位置插入一个元素element，index及其之后的元素依次向链表后移动。

public void add(int index, E element) {
    // 检查index必须大于等于0且小于等于index
    checkPositionIndex(index);

    // 如果index为size说明添加到链表最后，和前一个add方法逻辑相同
    if (index == size)
        linkLast(element);
    else
        // 否则，将element插入到第index个node之前
        linkBefore(element, node(index));
}

linkBefore方法代码如下所示：

void linkBefore(E e, Node<E> succ) {
    // 插入点不能为null
    // assert succ != null;
    // 获取插入点前一个节点
    final Node<E> pred = succ.prev;
    // 创建新node，位于插入点和插入点前一个节点之间
    final Node<E> newNode = new Node<>(pred, e, succ);
    设置插入点前一个节点为新的node
    succ.prev = newNode;
    如果插入点前一个节点为null，说明新节点位于链表开头
    if (pred == null)
        first = newNode;
    else
        设置插入点前一个节点的下一个节点为新节点
        pred.next = newNode;
    size++;
    modCount++;
}

还有一个方法我们没有分析，这个方法是node(index)，作用为根据index查找node。代码如下：

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

    // 如果index小于size的一半，从链表第一个元素开始查找，优化查找速度
    if (index < (size >> 1)) {
        Node<E> x = first;
        // 一直循环直到找到node
        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;
    }
}

addAll方法

addAll方法负责将其他集合的所有元素添加到LinkedList中。共有两个重载版本。代码如下：

// 把c中所有元素添加到LinkedList末尾
public boolean addAll(Collection<? extends E> c) {
    // 调用另一个重载方法，插入c中元素到链表末尾
    return addAll(size, c);
}

// 把c中所有元素插入到LinkedList index位置之后
public boolean addAll(int index, Collection<? extends E> c) {
    // 检查index必须大于等于0并且小于等于size
    checkPositionIndex(index);

    // 将c转换为array
    Object[] a = c.toArray();
    // 获取a的长度
    int numNew = a.length;
    if (numNew == 0)
        return false;

    // pred为紧邻插入位置之前的节点
    // succ为紧邻插入位置之后的节点
    // 即集合c的元素会插入到pred和succ之间
    Node<E> pred, succ;
    
    if (index == size) {
        // 如果插入在链表最后
        // succ不存在，设置为null
        // pred设置为链表末端节点
        succ = null;
        pred = last;
    } else {
        // 设置succ为第index位置的node
        succ = node(index);
        // pred为succ前一个节点
        pred = succ.prev;
    }

    // 遍历a数组
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        // 创建新的node，上一个节点为pred
        Node<E> newNode = new Node<>(pred, e, null);
        
        if (pred == null)
            // 如果pred为null，说明新添加的节点为链表第一个节点
            // 设置链表第一个节点为新创建的node
            first = newNode;
        else
            // pred的下一个节点设置为新节点
            pred.next = newNode;
        // 更新pred为新节点，方便下一次循环使用
        pred = newNode;
    }

    if (succ == null) {
        // succ为null说明在链表末尾插入元素
        // 设置链表末尾节点为pred，即新加入的节点
        last = pred;
    } else {
        // 设置最后一轮新加入节点的后一个节点为succ
        pred.next = succ;
        // 设置succ前一个节点为pred
        // 这样succ后面的链表就成功的连接到新节点之后
        succ.prev = pred;
    }

    // 修改size和modCount
    size += numNew;
    modCount++;
    return true;
}

remove方法

获取并移除链表第一个元素。

public E remove() {
    return removeFirst();
}

remove调用了removeFirst方法，内容如下所示：

public E removeFirst() {
    // 获取第一个元素
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    // 将第一个元素从链表中取出
    return unlinkFirst(f);
}

unlinkFirst代码如下所示：

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    // 获取f节点的元素
    final E element = f.item;
    // 获取f的下一个节点
    final Node<E> next = f.next;
    // f节点内容置空
    f.item = null;
    // f下一个节点置空，这样f节点会被GC回收
    f.next = null; // help GC
    // 设置链表首节点为f节点后面的节点
    first = next;
    // 如果链表中无元素，这只last为null
    if (next == null)
        last = null;
    else
        // 否则设置next节点的前一个节点为null，因为此时next节点为链表首节点
        next.prev = null;
    size--;
    modCount++;
    return element;
}

remove(int index)方法

获取并移除链表中index位置的节点元素

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

移除的逻辑位于unlink方法：

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        // 如果x的前一个节点为null，说明x是链表首节点
        first = next;
    } else {
        // 设置x的前一个节点的下一个节点为x的下一个节点
        prev.next = next;
        x的前一个节点设置为null
        x.prev = null;
    }

    if (next == null) {
        // 如果x的下一个节点为null，说明x是链表的末尾节点
        last = prev;
    } else {
        // x下一个节点的前一个节点设置为x的前一个节点，x此时从链表中脱离
        next.prev = prev;
        // x节点的下一个节点置空
        x.next = null;
    }

    // x节点元素置空
    x.item = null;
    size--;
    modCount++;
    return element;
}

remove(Object o)方法

从LinkedList中获取并移除指定的元素o。如果能够获取到

public boolean remove(Object o) {
    // 如果o为null，使用==方式判断相等
    if (o == null) {
        // 遍历查找，找到后执行unlink
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        // 如果o不为null，使用equals方法判断相等
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    // 如果没有找到o，返回false
    return false;
}

clear方法

清除链表中所有的元素。如果仅把LinkedList的first和last置空是不够的，因为各个node之间的连接关系还在，有可能造成GC不回收node。

clear方法的逻辑如下：

public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    // 遍历链表中每一个node
    for (Node<E> x = first; x != null; ) {
        // 设置node内容和前后节点都为null
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    // 设置list的首尾元素为null
    first = last = null;
    // 重置size为0
    size = 0;
    modCount++;
}