java集合源码分析（四）：LinkedList

概述

LinkedList 是一个不保证线程安全的、基于双向的双端链表的实现的 List 集合。LinkedList 继承了 AbstractSequentialList 抽象类，在实现 List 接口的同时还实现了 Deque 接口，也正因如此，它也具有队列的特性与方法。

这是关于 java 集合类源码的第四篇文章。往期文章：

1. java集合源码分析（一）：Collection 与 AbstractCollection
   
2. java集合源码分析（二）：List与AbstractList
3. java集合源码分析（三）：ArrayList

一、LinkedList 的类关系

LinkedList 的类关系

LinkedList 实现了 Cloneable ，Serializable 接口，表明它可以拷贝，可以被序列化。

但是和 ArrayList 或者 Vector 相比，因为它是链表，所以无法像数组那样通过下标快速随机访问，故而没有实现 RandomAccess 接口。

他实现了 List 接口，但是也实现了 Queue 的子接口 Deque，因此除了列表，他也具备双端队列的特性。

他的父类不再是 AbstractList，而是另一个继承了 AbstractList 的抽象类 AbstractSequentialList，这个类重写了 AbstractList 的一些方法，使之更适合 LinkedList 这样的链表。

二、AbstractSequentiaList

要了解 LinkedList，绕不过去他的父类 AbstractSequentiaList 抽象类。

AbstractSequentiaList 的方法

从模板方法模式的角度理解，AbstractSequentiaList 是 AbstractList 之后的又一层模板，他进一步实现了 AbstractList 中的某些关键方法，同时也会调整原先的一些算法逻辑。

而事实也是如此，对于链表来说，迭代必然和数组是不同的。而 AbstractList 原本提供两个方法 iterator() 与 listIterator()，他们分别用来获取两个不同的迭代器 Itr 与 ListItr ，在 AbstractSequentiaList 里将 iterator() 与 listIterator()方法统一起来，并且将 listIterator() 变成了一个抽象方法：

public Iterator<E> iterator() {
    return listIterator();
}

public abstract ListIterator<E> listIterator(int index);

这样一来，继承 AbstractSequentiaList 的类就必须重新实现 listIterator()方法，保证获取迭代器的行为是由子类自己决定的。

然后基于listIterator()方法，他进一步的实现了 AbstractList 中一些未实现的关键方法，比如 get()，set()，add()，remove()：

// get
public E get(int index) {
    try {
        // 直接获取从当前下标开始的迭代器，并且返回next
        return listIterator(index).next();
    } catch (NoSuchElementException exc) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
}

// set
public E set(int index, E element) {
    try {
        ListIterator<E> e = listIterator(index);
        E oldVal = e.next();
        e.set(element);
        return oldVal;
    } catch (NoSuchElementException exc) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
}

// add
public void add(int index, E element) {
    try {
        listIterator(index).add(element);
    } catch (NoSuchElementException exc) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
}

// addAll
public boolean addAll(int index, Collection<? extends E> c) {
        try {
            boolean modified = false;
            ListIterator<E> e1 = listIterator(index);
            Iterator<? extends E> e2 = c.iterator();
            while (e2.hasNext()) {
                e1.add(e2.next());
                modified = true;
            }
            return modified;
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }

// remove
public E remove(int index) {
    try {
        ListIterator<E> e = listIterator(index);
        E outCast = e.next();
        e.remove();
        return outCast;
    } catch (NoSuchElementException exc) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
}

我们可以很直观的看出，这些增删改查操作都必须依赖迭代器，而这正对应链表增删改查的行为。可以说，当实现完 listIterator() 方法以后，LinkedList 就有了基本的雏形。

三、成员变量与内部类

当一个类继承了 AbstractSequentiaList 抽象类之后，它就已经具有链表的操作模式了，但是要真正的使用，还需要提供关于链表的数据结构。

1.基本变量

// 序列化id
private static final long serialVersionUID = 876323262645176354L;

// 集合中元素的格式
transient int size = 0;

2.双向/双端链表

LinkedList 的结构

LinkedList 底层实现是一个双向的双端链表，因此他具有一个节点内部类 Node ，类内持有前驱节点与后继节点的指针，LinkedList 类内持有整个链表的头尾指针：

/// 头指针
transient Node<E> first;

// 尾指针
transient Node<E> last;

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

四、构造方法

LinkedList 提供了只提供了两个构造方法：

/**
     * Constructs an empty list.
     */
public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

五、类内的公共方法

LinkedList 把一些增删节点的通用操作提取成了私有或者默认的公共方法：

1.添加节点

// 添加头结点
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    // 如果当前链表为空
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

// 添加尾节点
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++;
}

