【java容器的刻意练习】【六】LinkedList底层数据结构

今天开始学习LinkedyList源码（以后所有源码都在jdk1.13上分析）。

一般我们都有以下几个问题：

• LinkedList底层是什么数据结构？
• LinkedList优缺点是什么？
• LinkedList的适合场景有哪些？
• LinkedList面试中有哪些考点？
• LinkedList工作中用在什么场景？

今天我们先解决第一个问题：LinkedList底层是什么数据结构？

先创建一个LinkedList。

  LinkedList linkedList = new LinkedList();

进去看LinkedList()这个构造函数，如下：

    public LinkedList() {
    }

空的。我们没看错，空的，啥都没做。

那调用linkedList.add(123);加个元素，看看add(E e)源码：

    public boolean add(E e) {
        linkLast(e);
        return true;
    }

调用了这个保护函数 linkLast(E e)：

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

原来底层是个Node组成的双向链表，节点定义了3个变量，item就是我们插入对象（数据），next是指向下个节点的引用，prev是指向上一个节点的引用：

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

我们再看回first、last、size、modCount是啥？

    transient int size = 0;

    /**
     * Pointer to first node.
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     */
    transient Node<E> last;

原来first是指向双向链表第一个节点的引用；last是指向双向链表最后一个节点的引用；size是双向链表的节点数；而modCount`就是我们在ArrayList分析过的，对当前容器操作次数。

知道这些成员变量定义之后，我们再回来看刚才那个插入函数linkLast：

    /**
     * Links e as last element.
     */
    void linkLast(E e) {
        // 用临时引用`l`节点指向之前最后一个节点
        final Node<E> l = last;

        // 在`l`节点后面添加最新的`e`节点，`e`节点后面为空节点
        final Node<E> newNode = new Node<>(l, e, null);

        // 将双向链表尾引用`last`指向新节点
        last = newNode;

        // 如果链表为空，即是第一次添加
        if (l == null)
            // 双向链表头引用`fist`指向新节点
            first = newNode;
        else
            // 如果不是第一次添加，上一次最后一个节点变成倒数第二个节点
            // 它的`next`引用指向新节点，这样新节点就是倒数第一个节点
            l.next = newNode;

        // 双向链表大小、操作次数都递增
        size++;
        modCount++;
    }

到这里，我们终于知道，LinkedList的底层数据结构是双向链表。

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