文章目录

1. 1. LinkedList概述
2. 2. 构造方法
3. 3. 外部方法
4. 4. fast-fail机制
   1. 4.1. 解决方案
   2. 4.2. 抛出异常原理
   3. 4.3. 解决原理

本篇博客重点剖析继承Collection接口中的LinkedList类，JDK源码版本基于1.8.0_25。

LinkedList概述

LinkedList与ArrayList一样实现List接口，只是ArrayList是List接口的大小可变数组的实现，LinkedList是List接口链表的实现。基于链表实现的方式使得LinkedList在插入和删除时更优于ArrayList，而随机访问则比ArrayList逊色些。LinkedList继承于AbstractSequentialList，实现了List, Deque, Cloneable, java.io.Serializable这些接口。

java.lang.Object
   ↳     java.util.AbstractCollection<E>
         ↳     java.util.AbstractList<E>
               ↳     java.util.AbstractSequentialList<E>
                     ↳     java.util.LinkedList<E>

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {}

• 继承 AbstractSequentialList：双向链表，可以被当作堆栈、队列或双端队列进行操作。
• Deque 接口：为 add、poll 提供先进先出队列操作，从而能将LinkedList当作双端队列使用。
• Cloneable接口：覆盖了函数clone()，Returns a shallow copy of this ArrayList instance.
• Serializable接口：ArrayList支持序列化，能通过序列化去传输。

稍微提及一下AbstractSequentialList，AbstractSequentialList继承AbstractList，对其中的方法进行再抽象，不同于动态数组列表ArrayList。

AbstractSequentialList在功能上，最大限度地减少了实现受“连续访问”数据存储（如链接列表）支持的此接口所需的工作。说白了就是你的列表需要快速的添加删除数据等，用此抽象类，若是需要快速随机的访问数据等用AbstractList抽象类。

JDK 1.8.0_25：This class provides a skeletal implementation of the List interface to minimize the effort required to implement this interface backed by a “sequential access“ data store.

同ArrayList一样，LinkedList中的操作不是线程安全的，所以为了防止意外的非同步访问，最好在创建时声明：

List list = Collections.synchronizedList(new LinkedList(...));

LinkedList与Collection的关系：

LinkedList包含三个重要的成员：first、last 和 size。

• transient Node<E> first：双向链表的表头，它是双向链表节点所对应的类Node的实例。Node中包含成员变量：prev, next, item。
• transient Node<E> last：双向链表的表尾。
• transient int size：双向链表中节点的个数。

构造方法

LinkedList实现了一个双向列表，由first字段和last字段指向列表的头部和尾部。列表的每个节点是一个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;
        }
    }

LinkedList提供了两个构造方法：LinkedList()和LinkedList(Collection<? extends E> c)。

前一个构造方法为空，里面不含任何元素。后者构造一个包含指定 collection 中的元素的列表。构造函数首先会调用LinkedList()，构造一个空列表，然后调用了addAll()方法将Collection中的所有元素添加到列表中。addAll()源码如下：

public boolean addAll(int index, Collection<? extends E> c) {
        //若插入的位置小于0或者大于链表长度，则抛出IndexOutOfBoundsException异常
        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;    //前导指向队尾元素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;//表头first指向此节点
            else
                pred.next = newNode;//先导存在，则将其next指向新节点
            pred = newNode;//先导移动，继续创建新节点
        }

        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

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

外部方法

LinkedList提供了一堆linkXX和unlinkXX辅助方法，用来往列表中插入元素和删除元。

方法名	用途
linkFirst	插入头部
linkLast	插入尾部
linkBefore	插入到某个节点前
unlinkFirst	删除头部
unlinkLast	删除尾部
unlink	删除某节点

接下来是一些向外暴露的接口的方法，get、remove、add等类型的方法。用到了之前的那些辅助方法。还有一些获取当前状态的方法，比如size、isEmpty、contains，一些方法是父类的方法。

唯一值得拿出来说的是在get、set、add、remove中都有调用的node方法，它将输入的index与链表长度的1/2进行对比，如果小于链表长度的一半，就从表头first开始操作；否则就从last开始，从而节省一半的查找时间。

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

此外遍历LinkedList时切忌不要sillyB到使用随机访问去遍历，建议使用迭代器或for循环。不然你将感受到地狱。

fast-fail机制

讲了ArrayList和LinkedList，最后讲讲两者面对多线程对同一个集合操作时，可能会产生的fail-fast事件。

fail-fast 机制是java集合(Collection)中的一种错误机制。简单来说就是当某一个线程遍历list的过程中，list的内容被另外一个线程所改变了；就会抛出ConcurrentModificationException异常，产生fail-fast事件。

解决方案

fail-fast机制，是一种错误检测机制。它只能被用来检测错误，因为JDK并不保证fail-fast机制一定会发生。若在多线程环境下使用fail-fast机制的集合，建议使用“java.util.concurrent包下的类”去取代“java.util包下的类”。

所以，本例中只需要将ArrayList替换成java.util.concurrent包下对应的类即可。即，将代码

private static List<String> list = new ArrayList<String>();

替换为

private static List<String> list = new CopyOnWriteArrayList<String>();

抛出异常原理

原理很简单，在AbstractList里定义了一个叫modCount的玩意。

protected transient int modCount = 0;

这货存在的全部意义就是在有操作对List进行修改时，自加一。例如在ArrayList里的 ensureExplicitCapacity 方法，remove方法，clear方法等等。

产生fail-fast事件，是通过抛出ConcurrentModificationException异常来触发的。而ConcurrentModificationException是在操作Iterator时抛出的异常。

再查看Iterator的源码你会发现，Iterator里定义了一个叫expectedModCount的变量，初始化等于modCount的值。

所以每次遍历List中的元素的时候，都会比较 expectedModCount 和 modCount 是否相等。如果不相等则抛出异常。

那么什么时候 modCount 不等于 expectedModCount呢？查看ArrayList的源码，如上面所说，无论是 ensureExplicitCapacity()、add()、remove()，还是clear()，只要涉及到修改集合中的元素个数时，都会改变modCount的值。

总结一下就是当多个线程对同一个集合进行操作的时候，某线程访问集合的过程中，该集合的内容被其他线程所改变(即其它线程通过add、remove、clear等方法，改变了modCount的值)；这时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。

解决原理

查看和ArrayList对应的CopyOnWriteArrayList的源码。举个最简单的例子add方法：

public boolean add(E e) {
       final ReentrantLock lock = this.lock;
       lock.lock();
       try {
           Object[] elements = getArray(); //copy一份原来的array
           int len = elements.length;
           Object[] newElements = Arrays.copyOf(elements, len + 1); 
           newElements[len] = e; //在copy的数组上add
           setArray(newElements); //原有引用指向修改后的数据
           return true;
       } finally {
           lock.unlock();
       }
   }

CopyOnWriteArrayList的add、set、remove等会改变原数组的方法中，都是先copy一份原来的array，再在copy数组上进行add、set、remove操作。然后把原有数据的引用改成指向修改后的数据，这就才不影响COWIterator那份数组。