ArrayList和LinkedList的大致区别：
- ArrayList基于动态数组的数据结构，LinkedList基于链表的数据结构。
- 对于随机访问的get和set，ArrayList优于LinkedList，因为LinkedList要移动指针。
- 对于新增add和删除remove操作，LinkedList优于ArrayList，因为ArrayList要移动数据。
接下来看下具体的demo，来比较下两者的性能。
public class ListDemo {
public static final int N=50000;
public static List values;
public static void main(String args[]){
create();
System.out.println("ArrayList消耗时间："+removeTime(new ArrayList(values)));
System.out.println("LinkedList消耗时间："+removeTime(new LinkedList(values)));
}
static void create(){
Integer vals[]=new Integer[N];
Random r=new Random();
for(int i=0,currentVal=0;i<N;i++){
vals[i] = currentVal;
currentVal+=r.nextInt(100)+1;
}
values=Arrays.asList(vals);
}
/**
* 比较 get随机访问 arrayList 优于 linkedList
* 二分查找法使用的随机访问(random access)策略，而LinkedList是不支持快速的随机访问的。对一个LinkedList做随机访问所消耗的时间与这个list的大小是成比例的。而相应的，在ArrayList中进行随机访问所消耗的时间是固定的
* @param lst
* @return
*/
static long getTime(List lst){
long start=System.currentTimeMillis();
for(int i=0;i<N;i++){
int index=Collections.binarySearch(lst, values.get(i));
if(index!=i)
System.out.println("***错误***");
}
return System.currentTimeMillis()-start;
}
/**
* 比较 重复的在一个列表的开端插入一个元素 linkedList 优于 arrayList
* 利用Collections.reverse方法对列表进行反转时，linkedList性能就要好些。
* 当一个元素被加到ArrayList的最开端时，所有已经存在的元素都会后移，这就意味着数据移动和复制上的开销。相反的，将一个元素加到LinkedList的最开端只是简单的未这个元素分配一个记录，然后调整两个连接。在LinkedList的开端增加一个元素的开销是固定的，而在ArrayList的开端增加一个元素的开销是与ArrayList的大小成比例的。
* @param list
* @return
*/
static long addTime(List list){
long start=System.currentTimeMillis();
Object o = new Object();
for(int i=0;i<N;i++){
list.add(0, o);
}
return System.currentTimeMillis()-start;
}
static long removeTime(List list){
long start=System.currentTimeMillis();
Object o = new Object();
for(int i=0;i<N;i++){
list.remove(0);
}
return System.currentTimeMillis()-start;
}
}
从demo数据的比较，可以看到arrayList & linkedList在性能上各有优缺点。
- 两者在列表末尾增加一个元素，所花的开销都是固定的。对ArrayList而言，会在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；对LinkedList而言，这个开销是统一的，会分配一个内部Entry对象。
- 在ArrayList的中间插入或删除一个元素时，这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。
- LinkedList不支持高效的随机元素访问。
- ArrayList的空间浪费主要体现在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个单元都需要消耗相当的空间。
