ArrayList 和 LinkedList 的区别

ArrayList 和 LinkedList 的区别

• ArrayList基于动态数组实现的非线程安全的集合；LinkedList基于链表实现的非线程安全的集合。
• 对于随机index访问的get和set方法，一般ArrayList的速度要优于LinkedList。因为ArrayList直接通过数组下标直接找到元素；LinkedList要移动指针遍历每个元素直到找到为止。
• 新增和删除元素，一般LinkedList的速度要优于ArrayList。因为ArrayList在新增和删除元素时，可能扩容和复制数组；LinkedList实例化对象需要时间外，只需要修改指针即可。
• LinkedList集合不支持 高效的随机随机访问（RandomAccess）
• ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间

测试代码

public static void main(String[] args) {
		ArrayList<Integer> arrayList = new ArrayList<Integer>();
		LinkedList<Integer> linkedList = new LinkedList<Integer>();
		int size = 10000 * 1000;
		int index = 5000 * 1000;
		
		System.out.println("arrayList add " + size);
		addData(arrayList, size);
		System.out.println("linkedList add " +  + size);
		addData(linkedList, size);
		System.out.println();
		
		System.out.println("arrayList get " + index + " th");
		getIndex(arrayList, index);
		System.out.println("linkedList get " + index + " th");
		getIndex(linkedList, index);
		System.out.println();
		
		System.out.println("arrayList set " + index + " th");
		setIndex(arrayList, index);
		System.out.println("linkedList set " + index + " th");
		setIndex(linkedList, index);
		System.out.println();
		
		System.out.println("arrayList add " + index + " th");
		addIndex(arrayList, index);
		System.out.println("linkedList add " + index + " th");
		addIndex(linkedList, index);
		System.out.println();
		
		System.out.println("arrayList remove " + index + " th");
		removeIndex(arrayList, index);
		System.out.println("linkedList remove " + index + " th");
		removeIndex(linkedList, index);
		System.out.println();
		
		System.out.println("arrayList remove Object " + index);
		removeObject(arrayList, (Object)index);
		System.out.println("linkedList remove Object " + index);
		removeObject(linkedList, (Object)index);
		System.out.println();
		
		System.out.println("arrayList add");
		add(arrayList);
		System.out.println("linkedList add");
		add(linkedList);
		System.out.println();
		
		System.out.println("arrayList foreach");
		foreach(arrayList);
		System.out.println("linkedList foreach");
		foreach(linkedList);
		System.out.println();
		
		System.out.println("arrayList forSize");
		forSize(arrayList);
		System.out.println("linkedList forSize");
//		forSize(linkedList);
		System.out.println("cost time: ...");
		System.out.println();
		
		System.out.println("arrayList iterator");
		ite(arrayList);
		System.out.println("linkedList iterator");
		ite(linkedList);
	}
	
	private static void addData(List<Integer> list, int size) {
		long s1 = System.currentTimeMillis();
		for (int i = 0; i < size; i++) {
			list.add(i);
		}
		long s2 = System.currentTimeMillis();
		System.out.println("cost time: " + (s2-s1));
	}
	
	private static void getIndex(List<Integer> list, int index) {
		long s1 = System.currentTimeMillis();
		list.get(index);
		long s2 = System.currentTimeMillis();
		System.out.println("cost time: " + (s2-s1));
	}
	
	private static void setIndex(List<Integer> list, int index) {
		long s1 = System.currentTimeMillis();
		list.set(index, 1024);
		long s2 = System.currentTimeMillis();
		System.out.println("cost time: " + (s2-s1));
	}
	
	private static void addIndex(List<Integer> list, int index) {
		long s1 = System.currentTimeMillis();
		list.add(index, 1024);
		long s2 = System.currentTimeMillis();
		System.out.println("cost time: " + (s2-s1));
	}
	
	private static void removeIndex(List<Integer> list, int index) {
		long s1 = System.currentTimeMillis();
		list.remove(index);
		long s2 = System.currentTimeMillis();
		System.out.println("cost time: " + (s2-s1));
	}
	
	private static void removeObject(List<Integer> list, Object obj) {
		long s1 = System.currentTimeMillis();
		list.remove(obj);
		long s2 = System.currentTimeMillis();
		System.out.println("cost time: " + (s2-s1));
	}
	
	private static void add(List<Integer> list) {
		long s1 = System.currentTimeMillis();
		list.add(1024);
		long s2 = System.currentTimeMillis();
		System.out.println("cost time: " + (s2-s1));
	}
	
	private static void foreach(List<Integer> list) {
		long s1 = System.currentTimeMillis();
		for (Integer i : list) {
			//do nothing
		}
		long s2 = System.currentTimeMillis();
		System.out.println("cost time: " + (s2-s1));
	}
	
	private static void forSize(List<Integer> list) {
		long s1 = System.currentTimeMillis();
		int size = list.size();
		for (int i = 0; i < size; i++) {
			list.get(i);
		}
		long s2 = System.currentTimeMillis();
		System.out.println("cost time: " + (s2-s1));
	}
	
	private static void ite(List<Integer> list) {
		long s1 = System.currentTimeMillis();
		Iterator<Integer> ite = list.iterator();
		while (ite.hasNext()) {
			ite.next();
		}
		long s2 = System.currentTimeMillis();
		System.out.println("cost time: " + (s2-s1));
	}

JDK1.8，win7 64位。结果

arrayList add 10000000
cost time: 3309
linkedList add 10000000
cost time: 1375

arrayList get 5000000 th
cost time: 0
linkedList get 5000000 th
cost time: 53

arrayList set 5000000 th
cost time: 0
linkedList set 5000000 th
cost time: 44

arrayList add 5000000 th
cost time: 3
linkedList add 5000000 th
cost time: 45

arrayList remove 5000000 th
cost time: 3
linkedList remove 5000000 th
cost time: 46

arrayList remove Object 5000000
cost time: 31
linkedList remove Object 5000000
cost time: 131

arrayList add
cost time: 0
linkedList add
cost time: 0

arrayList foreach
cost time: 30
linkedList foreach
cost time: 128

arrayList forSize
cost time: 5
linkedList forSize
cost time: ...

arrayList iterator
cost time: 6
linkedList iterator
cost time: 113

 思考：

• arrayList add 10000000 cost time: 3293；linkedList add 10000000 cost time: 1337
  arrayList add 1000000  cost time: 22  ；   linkedList add 1000000   cost time: 1011
  跑另外一组数据，size设为1000 * 1000，得出当size增加，ArrayList的add操作的累计时间增长更快
• 千万别在循环中调用LinkedList的get方法，耗时会让你崩溃
• 代码例子中，"新增和删除元素，一般LinkedList的速度要优于ArrayList"并不成立，可以思考一下原因。

源码分析参考：

https://blog.csdn.net/luyuqin0115/article/details/80395694

【Java面试题与答案】整理推荐

• 基础与语法
• 集合
• 网络编程
• 并发编程
• Web
• 安全
• 设计模式
• 框架
• 算法与数据结构
• 异常
• 文件解析与生成
• Linux
• MySQL
• Oracle
• Redis
• Dubbo