前言

LinkedList使用频率相较ArrayList不高，但也值得探讨一下。适合集合高频次修改时采用。

介绍

与ArrayList不同,LinkedList是对List和Deque接口的双向链表实现。实现所有可选的列表操作，并允许所有元素（包括null）。 所有操作的执行都与双链接列表的预期一样。索引到列表中的操作将从开始或结束遍历列表，以更接近指定索引的为准。

请注意，此实现是不同步的。如果多个线程同时访问一个链表，并且至少有一个线程在结构上修改链表，则必须在外部对其进行同步。（结构修改是添加或删除一个或多个元素的任何操作；仅设置元素的值不是结构修改。）这通常通过在自然封装列表的某个对象上进行同步来实现。如果不存在此类对象，则应使用Collections.synchronizedList方法“包装”列表。最好在创建时执行此操作，以防止意外不同步地访问列表：

List list = Collections.synchronizedList(new LinkedList(...));

成员变量

    transient int size = 0;

    /**
     * 指向第一个节点的指针
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * 指向加载节点的指针
     * 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;
    }
}

数据结构

双向链表，可以从任一节点向前或者向后遍历。不支持随机访问。

push(E e)

    /**
     * 将元素推送到此列表表示的堆栈上。换句话说，在列表的前面插入元素。 此方法相当于addFirst。
     */
    public void push(E e) {
        addFirst(e);
    }

    /**
     * 在此列表的开头插入指定的元素。
     *
     * @param e the element to add
     */
    public void addFirst(E e) {
        linkFirst(e);
    }

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

这里其实就是链表的头插法，新建一个节点指向之前的头节点，之前的头节点向前指向新节点。头指针指向新的节点。

pop()

    /**
     * 从该列表表示的堆栈中弹出一个元素。换句话说，删除并返回此列表的第一个元素。 此方法等效于removeFirst（）
     */
    public E pop() {
        return removeFirst();
    }

    /**
     * 从此列表中删除并返回第一个元素。
     */
    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    /**
     * Unlinks non-null first node f.
     */
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

和push相反，pop弹出头节点，头指针指向头节点的下一个节点，下一个节点向前指向null

结尾

这里只是把LinkedList的核心数据结构指出，其他方法也都是对于双向链表的常规操作，读者可自行了解。

关于作者

我叫无涯，一位热爱coding的coder。更多文章在我的个人博客：oneyoung.top 。让我们一起进步。