LinkedList源码解析

摘要：说明是对链表的扩展，其底层使用链表实现，不是线程安全的集合类。其继承，实现了各个接口，其中继承了抽象类，是对支持随机读取的的部分功能的抽象，是对不支持随机读取的的一部分功能的抽象。并且实现了接口，代表其支持双端队列的所有功能。

LinkedList是对链表的扩展，其底层使用链表实现，不是线程安全的集合类。其继承AbstractSequentialList，实现了List, Deque, Cloneable,Serializable各个接口，其中AbstractSequentialList继承了AbstractList抽象类，AbstractList是对支持随机读取的List的部分功能的抽象，AbstractSequentialList是对不支持随机读取的List的一部分功能的抽象。并且LinkedList实现了Deque接口，代表其支持双端队列的所有功能。

LinkedList首先是链表的扩展，并且实现了双端队列的接口，所以其特点如下：

随机存储，优点是不需要提前申请空间

具有双端队列的所有功能，可以简单地实现先进先出和后进先出

新增和删除时间复杂度比较少

//元素的个数
transient int size = 0;

//首节点
transient Node first;

//尾节点
transient Node last;

在此之前，先介绍一下双端链表的数据结构

private static class Node {
        //节点的值
        E item;
        //下一个节点，如果为尾节点，则此值为null
        Node next;
        //前一个节点，如果为首节点，则此值为null
        Node prev;

        Node(Node prev, E element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

//向链表头添加元素
private void linkFirst(E e) {
        final Node f = first;
        //设置新节点，令首节点等于新节点，并将新节点的next指向原来的首节点
        final Node 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 l = last;
        //设置新节点，令尾节点指向新节点，并且将新节点的prev指向原来的尾节点
        final Node newNode = new Node<>(l, e, null);
        last = newNode;
        //如果原来尾节点为空，代表为空链表，则令首节点也为新节点
          ，否则，令原来尾节点的下一个节点为新节点
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

//在给定节点之前插入对应节点
void linkBefore(E e, Node succ) {
        //获取给定节点的前一个节点，设为pred
        final Node pred = succ.prev;
        //设置新节点，令其prev为给定节点的前一个节点，next为给定节点
        final Node newNode = new Node<>(pred, e, succ);
        //同时设置给定节点的前一个节点为新节点
        succ.prev = newNode;
        //判断pred是否为空，如果是，那么新节点就是首节点
          ，否则，直接令pred的下一个节点为新节点
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

//删除首节点
private E unlinkFirst(Node f) {
        final E element = f.item;
        final Node next = f.next;
        //将首节点中相关引用置空，防止内存泄漏
        f.item = null;
        f.next = null;
        //令首节点为首节点的下一个节点
        first = next;
        //如果首节点为空，那么直接将尾节点也置空，
          否则，将当前首节点的prev置为null
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }
//删除尾节点
private E unlinkLast(Node l) {
        final E element = l.item;
        final Node prev = l.prev;
        //将尾节点中相关引用置空，防止内存泄漏
        l.item = null;
        l.prev = null; 
        //令尾节点为尾节点的前一个节点
        last = prev;
        //如果尾节点为空，那么直接将首节点也置空，
          否则，将当前尾节点的next置为null
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }
    
//删除指定元素
E unlink(Node x) {
        final E element = x.item;
        final Node next = x.next;
        final Node prev = x.prev;
        
        //如果指定节点的前一个节点为空，代表制定节点为首节点
          ，令首节点为指定节点的下一个节点，否则，指定节点
          的prev的next节点为其自身的next节点，并且令指定节点
          的prev节点为null
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
        
        //同理，如果指定节点的下一个节点为null，代表指定节点为尾节点，令
          尾节点等于指定节点的上一个节点，否则，指定节点的next节点的prev节点
          等于其自身的prev节点，且令自身的next节点等于null
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
        //最后，将指定节点的item也置为null，防止内存泄漏
        x.item = null;
        size--;
        modCount++;
        return element;
    }
//按照索引值与对应集合类进行批量添加
public boolean addAll(int index, Collection c) {
        //检验index是否合法，就是检查其是否在[0,size]范围内，如果index为size，就是尾节点
        checkPositionIndex(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        //如果集合类长度为0，那么直接返回失败
        if (numNew == 0)
            return false;
        
        //如果index与size大小相等，直接设置插入位置为尾节点
          ，否则，进行遍历查找节点，设置查找到的节点的前一个节点为插入节点
        Node 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 newNode = new Node<>(pred, e, null);
            //如果pred==null，代表index=0，此时直接插入首节点，令
              首节点等于新节点，否则，直接令pred的下一个节点为新节点，然后依序插入
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
        //如果，succ==null，代表index==size，则是直接从
          尾部进行插入，所以，直接令尾节点指向插入的最后一个节点即可
          ，否则，令最后一个插入节点的next等于succ，
          令succ的prev等于最后一个插入节点即可（其实就是进行了一个衔接）
        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }
        //对元素数量进行增加
        size += numNew;
        modCount++;
        return true;
    }
//根据索引查找对应的节点（调用这个方法的方法已经判断过index，所以直接使用）
Node node(int index) {
        //如果index靠近左边，从first开始遍历，否则，从last开始遍历
        if (index < (size >> 1)) {
            Node x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }