【JDK1.8源码阅读】LinkedList

LinkedList源码

1 概述

​ LinkedList是实现了List和Deque接口的双向链表。实现了所有可选的list操作，并允许所有元素为null。

​ 索引集合操作，无论指定的下标元素在什么位置，都会从头或从尾部开始遍历。（ps:从头或从尾是可以自己指定的，所以链表的检索复杂度可能是0~lenth）

​ 这个实现不是线程安全的。如果多线程同时使用一个链表，只要其中一个线程修改了链表的结构，就需要在外部同步它们，否则就会出问题（结构修改指新增或删除元素，而修改元素值不算）。典型的处理办法是将集合封装到一些实体中来同步。

​ 在多线程情况下使用链表，如果没有经过封装，则就要使用Collections.synchronizedList方法返回的包装对象来使用。这是最好的防止意外出现的办法：

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

​ iterator和listIterator方法返回的迭代器是“快速失败的”：除了调用迭代器自身的add或delete方法外，在生成迭代器之后链表发生结构改变，迭代时都会抛出ConcurrentModificationException。因此，面向并发修改，迭代会快速失败，而不是去冒着未来可能会出现风险的情况下继续执行。

​ 注意，快速失败不能保证存在不同步的并发修改行为，它只是尽可能的抛出ConcurrentModificationException，绝对不能依赖这个机制来编写正常代码，这个机制仅用于debug！

作者：Josh Bloch

2 源码

以下源码的位置经过阅读的顺序调整。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;  // 初始化元素个数
    // 注：transient修饰的变量不会参与序列化。
    
    // 注：Node是LinkedList的内部类，每个Node都会记录前一个和后一个元素，和自己本身的内容
        
    /**
     * 指向第一个元素
     * 不变的: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * 指向最后一个元素
     * 不变的: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;
   
    /**
     * 空构造
     */
    public LinkedList() {
    }
    
    /**
     * 使用指定集合来初始化一个链表
     *
     * @param  c 指定要转换的集合对象
     * @throws NullPointerException 如果集合是空会抛出空指针
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    
    /**
     * 向链表中添加指定集合的所有元素,添加的顺序取决于迭代器。
     * 这个操作执行过程中，如果集合被修改了，那么结果将是未知的。
     *
     * @param c 指定要把所有元素放入链表的集合对象
     * @return {@code true} 添加成功返回true
     * @throws NullPointerException 如果集合是空会抛出空指针
     */
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c); // 传入容量默认是0
    }
    
    /**
     * 从指定位置开始，插入所有指定集合中的元素。
     * 向链表中添加指定集合的所有元素,添加的顺序取决于迭代器。
     * 如果集合内没有元素，会返回false。
     *
     * @param index 要插入元素的位置
     * @param c 指定要把所有元素放入链表的集合对象
     * @return {@code true} 添加成功返回true
     * @throws IndexOutOfBoundsException {@inheritDoc} 会下标越界
     * @throws NullPointerException 如果集合是空会抛出空指针
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        // 验证传入的下标是0~size之间的数，越界抛出异常
        checkPositionIndex(index); 
		// c(要添加的集合)要是为空就会抛出空指针
        Object[] a = c.toArray();
        int numNew = a.length;
        // 如果集合内没有元素，会返回false。
        if (numNew == 0)
            return false;
		// 初始化要插入的前一个位置和要插入的位置
        Node<E> pred, succ;
        if (index == size) {
            // 如果要插入的位置是末尾，要插入的前置位就是last（当前最后一个）
            // 而要插入的位置上就是空
            succ = null;
            pred = last;
        } else {
            // 如果指定要插入的位置不是末尾，插入的位置就直接指定真实的节点
            // 如果指定的index小于链表容量的一半，就从第一个开始找，反之从尾巴开始遍历找。
            succ = node(index);
            // 得到要插入的位置后，直接在Node成员变量中获得它的前一个位置
            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;
        }
		// 处理边界值，如果新末尾是null，就设置链表的结尾是末尾的前一个元素
        // 如果不是，就把最后一个设为末尾
        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }
		// 重设容量
        size += numNew;
        // 链表结构从初始化后开始，经过结构变更的次数
        // 表示如果是无参构造初始化的，modCount应该是0，而通过有参构造返回的则是1
        modCount++;
        return true;
    }
    
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    /**
     * Tells if the argument is the index of a valid position for an
     * iterator or an add operation.
     */
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }
    /**
     * 返回指定位置的非空节点。如果指定的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;
        }
    }
    /**
     * 这个集合结构被改变的次数。结构改变指的是那些会改变集合容量或者其他会扰乱迭代结果的操作。
     *
     * 这个属性被迭代器实现的方法使用并返回。如果这个值的改变超预期，这些方法会抛出
     * ConcurrentModificationException异常：next、remove、previous、set、add。
     * 该参数是“快速失败”机制的基础。
     *
     * 子类可以选择性使用该参数。如果子类希望使用“快速失败”机制，可以使用该参数或者重写相关方法。 
     * 单一的调用add或者remove必须在此属性上加1，或者在迭代中抛出
     * ConcurrentModificationExceptions异常。如果你的实现不使用“快速失败”机制，请忽略它。
     */
    protected transient int modCount = 0;
    
    /**
     * Links e as first element.把e链接到第一个元素
     */
    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++;
    }
    
    /**
     * Links e as last element.把e关联到最后一个元素
     */
    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++;
    }
    
    /**
     * Inserts element e before non-null Node succ.把e关联到前一个元素
     */
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        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++;
    }
    
    /**
     * Unlinks non-null first node f.断开第一个元素
     */
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }
    
    /**
     * Unlinks non-null last node l.断开最后一个元素
     */
    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }

    /**
     * Unlinks non-null node x.断开某一个元素
     * 将不会包含自己，新的链表是从头断开，则新头是原来的第二个，新头的前一个为null
     * 如果从中间断开，就仅仅是把指定的节点去掉，去掉的这个节点记录的前后元素相连
     * 如果是从最后断开，就只要去掉就行，新的末尾记录下一个为null
     */
    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;
    }
    // 用的比较少的是Deque的相关方法
    // 其他内容有兴趣的自己研究，此处就不再赘述
    

​