2018-08-10JDK 1.8 LinkedList源码分析

LinkedList是一个实现了List接口和Deque接口的双端链表。
有关索引的操作可能从链表头开始遍历到链表尾部，也可能从尾部遍历到链表头部，这取决于看索引更靠近哪一端

LinkedtList内部的成员变量如下:

    transient int size = 0;
    
    transient Node<E> first;  //指向链表头部
    
    transient Node<E> last; //指向链表尾部

其中size表示当前链表中的数据个数。下面是Node节点的定义，Node类LinkedList的静态内部类:

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

add(E e)

add(E e)用于将元素添加到链表尾部，实现如下:

    public boolean add(E e) {
            linkLast(e);
            return true;
        }
    
    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++;
        }

从上面代码可以看到，linkLast方法中就是一个链表尾部添加一个双端节点的操作，但是需要注意对链表为空时头节点的处理

add(int index,E e)

add(int index,E e)用于在指定位置添加元素。实现如下：

    public void add(int index, E element) {
            checkPositionIndex(index); //检查索引是否处于[0-size]之间
    
            if (index == size)//如果要插入的索引位置就是链表的长度，就添加在链表尾部
                linkLast(element);
            else//添加在链表指定位置
                linkBefore(element, node(index));
        }

从上面代码可以看到，主要分为3步：

1. 检查index的范围，否则抛出异常
2. 如果插入位置是链表尾部，那么调用linkLast方法
3. 如果插入位置是链表之间，那么调用linkBefore方法

linkLast方法前面已经讨论了，下面看一下linkBefore的实现。在看linkBefore之前，先看一下node(int 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;
            }
        }

从上面可以看到，node(int index)方法将根据index是靠近头部还是尾部选择不同的遍历方向。一旦得到了指定索引位置的节点，再看linkBefore()方法，实现如下：

    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; //前一个有节点则让前一个节点的下个节点指向新节点，也就是新节点就在pred和succ节点之间了
            size++;
            modCount++;
        }

从上图以及代码可以看到linkBefore主要分三步：

1. 创建newNode节点，将newNode的后继指针指向succ，前驱指针指向pred
2. 将succ的前驱指针指向newNode
3. 根据pred是否为null，进行不同操作。

• 如果pred为null，说明该节点插入在头节点之前，要重置first头节点
• 如果pred不为null，那么直接将pred的后继指针指向newNode即可