源码阅读之LinkedList

昨天阅读了ArrayList的源码，今天继续努力，将List下的LinkedList的源码也阅读一遍。相对于ArrayList的底层实现是用数组实现而言，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;
        }
    }

相对于ArrayList使用数组存储容量有限，使用双向链表可以更放心的扩充容量。其次在双向链表中的插入删除的时间复杂度为O(1)，具有更快的速度。但是由于链表只能从前往后查找，所以在LinkedList中其查找速度为O(n)，具有更高的复杂度。

 public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

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

LinkedList另外一个特点是有两个指针，分别是头指针和尾指针，这就可以直接获取头元素和尾元素。并且可以随时在链表头和尾插入元素。

/**
     * 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;

 /**
     * Links e as first element.
     */
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

    /**
     * Links e as last element.
     */
    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++;
    }

由于这个特点，所以LinkedList也是一个双端队列，可以在队列两端插入和删除

 public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

    /**
     * Inserts the specified element at the end of this list.
     *
     * @param e the element to insert
     * @return {@code true} (as specified by {@link Deque#offerLast})
     * @since 1.6
     */
    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }