【Java集合】JDK1.8源码之LinkedList（详细注释+常见问题）

详细注释

LinkedList类属性与继承关系：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    /**
     * 实际元素个数
     */    
    transient int size = 0;
    /**
     * 链表头结点
     */
    transient Node<E> first;
    /**
     * 链表尾结点
     */
    transient Node<E> last;
    //
}

（1）LinkedList底层实现为双向链表。链表的特点就是插入删除数据快，而查询数据慢。
（2）因为使用链表的原因，所以不存在容量不足的问题，没有扩容机制。
（3）从后面的源码分析中我们也可以看出，LinkedList支持null并且LinkedList没有同步机制。
（4）LinkedList直接继承于AbstractSequentialList，同时实现了List接口，也实现了Deque接口（双端队列）。
AbstractSequentialList为顺序访问的数据存储结构提供了一个骨架类实现，如果要支持随机访问，则优先选择AbstractList类继承。LinkedList 基于链表实现，因此它继承了AbstractSequentialList。

内部类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;
        }
    }

类的构造方法：

    /**
     * 无参数构造函数
     */
    public LinkedList() {
    }

    public LinkedList(Collection<? extends E> c) {
        // 调用无参数构造函数
        this();
        // 添加进参数集合c里所有的元素
        addAll(c);
    }

添加(单个)操作：

    public boolean add(E e) {
        // 将元素e添加到链表尾部
        linkLast(e);
        return true;
    }

    void linkLast(E e) {
        // 保存尾结点
        final Node<E> l = last;
        // 创建以元素e为数据域的新结点，将其前结点(prev)指向当前尾结点(l)
        final Node<E> newNode = new Node<>(l, e, null);
        // 重新设置尾结点
        last = newNode;
        // 当之前的尾结点(l)为空时，说明当前链表也为空
        if (l == null)
            //将新结点设置为头结点
            first = newNode;
        else
            //将之前的尾结点(l)的后一结点(next)指向新生成的结点(newNode)
            l.next = newNode;
        // 大小+1
        size++;
        // 结构性修改+1
        modCount++;
    }

    public void add(int index, E element) {
        // 校验索引index
        checkPositionIndex(index);
        // 当索引值等于size时(也就是当前尾结点的索引值+1)
        if (index == size)
            // 将元素e添加到链表尾部            
            linkLast(element);
        else
            // 将元素e添加至node(index)的前一位
            linkBefore(element, node(index));
    }

    Node<E> node(int index) {
        // 判断索引index值是不是小于整个链表长度的一半
        // 也就是判断索引是距离链表头近还是链表尾近
        if (index < (size >> 1)) {
            // 保存头结点
            Node<E> x = first;
            // 从头向尾查找，直至i=index
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            // 保存尾结点
            Node<E> x = last;
            // 从尾向前查找，直至i=index
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }    

    void linkBefore(E e, Node<E> succ) {
        // 保存参数结点succ的前一结点
        final Node<E> pred = succ.prev;
        // 创建以元素e为数据域的新结点
        // 将其前结点(prev)指向参数结点succ的前一结点(pred)
        // 将其后结点(next)指向参数结点(succ)
        final Node<E> newNode = new Node<>(pred, e, succ);
        // 重新设置参数结点(succ)的前一结点，指向新结点(newNode)
        succ.prev = newNode;
        // 当之前的参数结点succ的前一结点为空时
        // 说明当前链表也为空
        if (pred == null)
            // 将新结点设置为头结点            
            first = newNode;
        else
            // 将之前的参数结点succ的前一结点(pred)的后一结点(.next)指向新生成的结点(newNode)
            pred.next = newNode;
        // 大小+1
        size++;
        // 结构性修改+1
        modCount++;
    }      

添加(多个)操作：

    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

    /*
    * 参数中的index表示在索引下标为index的结点（实际上是第index + 1个结点）的前面插入
    */
    public boolean addAll(int index, Collection<? extends E> c) {
        // 校验索引值
        checkPositionIndex(index);
        // 将参数集合c转换为数组
        Object[] a = c.toArray();
        // 保存数组长度
        int numNew = a.length;
        // 当长度等于0,代表参数集合c为空
        if (numNew == 0)
            return false;
        // 设置前结点，后结点
        Node<E> pred, succ;
        // 当插入位置为链表尾部时
        // 后结点设为null，前结点设为链表尾结点(last)
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            // 插入其他位置时
            // 后结点设为 索引为index的结点
            succ = node(index);
            // 前结点设为 当前前结点(succ)的前结点            
            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)，使其指向当前新结点
            pred = newNode;
        }
        // 在参数集合c中最后一个元素插入后
        // 当之前获取到的后结点(succ)为空时
        if (succ == null) {
            // 将尾结点指向参数集合c中的最后一个元素
            last = pred;
        } else {
            // 将之前获取到的后结点(succ)与参数集合c中的最后一个元素互相指向
            pred.next = succ;
            succ.prev = pred;
        }
        // 修改实际元素个数
        size += numNew;
        // 结构性修改+1
        modCount++;
        return true;
    }

删除操作：

    public E remove(int index) {
        // 校验索引值
        checkElementIndex(index);
        return unlink(node(index));
    }

    public boolean remove(Object o) {
        // 判断参数o是否为null
        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;
                }
            }
        }
        // 未找到值，返回false
        return false;
    }

    E unlink(Node<E> x) {
        // 保存参数结点(x)的数据域
        final E element = x.item;
        // 保存参数结点(x)的后结点
        final Node<E> next = x.next;
        // 保存参数结点(x)的前结点
        final Node<E> prev = x.prev;
        // 前结点为空时 表明参数结点(x)为头结点
        if (prev == null) {
            // 将头结点指向后结点(next)
            first = next;
        } else {
            // 将前结点(prev)的后结点(.next)直接指向当前后结点(next)
            prev.next = next; // 赋值前驱结点的后继
            // 参数结点(x)的前结点(.prev)指向null
            x.prev = null;
        }
        // 后结点为空时 表明参数结点(x)为尾结点        
        if (next == null) {
            // 将尾结点指向前结点(prev)        
            last = prev;
        } else {
            // 将后结点(next)的后结点(.pre)直接指向当前 前结点(prev)
            next.prev = prev;
            // 参数结点(x)的后结点(.next)指向null            
            x.next = null;
        }
        // 参数结点(x)的数据域设置为null
        x.item = null;
        // 大小-1
        size--;
        // 结构性修改+1
        modCount++;
        // 返回原数据域
        return element;
    }    

常见问题

1.关于LinkedList的描述：
以双向链表实现。链表无容量限制，但双向链表本身使用了更多空间，每插入一个元素都要构造一个额外的Node对象，也需要额外的链表指针操作。

按下标访问元素－get（i）、set（i,e） 要悲剧的部分遍历链表将指针移动到位 （如果i>数组大小的一半，会从末尾移起）。

插入、删除元素时修改前后结点的指针即可，不再需要复制移动。但还是要部分遍历链表的指针才能移动到下标所指的位置。

只有在链表两头的操作－add（）、addFirst（）、removeLast（）或用iterator（）上的remove（）倒能省掉指针的移动。

2.LinkedList数据结构：

LinkedList底层使用的双向链表结构，有一个头结点和一个尾结点，双向链表意味着我们可以从头开始正向遍历，或者是从尾开始逆向遍历，并且可以针对头部和尾部进行相应的操作

3.ArrayList和LinkedList的相同点
（1）两者均不是线程安全的。
（2）两者都支持null值。
（3）都实现了List接口。

4.ArrayList和LinkedList的不同点
（1）LinkedList 基于链表实现，便于顺序访问，它继承了AbstractSequentialList。而ArrayList支持随机访问，继承了AbstractList类。
（2）因为LinkedList 是基于链表的，因此不像ArrayList需要扩容机制。
（3）各种操作的性能对比：对于ArrayList来说，得益于快速随机访问的特性，获取任意位置元素是比较有效率的。如果是add或者remove操作，要分两种情况，如果是在ArrayList尾部做add，是不需要移动其他元素，耗时是O(1)。但如果在中间插入新元素的话，耗时是O(n-index)。另外，当ArrayList扩容时，会自动生成一个新的array(长度是之前的1.5倍)，再将旧的array移值上去，耗时是O(n)。。
因此，ArrayList的get操作快一些，而add操作，若add的位置为List中间，肯定是LinkedList要快一些，尾部的话两者差不多。具体使用哪个需要分场景选择最合适的。

参考：
http://blog.csdn.net/seu_calvin/article/details/53012654
http://calvin1978.blogcn.com/articles/collection.html/