// 添加到某个节点之前
void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    // 如果是头结点
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

2.删除节点

// 删除某个节点
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) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    // 如果是尾节点
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

// 删除尾节点
private E unlinkLast(Node<E> l) {
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null;
    last = prev;
    // 如果是头结点
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

// 删除尾节点
private E unlinkFirst(Node<E> f) {
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null;
    first = next;
    // 如果是尾节点
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

3.参数校验

LinkedList 内部提供两个参数校验的私有方法：

checkElementIndex()：判断是否为现有元素的索引

private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

checkPositionIndex：判断是

六、迭代器 ListItr

1.迭代器的构造方法

LinkedList 重新设计了一个 ListItr 迭代器，并且实现了 listIterator()方法，这是一切可用方法实现的前提。

当一个 ListItr 根据传入的索引被创建的时候，实际上是获取到了索引对应的节点，我们的遍历都是基于这个节点展开，这样可以有效避免每一次迭代都需要重新遍历链表。

private class ListItr implements ListIterator<E> {
    // 最后一个操作的节点
    private Node<E> lastReturned;
    // 下一个节点
    private Node<E> next;
    // 下一个节点的索引
    private int nextIndex;
    // 记录 modCount
    private int expectedModCount = modCount;

    ListItr(int index) {
        // 如果不是在队尾，就找到下标对应的节点
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }
}

这里的 node()是一个通过 for 循环获取下标对应节点的方法：

Node<E> node(int 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;
    }
}

可以看到这是一个很巧妙的想法，借助双端链表的特点，根据下标确定要从头还是尾开始遍历，这样可以保证最多只遍历链表一半的节点，提高查找效率。

2.迭代器的成员方法

迭代器内部提供了一系列用于确认节点位置与链表状态的方法：

public boolean hasNext() {
    return nextIndex < size;
}

// 获取下一个节点
public E next() {
    checkForComodification();
    if (!hasNext())
        throw new NoSuchElementException();

    lastReturned = next;
    next = next.next;
    nextIndex++;
    return lastReturned.item;
}

public boolean hasPrevious() {
    return nextIndex > 0;
}

// 获取上一个节点（当前节点）
public E previous() {
    checkForComodification();
    if (!hasPrevious())
        throw new NoSuchElementException();

    lastReturned = next = (next == null) ? last : next.prev;
    nextIndex--;
    return lastReturned.item;
}

public int nextIndex() {
    return nextIndex;
}

public int previousIndex() {
    return nextIndex - 1;
}

// 移除当前节点
public void remove() {
    checkForComodification();
    if (lastReturned == null)
        throw new IllegalStateException();

    Node<E> lastNext = lastReturned.next;
    // 删除节点
    unlink(lastReturned);
    if (next == lastReturned)
        next = lastNext;
    else
        nextIndex--;
    lastReturned = null;
    expectedModCount++;
}

// 更新
public void set(E e) {
    if (lastReturned == null)
        throw new IllegalStateException();
    checkForComodification();
    lastReturned.item = e;
}

// 添加节点
public void add(E e) {
    // 并发修改检查
    checkForComodification();
    lastReturned = null;
    if (next == null)
        linkLast(e);
    else
        linkBefore(e, next);
    nextIndex++;
    expectedModCount++;
}

// 遍历并且对节点中的值进行处理
public void forEachRemaining(Consumer<? super E> action) {
    Objects.requireNonNull(action);
    // 每次循环都进行并发修改检查，所以遍历中不允许进行结构性操作
    while (modCount == expectedModCount && nextIndex < size) {
        action.accept(next.item);
        lastReturned = next;
        next = next.next;
        nextIndex++;
    }
    checkForComodification();
}

3.包装类 DescendingIterator

现在，通过 ListItr 可以正向也可反向迭代，但是为了方便，LinkedList 提供了一个 ListItrl 的反向迭代器适配器 DescendingIterator，他在 ListItr 的同名正向方法里，引用了反向迭代的方法，以实现调用他的 next()，实际上却调用 ListItr 的 previous()的效果。

他和 AbstractList 的 SubList 一样体现了适配器模式的思想，不过它只提供简单的几个功能，远远不如 SubList 相对 AbstractList 那样强大：

private class DescendingIterator implements Iterator<E> {
    private final ListItr itr = new ListItr(size());
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    public E next() {
        return itr.previous();
    }
    public void remove() {
        itr.remove();
    }
}

4.迭代中操作的问题

和 ArrayList 一样，LinkedList 不使用迭代器删除会出现各种问题。

forEach

由于 LinkedList 没有重写 forEach()方法，使用 forEach()仍然还是沿用 Iterable 接口提供的增强 for 循环实现，实际上编译以后还是用的迭代器，也就是说：

// forEach
list.forEach(list::remove);

// 增强for
for (T t : list) {
    list.remove(t);
}

// 迭代器
Iterator<T> iterator = list.listIterator();
while (iterator.hasNext()) {
    list.remove(iterator.next());
}

上面这三种写法是没区别的，最后都会变成第三种，由于迭代器创建的时候就会获取 modCount赋给成员变量 expectedModCount，因此，在迭代器里调用非迭代器自带的结构性操作方法，都会在第二次的并发修改检测的时候抛出异常。

LinkedList<String> list = new LinkedList<>(Arrays.asList("a","b","c","d"));
int i = 1;
Iterator<String> iterator = list.listIterator();
while (iterator.hasNext()) {
    String s = iterator.next();
    if (i++ == 1) {
        list.add(s); // ConcurrentModificationException
    }
}

for循环

for 循环的删除与 Arraylist 一样，根据下标删除也会因为索引对应的元素偏移而出现“漏删”的情况：

LinkedList<String> list = new LinkedList<>(Arrays.asList("a","b","c","d"));
for (int i = 0; i < list.size(); i++) {
    list.remove(i);
}
System.out.println(list); // [b, d]

解决的方式也跟 ArrayList 一样，选择一个不会引起索引偏移的删除方式，比如倒序删除：

LinkedList<String> list = new LinkedList<>(Arrays.asList("a","b","c","d"));
for (int i = list.size() - 1; i >= 0 ; i--) {
    list.remove(i); // 等同于 list.remove(list.get(i));
}
System.out.println(list); // []

七、来自 List 接口的方法

由于 LinkedList 很大部分的实现的抽象方法都来自于 Deque 接口，因而将来自 Deque 与 List 接口的方法分开讨论。

1.get / set / add

public E get(int index) {
    // 检查下标
    checkElementIndex(index);
    return node(index).item;
}

public E set(int index, E element) {
    checkElementIndex(index);
    // 获取下标对应的节点
    Node<E> x = node(index);
    // 更新节点的值
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

public boolean add(E e) {
    // 添加节点至队尾
    linkLast(e);
    return true;
}

2.addAll

// 从指定位置添加集合中的全部元素到链表
public boolean addAll(int index, Collection<? extends E> c) {
    // 检查 index >= 0 && index <= size;
    checkPositionIndex(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    // 要添加的是否为空集合
    if (numNew == 0)
        return false;

    Node<E> pred, succ;
    // 如果是添加在队尾
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        // 遍历获取元素
        pred = succ.prev;
    }

    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        // 是否为头结点
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

    // 如果添加的节点在队尾，那么添加的节点就是新的尾节点
    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}

// 将集合中的全部元素添加到队尾
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

3.remove

// 根据节点的索引删除
public E remove(int index) {
    checkElementIndex(index);
    // 移除下标对应的节点
    return unlink(node(index));
}

// 根据节点的值删除
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

4.toArray

public Object[] toArray() {
    // 创建一个新数组
    Object[] result = new Object[size];
    int i = 0;
    // 将节点对应的值填到数组中
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}

public <T> T[] toArray(T[] a) {
    // 如果数组的长度小于集合元素数量
    if (a.length < size)
        a = (T[])java.lang.reflect.Array.newInstance(
        a.getClass().getComponentType(), size);
    int i = 0;
    Object[] result = a;
    // 将节点对应的值填入数组
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;

    // 如果传入数组的长度大于集合元素数量
    if (a.length > size)
        a[size] = null;
    return a;
}

5.contains / indexOf

public boolean contains(Object o) {
    return indexOf(o) != -1;
}

public int indexOf(Object o) {
    int index = 0;
    // 查找节点是否为null
    if (o == null) {
        // 遍历节点
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

6.lastIndexOf

public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        // 从后向前遍历
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            // 返回把遇到的第一个符合条件的节点的下标
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}

7.clear

LinkedList 的 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

清除节点之间的所有链接是“不必要的”，但是：

1.如果被丢弃的节点驻留在多个代中，那么这样有助于分代 GC；

2.如果存在可访问的迭代器，也不妨碍释放内存；

对这段话，我是这么理解的：

有些节点可能被多次访问，有些则很少被访问，这样这些节点对象可能就会分布在不同的年代，断开引用可以保证不常使用的节点尽快回收。同时，每一个迭代器内部都会持有一个节点的引用，因此断开节点间的引用可以避免只要迭代器不销毁，引用链上的节点都无法回收的情况。

public void clear() {
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        // 清空节点的值，并断开每一个节点引用
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

八、来自 Deque接口的方法

Deque 接口的实现类都是双端队列，因此他操作方法总是同时存在从队头或者队尾两个版本：

我们可以简单粗暴的理解：但凡方法名带 Last 或者 Firs 的方法，基本都是由 Deque 提供的。

Deque 的方法

由于只要规定好从只从队头操作，那么这个结构同样也可以实现栈的效果，因此 Deque 的实现类也常用于代替 Stack 类，即List接口下老旧的 Vector 实现类的子类 Stack 类。

stack 对应的方法

换句话说，LinkedList 实现了 Deque 接口，所以他既有队列该有的方法，也有栈该有的方法。

1.add / offer / push

// 插到队首
public void push(E e) {
    addFirst(e);
}
public void addFirst(E e) {
    linkFirst(e);
}
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

// 插到队尾
public void addLast(E e) {
    linkLast(e);
}
public boolean offerLast(E e) {
    addLast(e);
    return true;
}

2.remove / poll / pop

// 移除头结点
public E remove() {
    return removeFirst();
}
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
public E pop() {
    return removeFirst();
}

// 移除尾节点
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}
public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}

3.get / peek / element

peek 的意思是“瞟一眼”，在栈中 pop()会直接让栈顶元素出栈，所以当只想获取元素而不删除的时候，就需要 peek()，在 LinkedList 中 pop()其实就等于删除头结点，而 peek()自然就等于获取头结点。

public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}
public E element() {
    return getFirst();
}

九、其他

LinkedList 实现了 Cloneable 结构，所以他自然有 clone()方法可用。在 LinkedList，clone()分为了两步：

// 拷贝 LinkedList 对象本身
private LinkedList<E> superClone() {
    try {
        return (LinkedList<E>) super.clone();
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}

// 将自己的节点放入拷贝得到的 LinkedList 对象
public Object clone() {
    LinkedList<E> clone = superClone();

    // 让克隆得到的集合回到初始状态
    clone.first = clone.last = null;
    clone.size = 0;
    clone.modCount = 0;

    // 重新添加节点
    for (Node<E> x = first; x != null; x = x.next)
        clone.add(x.item);

    return clone;
}

十、总结

数据结构

LinkedList 底层实现基于双向的双端链表，他无法像 ArrayList 那样直接随机通过索引去访问元素，每一次获取迭代器或者节点，都需要通过 node()方法遍历整个链表。

LinkedList 实现了 Deque 接口，因此可以把它当成队列或者栈使用。实际上，他也提供了对应的同名方法。

迭代优化

尽管 LinkedList 针对这个问题做了优化，在遍历之前，通过位运算获取当前链表长度的一半，借此判断要获取的节点在链表前半截还是后半节，以选择从头还是尾开始遍历，保证了最坏情况下也只需要遍历一半的节点就能找到目标节点。

因此，如非必要，最好不要通过下标去删除 LinkedList 中的元素，或者尽量在一次循环中完成所有操作。

迭代操作

LinkedList 的迭代器创建的时候就会获取 modCount，所以在迭代器里调用非迭代器自带的结构性操作方法，都会导致在下一次调用迭代器的结构性操作方法的时候抛出 ConcurrentModificationException异常。

LinkedList 在 for 循环中删除元素，同 ArrayList 一样，会因为索引“偏移”导致漏删，解决方式也是倒序删除或者其他不会导致索引“偏移”的方法——当然，考虑到性能问题，最好不要在 for 循环去操作 LinkedList。