面试官：LinkedList 真的是查找慢、增删快？

南风

发布于 2019-12-19 15:36:44

2.2K0

发布于 2019-12-19 15:36:44

文章被收录于专栏：Java大联盟

作者 | 你在我家门口

juejin.im/post/5c00987de51d451aa843b67b

测试结果

废话不多说，先上测试结果。作者分别在 ArrayList 和 LinkedList 的头部、尾部和中间三个位置插入与查找 100000 个元素所消耗的时间来进行对比测试，下面是测试结果。

在这里说明一下测试的环境，尾部插入是在空表的基础上测试的，头部和中间位置插入是在已存在 100000 个元素的表上进行测试的。

测试结论

ArrayList 的查找性能绝对是一流的，无论查询的是哪个位置的元素。
ArrayList 除了尾部插入的性能较好外（位置越靠后性能越好），其他位置性能就不如人意了。
LinkedList 在头尾查找、插入性能都是很棒的，但是在中间位置进行操作的话，性能就差很远了，而且跟 ArrayList 完全不是一个量级的。

源码分析

我们把 Java 中的 ArrayList 和 LinkedList 就是分别对顺序表和双向链表的一种实现，所以在进行源码分析之前，我们先来简单回顾一下数据结构中的顺序表与双向链表中的关键概念

顺序表：需要申请连续的内存空间保存元素，可以通过内存中的物理位置直接找到元素的逻辑位置。在顺序表中间插入 or 删除元素需要把该元素之后的所有元素向前 or 向后移动。
双向链表：不需要申请连续的内存空间保存元素，需要通过元素的头尾指针找到前继与后继元素（查找元素的时候需要从头 or 尾开始遍历整个链表，直到找到目标元素）。在双向链表中插入 or 删除元素不需要移动元素，只需要改变相关元素的头尾指针即可。

所以我们潜意识会认为：ArrayList 查找快，增删慢。LinkedList 查找慢，增删快。但实际上真的是这样的吗？我们一起来看看吧。

测试程序

测试程序代码基本没有什么营养，这里就不贴出来了，但是得把程序的运行结果贴出来，方便逐个分析。

运行结果

ArrayList尾部插入100000个元素耗时：26ms LinkedList尾部插入100000个元素耗时：28ms ArrayList头部插入100000个元素耗时：859ms LinkedList头部插入100000个元素耗时：15ms ArrayList中间插入100000个元素耗时：1848ms LinkedList中间插入100000个元素耗时：15981ms ArrayList头部读取100000个元素耗时：7ms LinkedList头部读取100000个元素耗时：11ms ArrayList尾部读取100000个元素耗时：12ms LinkedList尾部读取100000个元素耗时：9ms ArrayList中间读取100000个元素耗时：13ms LinkedList中间读取100000个元素耗时：11387ms

ArrayList 尾部插入

add(E e)方法

public boolean add(E e) {
        // 检查是否需要扩容
        ensureCapacityInternal(size + 1); // Increments modCount!!
        // 直接在尾部添加元素
        elementData[size++] = e;
        return true;
    }

可以看出，对ArrayList的尾部插入，直接插入即可，无须额外的操作。

LinkedList 尾部插入

LinkedList中定义了头尾节点。

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

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

add(E e)方法，该方法中调用了linkLast(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;
        // 创建一个新的结点，其头结点指向last
        final Node<E> newNode = new Node<>(l, e, null);
        // 尾结点置为newNode
        last = newNode;
        if (l == null)
            first = newNode;
        else
            // 修改原先的尾结点的尾结点，使其指向新的尾结点
            l.next = newNode;
        size++;
        modCount++;
    }

总结

对于尾部插入而言，ArrayList 与 LinkedList 的性能几乎是一致的。

ArrayList 头部插入

add(int index, E element)方法，可以看到通过调用系统的数组复制方法来实现了元素的移动。所以，插入的位置越靠前，需要移动的元素就会越多。

public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1); // Increments modCount!!
        // 把原来数组中的index位置开始的元素全部复制到index+1开始的位置（其实就是index后面的元素向后移动一位）
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 插入元素
        elementData[index] = element;
        size++;
    }

LinkedList 头部插入

add(int index, E element)方法，该方法先判断是否是在尾部插入，如果是调用linkLast()方法，否则调用linkBefore()，那么是否真的就是需要重头开始遍历呢？我们一起来看看。

public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

在头尾以外的位置插入元素当然得找出这个位置在哪里，这里面的 node() 方法就是关键所在，这个函数的作用就是根据索引查找元素，但是它会先判断index 的位置，如果 index 比 size 的一半 (size >> 1,右移运算，相当于除以 2）要小，就从头开始遍历。

否则，从尾部开始遍历。从而可以知道，对于 LinkedList 来说，操作的元素的位置越往中间靠拢，效率就越低。

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

这个函数的工作就只是负责把元素插入到相应的位置而已，关键的工作在 node() 方法中已经完成了。

void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }