ArrayList和LinkedList的插入删除性能差距到底有多大 计算机 内容发表于2017-07-11

从算法角度来看,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)