ArrayList与LinkedList性能分析

今天面试时，遇到一个问题“Arraylist和LinkedList的区别”
当然咯,笔者将按照常规回答,描述了ArrayList和LinkedList的区别,如下所示

ArrayList底层是数组，增删慢，查找快。
LinkedList底层是双向链表，增删快，查找慢
=================================================
下面笔者还将详细对"ArrayList与LinkedList性能"进行对比分析,如下所示

数据插入分析

1.头部插入法

package com.java265.test.list.add;
import com.java265.test.list.AddListUtil;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
 
public class HeaderAdd {
    public static void main(String[] args) {
        System.out.println("----------10w----------");
        useTime(100000);
        System.out.println("----------30w----------");
        useTime(300000);
        System.out.println("----------50w----------");
        useTime(500000);
        System.out.println("----------100w----------");
        useTime(1000000);

    }

    public static void useTime(int count){
        System.out.println
		("从ArrayList的头部新增耗时：" + addHeader(new ArrayList<>(), count) + "ms");
        System.out.println
		("从LinkedList的头部新增耗时：" + addHeader(new LinkedList<>(), count) + "ms");
    }

    /**
     * 从List的头部新增元素
     * @param list list
     * @param count 新增元素的个数
     * @return 所耗费的时间（单位：ms）
     */
    public static long addHeader(List<String> list, int count) {
       long start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            list.add(0, "onemore-" + i);
        }
        long end =  System.currentTimeMillis();
        return (end - start);
    }
}

数据统计：数据量/w , 耗时/ms

----------11w----------
从ArrayList的头部新增耗时：510ms
从LinkedList的头部新增耗时：20ms
----------31w----------
从ArrayList的头部新增耗时：3982ms
从LinkedList的头部新增耗时：27ms
----------51w----------
从ArrayList的头部新增耗时：12019ms
从LinkedList的头部新增耗时：19ms
----------101w----------
从ArrayList的头部新增耗时：56105ms
从LinkedList的头部新增耗时：580ms 

数量级(万)	ArrayList	LinkedList
11	510 ms	20ms
31	3982 ms	27 ms
51	12019 ms	19 ms
101	56105 ms	580 ms

从实验结果上，我们可以看出
     头部插入法LinkedList效率远高于ArrayList

2.尾部插入法

package com.java265.test.list.add;

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

package com.java265.test.list.add;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
 
public class TailAdd {
    public static void main(String[] args) {
        System.out.println("----------1w----------");
        useTime(10000);
        System.out.println("----------5w----------");
        useTime(50000);
        System.out.println("----------10w----------");
        useTime(100000);
        System.out.println("----------15w----------");
        useTime(150000);
        System.out.println("----------20w----------");
        useTime(200000);
        System.out.println("----------30w----------");
        useTime(300000);
        System.out.println("----------50w----------");
        useTime(500000);
        System.out.println("----------70w----------");
        useTime(700000);
        System.out.println("----------100w----------");
        useTime(1000000);
    }

    public static void useTime(int count){
        System.out.println
		("从ArrayList的尾部新增耗时：" + addTail(new ArrayList<>(), count) + "ms");
        System.out.println
		("从LinkedList的尾部新增耗时：" + addTail(new LinkedList<>(), count) + "ms");
    }

    /**
     * 从List的尾部新增元素
     * @param list list
     * @param count 新增元素的个数
     * @return 所耗费的时间（单位：ms）
     */
    public static long addTail(List<String> list, int count) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            list.add("tail-" + i);
        }
        long end = System.currentTimeMillis();
        return (end - start);
    }
}

//运行以上代码,将输出以下信息
----------1w----------
从ArrayList的尾部新增耗时：5ms
从LinkedList的尾部新增耗时：4ms
----------5w----------
从ArrayList的尾部新增耗时：10ms
从LinkedList的尾部新增耗时：4ms
----------10w----------
从ArrayList的尾部新增耗时：15ms
从LinkedList的尾部新增耗时：4ms
----------15w----------
从ArrayList的尾部新增耗时：5ms
从LinkedList的尾部新增耗时：23ms
----------20w----------
从ArrayList的尾部新增耗时：7ms
从LinkedList的尾部新增耗时：9ms
----------30w----------
从ArrayList的尾部新增耗时：11ms
从LinkedList的尾部新增耗时：27ms
----------50w----------
从ArrayList的尾部新增耗时：13ms
从LinkedList的尾部新增耗时：68ms
----------70w----------
从ArrayList的尾部新增耗时：23ms
从LinkedList的尾部新增耗时：379ms
----------100w----------
从ArrayList的尾部新增耗时：48ms
从LinkedList的尾部新增耗时：120ms

从实验结果上，我们可以看出从数据测试来看
   对于尾插法而言
     不是说ArrayList就一定比LinkedList效率高
	  经过大量的数据测试，
	 发现10w以内LinkedList比ArrayList快
	     100w以上ArrayList明显比LinkedList快

2.数据删除

1.头部删除法

package com.java265.test.list.del;

import com.java265.test.list.DeleteListUtil;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
 
public class DelList {

    public static void main(String[] args) {
        System.out.println("----------1w----------");
        delToList(10000);
        System.out.println("----------5w----------");
        delToList(50000);
        System.out.println("----------10w----------");
        delToList(100000);
        System.out.println("----------15w----------");
        delToList(150000);
        System.out.println("----------20w----------");
        delToList(200000);
        System.out.println("----------30w----------");
        delToList(300000);
        System.out.println("----------50w----------");
        delToList(500000);
        System.out.println("----------70w----------");
        delToList(700000);
        System.out.println("----------100w----------");
        delToList(1000000);

    }

    public static void delToList(int count){

        System.out.println
		("从ArrayList的头部删除元素：" + deleteHeader(new ArrayList<>(), count) + "ms");
        System.out.println
		("从LinkedList的头部删除元素：" + deleteHeader(new LinkedList<>(), count) + "ms");

    }

    /**
     * 从List的头部删除元素
     * @param list list
     * @param count 删除元素的个数
     * @return 所耗费的时间（单位：ms）
     */
    public static double deleteHeader(List<String> list, int count) {
        for (int i = 0; i < count; i++) {
            list.add("del-" + i);
        }
        long start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            list.remove(0);
        }
        long end = System.currentTimeMillis();
        return (end - start);
    }

}

 //以上代码运行，将输出以下信息
----------1w----------
从ArrayList的头部删除元素：6.0ms
从LinkedList的头部删除元素：1.0ms
----------5w----------
从ArrayList的头部删除元素：79.0ms
从LinkedList的头部删除元素：2.0ms
----------10w----------
从ArrayList的头部删除元素：416.0ms
从LinkedList的头部删除元素：4.0ms
----------15w----------
从ArrayList的头部删除元素：875.0ms
从LinkedList的头部删除元素：2.0ms
----------20w----------
从ArrayList的头部删除元素：1587.0ms
从LinkedList的头部删除元素：5.0ms
----------30w----------
从ArrayList的头部删除元素：3623.0ms
从LinkedList的头部删除元素：6.0ms
----------50w----------
从ArrayList的头部删除元素：11891.0ms
从LinkedList的头部删除元素：8.0ms
----------70w----------
从ArrayList的头部删除元素：26807.0ms
从LinkedList的头部删除元素：15.0ms
----------100w----------
从ArrayList的头部删除元素：56940.0ms
从LinkedList的头部删除元素：30.0ms

从实验结果上，我们可以看出
  头部删除LinkedList比ArrayList快

2.尾部删除法

package com.java265.test.list.del;

import com.java265.test.list.DeleteListUtil;

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

public class DelList {
    public static void main(String[] args) {
        System.out.println("----------1w----------");
        delToList(10000);
        System.out.println("----------5w----------");
        delToList(50000);
        System.out.println("----------10w----------");
        delToList(100000);
        System.out.println("----------15w----------");
        delToList(150000);
        System.out.println("----------20w----------");
        delToList(200000);
        System.out.println("----------30w----------");
        delToList(300000);
        System.out.println("----------50w----------");
        delToList(500000);
        System.out.println("----------70w----------");
        delToList(700000);
        System.out.println("----------100w----------");
        delToList(1000000);

    }

    public static void delToList(int count){

        System.out.println
		("从ArrayList的尾部删除元素：" + deleteTail(new ArrayList<>(), count) + "ms");
        System.out.println
		("从LinkedList的尾部删除元素：" + deleteTail(new LinkedList<>(), count) + "ms");

    }

    /**
     * 从List的尾部删除元素
     * @param list list
     * @param count 删除元素的个数
     * @return 所耗费的时间（单位：ms）
     */
    public static double deleteTail(List<String> list, int count) {
        for (int i = 0; i < count; i++) {
            list.add("del-" + i);
        }
        long start = System.currentTimeMillis();;
        for (int i = 0; i < count; i++) {
            list.remove(list.size() - 1);
        }
        long end = System.currentTimeMillis();;
        return (end - start);
    }
}
 
//运行以上代码，将输出以下信息
----------1w----------
从ArrayList的尾部删除元素：1.0ms
从LinkedList的尾部删除元素：2.0ms
----------5w----------
从ArrayList的尾部删除元素：1.0ms
从LinkedList的尾部删除元素：8.0ms
----------10w----------
从ArrayList的尾部删除元素：0.0ms
从LinkedList的尾部删除元素：6.0ms
----------15w----------
从ArrayList的尾部删除元素：1.0ms
从LinkedList的尾部删除元素：4.0ms
----------20w----------
从ArrayList的尾部删除元素：0.0ms
从LinkedList的尾部删除元素：4.0ms
----------30w----------
从ArrayList的尾部删除元素：1.0ms
从LinkedList的尾部删除元素：14.0ms
----------50w----------
从ArrayList的尾部删除元素：1.0ms
从LinkedList的尾部删除元素：57.0ms
----------70w----------
从ArrayList的尾部删除元素：2.0ms
从LinkedList的尾部删除元素：29.0ms
----------100w----------
从ArrayList的尾部删除元素：4.0ms
从LinkedList的尾部删除元素：27.0ms

从实验结果上，我们可以看出
   尾部删除ArrayList比LinkedList快

3.数据检索

1.for循环遍历List

package com.java265.test.list.query;

import com.java265.test.list.IterationListUtil;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class QueryList {
    public static void main(String[] args) {
        System.out.println("----------1w----------");
        IteratToList(10000);
        System.out.println("----------5w----------");
        IteratToList(50000);
        System.out.println("----------10w----------");
        IteratToList(100000);
        System.out.println("----------15w----------");
        IteratToList(150000);
    }

    public static void IteratToList(int count){

        System.out.println
		("通过for循环遍历ArrayList：" + getByFor(new ArrayList<>(count), count) + "ms");
        System.out.println
		("通过for循环遍历LinkedList：" + getByFor(new LinkedList<>(), count) + "ms");

    }

    /**
     * 通过for循环遍历List
     *
     * @param list  list
     * @param count 遍历元素的个数
     * @return 所耗费的时间（单位：ms）
     */
    public static double getByFor(List<String> list, int count) {
        for (int i = 0; i < count; i++) {
            list.add("for-" + i);
        }
        String name = "本草中国";
        long start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            if (name.equals(list.get(i))) {
                System.out.println(name);
            }
        }
        long end = System.currentTimeMillis();
        return (end - start);
    }
}
 

//运行以上代码,将输出以下信息

----------1w----------
通过for循环遍历ArrayList：1.0ms
通过for循环遍历LinkedList：43.0ms
----------5w----------
通过for循环遍历ArrayList：1.0ms
通过for循环遍历LinkedList：1924.0ms
----------10w----------
通过for循环遍历ArrayList：1.0ms
通过for循环遍历LinkedList：11731.0ms
----------15w----------
通过for循环遍历ArrayList：1.0ms
通过for循环遍历LinkedList：13699.0ms

从实验结果上，我们可以看出
    使用for循环遍历时
	ArrayList的效率高于LinkedList,而且LinkedList的效率极低。

2.foreach循环遍历List

package com.java265.test.list.query;

import com.java265.test.list.IterationListUtil;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
 
public class QueryList {
    public static void main(String[] args) {
        System.out.println("----------1w----------");
        IteratToList(10000);
        System.out.println("----------5w----------");
        IteratToList(50000);
        System.out.println("----------10w----------");
        IteratToList(100000);
        System.out.println("----------50w----------");
        IteratToList(500000);
        System.out.println("----------100w----------");
        IteratToList(1000000);
    }

    public static void IteratToList(int count){

        System.out.println
		("通过foreach遍历ArrayList：" + getByForeach(new ArrayList<>(count), count) + "ms");
        System.out.println
		("通过foreach遍历LinkedList：" + getByForeach(new LinkedList<>(), count) + "ms");
    }

    /**
     * 通过foreach遍历List
     *
     * @param list  list
     * @param count 遍历元素的个数
     * @return 所耗费的时间（单位：ms）
     */
    public static double getByForeach(List<String> list, int count) {
        for (int i = 0; i < count; i++) {
            list.add("foreach-" + i);
        }
        String name = "本草中国";
        long start = System.currentTimeMillis();
        for (String str : list) {
            if (name.equals(str)) {
                System.out.println(name);
            }
        }
        long end = System.currentTimeMillis();
        return (end - start);
    }
}

//运行以上代码，将输出以下信息
----------1w----------
通过foreach遍历ArrayList：2.0ms
通过foreach遍历LinkedList：2.0ms
----------5w----------
通过foreach遍历ArrayList：1.0ms
通过foreach遍历LinkedList：5.0ms
----------10w----------
通过foreach遍历ArrayList：2.0ms
通过foreach遍历LinkedList：10.0ms
----------50w----------
通过foreach遍历ArrayList：4.0ms
通过foreach遍历LinkedList：7.0ms
----------100w----------
通过foreach遍历ArrayList：5.0ms
通过foreach遍历LinkedList：9.0ms

从实验结果上，我们可以看出
    使用foreach遍历时
	 ArrayList的效率和LinkedList相差不大。

---

从以上的测试情况，我们可以得出以下结论

ArrayList是实现基于动态数组的数据结构
LinkedList基于链表的数据结构

新增元素:
  头插法：
    LinkedList效率远高于ArrayList
  尾插法：
   对于尾插法而言，
       ArrayList就一定比LinkedList效率高
	   经测试
         10w以内LinkedList比ArrayList快
		 100w以上ArrayList明显比LinkedList

删除元素
  头部删除:
    头部删除LinkedList比ArrayList快
  尾部删除:
    尾部删除ArrayList比LinkedList快
 
数据查询
  使用for循环遍历时
   ArrayList的效率高于LinkedList
    而
   LinkedList的效率极低
  
  使用foreach遍历时
    ArrayList的效率和LinkedList相差不大
	   所以需避免使用for循环遍历LinkedList集合