ArrayList和LinkedList比较——java技术栈系列文章

IT黑名单 2016-12-13 17:04:21

目录

SkipList在java的API里实现分别是:
ConcurrentSkipListMap(在功能上对应HashTable、HashMap、TreeMap);
ConcurrentSkipListSet(在功能上对应HashSet)
SkipList更像Java中的TreeMap,TreeMap基于红黑树(一种自平衡二叉查找树)实现的,时间复杂度平均能达到O(log n)。本文主要比较ArrayList和LinkedList。

在搜索引擎搜索ArrayList和LinkedList,很容易得到这样的结果:

1、ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。
2、对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。
3、对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。

标红部分并不总是如此,在下文解释
ArrayList 是一个可改变大小的数组。当更多的元素加入到ArrayList中时,其大小将会动态地增长。内部的元素可以直接通过get与set方法进行访问,因为ArrayList本质上就是一个数组。
LinkedList 是一个双链表,在get与set方面弱于ArrayList。
两者的对比都是在数据量很大或者操作很频繁的情况下的对比,如果数据和运算量很小,那么对比将失去意义。

性能比较

package com.blacklist.demo;

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

public class Test {
	static String str = "abc";
	private static void init(List<String> link, List<String> array) {
		link.clear();
		array.clear();
		for (int i = 0; i < 1000000; i++) {
			link.add(str);
			array.add(str);
		}
	}
	public static void main(String[] args) {
		List<String> link = new LinkedList<String>();
		List<String> array = new ArrayList<String>();
		
		init(link, array);
		System.out.println("linked get:"+get(link));
		System.out.println("array get:"+get(array));
		init(link, array);
		System.out.println("linked times insert:"+insert(link, 1000000));
		System.out.println("array times insert:"+insert(array, 1000000));
		init(link, array);
		System.out.println("linked insert index:"+insertIndex(link, 10000));
		System.out.println("array insert index:"+insertIndex(array, 10000));
		init(link, array);
		System.out.println("linked insert index:"+insertIndex(link, 600000));
		System.out.println("array insert index:"+insertIndex(array, 600000));
	}
	private static long get(List<String> list) {
		long begin = System.currentTimeMillis();
		for(int i=0;i<10000;i++)
			list.get(i);
		return System.currentTimeMillis() - begin;
	}
	private static long insert(List<String> list, int num) {
		long begin = System.currentTimeMillis();
		for(int i=0;i<num;i++)
			list.add(str);
		return System.currentTimeMillis() - begin;
	}
	private static long insertIndex(List<String> list, int index) {
		if(index >= list.size()) {
			System.out.println("index out...");
			index = list.size()-1;
		}
		long begin = System.currentTimeMillis();
		for(int i=0;i<10000;i++)
			list.add(index, str);
		return System.currentTimeMillis() - begin;
	}
}
执行结果:
linked get:125
array get:1
linked times insert:157
array times insert:46
linked insert index:295
array insert index:5136
linked insert index:15707
array insert index:1099

可以看出:

1、ArrayList是基于对象数组的,LinkedList是按顺序从列表一段到另一端检查,所以访问列表中的任意一个元素时(random access),ArrayList的速度要比LinkedList快;
2、在进行插入操作时,
LinkedList并没有表现出其优势,反而不如ArrayList;
3、指定位置插入操作,在
表头插入时LinkedList优于ArrayList;
4、指定位置插入操作,在表尾插入时
LinkedList性能低于ArrayList(即使ArrayList在插入时有调整容量大小的开销);
以上基于jdk
1.8.0_91

适用场景:

1、操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能;
2、操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,LinkedList更优。


转载请注明来源【IT黑名单

本文链接:http://blog.itblacklist.cn/20161213/8439.html

© Copyright 2016 IT黑名单 Inc.All Rights Reserved. 豫ICP备15018592号-2