JDK源码 - 0903 LinkedList

List 实现分为两种 1.数组实现空间连续，查询较快 2. 链表实现插入删除较快遍历较慢

LinkedList.png

LinkedList 为List 与 Deque 接口的【双链表】实现，允许所有元素插入包括null . 当前实现类也是存在快速失败的机制且部分方法未进行同步实现，需要人为外部同步，或进行加锁同步。

AbstractSequentialList 是提供【顺序访问】的接口，其中包含着常用的操作方法，AbstractList 接口提供【随机访问】的接口，而 AbstractSequentialList 是继承与 AbstractList

AbstractSequentialListFunction.png

LinkedList 中链表实现主要是根据Node属性进行连接实现。first 标记连接上一个节点，last 标记连接下一个节点，Node中存在属性值E item 用于存放当前节点的值。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;
 
    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;
        }
    }

}

链表实现中存在linkFirst(E e) 、linkLast(E e) 方法，用于插入特定节点。
此外存在继承与Deque的链表方法，类似于getLast()、addLast(E e) 等。
peek()，poll() 都可以用于查找第一个元素，不同的是peek()不会删除第一个元素，pop()是用于删除第一个元素。比较下不同poll() 如果出现null 元素，会返回null,但是pop()会抛出异常。

LinkedListExtendDeque.png

LinkedListExtendDeque2.png

/**
Retrieves, but does not remove, the head (first element) of this list.
*/
    public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }
 /**
     * Retrieves and removes the head (first element) of this list.
     */
   public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
 /**
     * Pops an element from the stack represented by this list.  In other
     * words, removes and returns the first element of this list.
     */
  public E pop() {
        return removeFirst();
    }
 /**
     * Removes and returns the first element from this list.
     *
     * @return the first element from this list
     * @throws NoSuchElementException if this list is empty
     */
    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }