你不知道的LinkedList(二)：LinkedList的增删

十年前，在刚解除java不久，面试中就有人问道LinkedList和ArrayList的区别。我记得当时普片的答案都说是，LinikedList底层基于链表实现。而ArrayList底层基于数据。因此LinkedList的查找操作比ArrayList慢，但是增删等操作由于不需要移动数据，因此会比ArrayList快。但是事实上果真如此吗？对此，我们对ArrayList和LinkedList的多种情景进行分析。
定义的全局变量如下：

public static final int initSize = 100000;
public static final int changeSize = 400000;

private static ArrayList<Integer> arrayList = new ArrayList<>(initSize+changeSize);
private static LinkedList<Integer> linkedList = new LinkedList<>();

private static final Random random = new Random();

另外还有一个初始化方法，使用之前先对List初始化：

private static void initElems() {
    arrayList.clear();
    IntStream.range(0,initSize).forEach(i -> {
        arrayList.add(i);
        linkedList.add(i);
    });
}

1.插入分析

对于一个集合，我们最常用的方式是向其中插入数据，常用的方法有头插和尾插还有随机插入三种方法，现在根据这三种方法分别进行分析。为了真实有用，我们定义了一个初始大小为10000。

1.1 尾插法

尾插法就是在列表的末尾插入一个元素，代码如下：

private static void tailInsert(ArrayList arrayList,int size) {
    long start = System.currentTimeMillis();
    IntStream.range(0,size).forEach(i -> {
        arrayList.add(i);
    });
    long end = System.currentTimeMillis();
    System.out.println("ArrayList tailInsert cost:"+(end-start)+"ms");
}

private static void tailInsert(LinkedList linkedList,int size) {
    long start = System.currentTimeMillis();
    IntStream.range(0,size).forEach(i -> {
        linkedList.add(i);
    });
    long end = System.currentTimeMillis();
    System.out.println("LinkedList tailInsert cost:"+(end-start)+"ms");
}

我们只需修改changeSize的大小，然后再对结果进行比较，测试之后结果如下（时间单位ms）：

数据量	10万	20万	40万	80万	160万	320万	640万
ArrayList	5	8	8	14	29	125	3528	3209
LinkedList	4	8	11	21	266	3575	7179

可以看出，在数据量较小的时候，LinkedList还是有优势的。随着数据量的增大，LinkedList的性能几乎是ArrayList的二倍以上。

1.2 头插法

我们再修改为对一个集合头部进行插入：

private static void headInsert(ArrayList arrayList,int size) {
    long start = System.currentTimeMillis();
    IntStream.range(0,size).forEach(i -> {
        arrayList.add(0,i);
    });
    long end = System.currentTimeMillis();
    System.out.println("ArrayList headInsert cost:"+(end-start)+"ms");
}

private static void headInsert(LinkedList linkedList,int size) {
    long start = System.currentTimeMillis();
    IntStream.range(0,size).forEach(i -> {
        linkedList.add(0,i);
    });
    long end = System.currentTimeMillis();
    System.out.println("LinkedList headInsert cost:"+(end-start)+"ms");
}

我们修改changeSize的大小，然后再对结果进行比较，测试之后结果如下（时间单位ms）：

数据量	10万	20万	40万	80万
ArrayList	1967	4467	12813	45214
LinkedList	6	9	14	26

可以看出，LinkedList在头部插入的时候能够充分发挥其链表的优点。性能非常高。

1.3 随机插入

实际上在使用List的过程中还有一种方式是随机插入数据。

private static void randomInsert(ArrayList arrayList,int size) {
    long start = System.currentTimeMillis();
    IntStream.range(0,size).forEach(i -> {
        arrayList.add(random.nextInt(initSize+i),i);
    });
    long end = System.currentTimeMillis();
    System.out.println("ArrayList randomInsert cost:"+(end-start)+"ms");
}

private static void randomInsert(LinkedList linkedList,int size) {
    long start = System.currentTimeMillis();
    IntStream.range(0,size).forEach(i -> {
        linkedList.add(random.nextInt(initSize+i),i);
    });
    long end = System.currentTimeMillis();
    System.out.println("LinkedList randomInsert cost:"+(end-start)+"ms");
}

测试之后结果如下（时间单位ms）：

数据量	10万	20万	40万	80万
ArrayList	880	2291	6663	21644
LinkedList	30589	199670	耗时太长	耗时太长

可以看到，对于随机插入，LinkedList几乎完全不能用。ArrayList在此种情况下性能还是不错的。

2.反转

对list还有一个常用的操作就是进行反转操作。

private static void reverse(ArrayList arrayList) {
    long start = System.currentTimeMillis();
    Collections.reverse(arrayList);
    long end = System.currentTimeMillis();
    System.out.println("ArrayList reverse cost:"+(end-start)+"ms");
}


private static void reverse(LinkedList linkedList) {
    long start = System.currentTimeMillis();
    Collections.reverse(linkedList);
    long end = System.currentTimeMillis();
    System.out.println("LinkedList reverse cost:"+(end-start)+"ms");
}

我们修改initSize的大小，然后再对结果进行比较，测试之后结果如下（时间单位ms）：

数据量	10万	20万	40万	80万	160万	320万	640万
ArrayList	2	5	6	10	11	12	13
LinkedList	7	9	12	15	20	44	68

可以看到，虽然两个List对反转的处理性能都还可以，但是明显可以发现还是ArrayList的性能高。

3.分析

根据上述得到的结果进行分析，不难发现，除了头部插入这一种方法之外，其他的场景LinkedList的性能都低于ArrayList。
这是因为，LinkedList虽然修改操作只用改变前后节点的指针，而ArrayList由于需要在很多情况下通过System.arraycopy操作来创建新数组来实现将后续的元素挪动。看上去可能ArrayList的性能会低。但是实际上，在LinkedList中，对需要操作的节点寻址只能扫描全部的数据。而头插法恰恰是在头部操作不需要寻址，因此将LinkedList的优势发挥出来了。其他场景都不如ArrayList。
而这个寻址的方法即使我们之前提到的node方法：

    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;
        }
    }
    
       public void add(int index, E element) {
        checkPositionIndex(index);

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

在add方法中，如果index与size不等，则不得不用node方法找到索引位置的节点。

4.总结

经过以上分析我们可以得出，LinkedList的增删性能还真不一定比ArrayList快，在某些场景下可能还会比ArrayList低。因此，我们在使用的时候需要对其使用场景进行了解。通常情况下ArrayList的性能都好于ArrayList。
而LinkedList的头插法比ArrayList高效，这实际上也是队列的一种基本用法。实际上LinKedList本身也是一个Deque结构。
对于LinkedList,其作者也在twitter上回复：

image.png

实际上LinkedList不会有人真的用。