JAVA8 LinkedList源码学习总结

一、LinkedList是一个双向链表，数据结构图如下（节点中的数字为节点存储的内容）：

LinkedList结构

二、LinkedList内部有一个Node类，Node类有三个成员变量，分别是item（节点存储的内容）、prev（指向上一个Node）、next（指向下一个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实现了List、Queue、Deque（双端队列）接口，有List的特性（有顺序、不重复），支持Queue操作（先进后出），支持Deque操作（在队首队尾插入删除元素），此外，还提供了push、pop方法，因此还有栈的特性。

四、LinkedList常用API

1. 在链表头添加元素的方法：addFirst、offerFirst、push，在链表尾添加元素的方法：add、addLast、offerLast、offer。
2. 在链表头删除元素的方法：（删除元素的同时会返回所删除的元素，但有可能元素不存在，即链表为空，当遇到这种情况时LinkedList提供了两种处理方式，返回null或者抛出异常），返回null的方法有poll、pollFirst，抛出异常的方法有removeFirst、remove、pop。在链表末端删除元素的方法（末端元素同样可以不存在，即链表为空）：返回null的方法有pollLast，抛出异常的方法有removeLast。
3. 获取链表头元素的方法（获取元素同样会出现链表为空的情况）：返回null的方法有peek、peekFirst、element，抛出异常的方法有getFirst。获取链表末端元素的方法：返回null的方法有peekLast，抛出异常的方法有getLast。

五、与ArrayList一样，有两个toArray方法，toArray()和toArray(T[] a)，toArray()返回一个Object[]数组，toArray(T[] a)返回一个特定类型的数组。

六、内部有3个迭代器类，ListItr、DescendingIterator、LLSpliterator。

1. ListItr可以向前向后遍历，还可以增加元素、设置某个位置的元素。
2. DescendingIterator是从链表末端向前（单向）遍历的迭代器，内部其实是封装了一个ListItr，next方法委托了ListItr的previous方法，hasNext委托了ListItr的hasPrevious方法。
3. LLSpliterator是java8并行迭代器的一个实现，此实现通过trySplit返回一个Spliterators.ArraySpliterator对象，该对象再通过trySplit可把元素分割两半，然后可以交给多个线程处理。