ArrayList 和 LinkedList 的插入删除性能差距到底有多大

雨翔河

首页列表关于

2019-01-24 15:08

>  从算法角度来看，ArrayList是便于做查询的容器，LinkedList适合插入删除。如果在一个LinkedList做查询的话只能从头指针或者尾指针开始找起，这个在学链表的时候都知道。ArrayList如果用来删除或者插入操作的话，假设删除第一个元素，那么后面的元素要依次往后移，复杂度是很恐怖的。

前段时间和同事争论ArrayList和LinkedList的底层到底是不是这么一回事，晚上抽空写了段简单的代码验证了下。

```
package net.yuxianghe;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by hxy on 2017/7/11.
 */
public class TestList {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int max = 1000000;
        List<String> list1 = new ArrayList<>();
//        List<String> list2=new LinkedList<>();

for (int i = 0; i < max; i++) {
            list1.add(i + "");
//            list2.add(i+"");
        }

for (int i = 0; i < max - 10; i++) {
            list1.remove(0);
        }

long end = System.currentTimeMillis();
        long result = end - start;
        System.out.println("result:" + result);

}
}

```

上面的代码是演示删除操纵的性能差距到底有多大，数据量1万以下的时候相差不是非常大，但是十万以上的时候得到的结果是这样的：

max : 一百万数据
`1000000` 数据移除的时间消耗
ArrayList: 92055毫秒
LinkedList: 255毫秒

相差361倍，一个是秒得结果，一个是漫长的等待了许久。。。

测试环境：

macOS Sierra  10.12.5
2.2 GHz Intel Core i7
16 GB 1600 MHz DDR3

java version "1.8.0_60"
Java(TM) SE Runtime Environment (build 1.8.0_60-b27)
Java HotSpot(TM) 64-Bit Server VM (build 25.60-b23, mixed mode)

类型：工作标签：ArrayList,LinkedList,java