摘 要 ArrayList和LinkedList都是实现了List接口的容器类，用于存储一系列的对象引用。他们都可以对元素的增删改查进行操作。本文通过时间复杂度、空间复杂度来说明一下他们性能区别及应用场景。

关键词Java List;ArrayList;LinkedList

概述

List 是一个有序、可重复的集合，集合中每个元素都有其对应的顺序索引。它主要有两个常用的实现类：ArrayList 类和LinkedList 类。

ArrayList 类实现了可变数组的大小，存储在内的数据称为元素。使用 ArrayList 创建的集合，允许对集合中的元素进行快速的随机访问，不过，向 ArrayList 中插入与删除元素的速度相对较慢。

LinkedList 类采用链表结构保存对象。需要频繁向集合中插入和删除元素时，使用 LinkedList 类比 ArrayList 类效果高，但是 LinkedList 类随机访问元素的速度则相对较慢。

1时间复杂度

假设我们有一个很大的列表，它里面的元素已经排好序了，这个列表可能是ArrayList类型的也可能是LinkedList类型的，现在我们对这个列表来进行二分查找（binary search），比较列表是ArrayList和LinkedList时的查询速度，看下面的程序：

public class TestList ...{

public static final int N=50000;

public static List values;

static...{

Integer vals[]=new Integer[N];

Random r=new Random（）;

for（int i=0，currval=0;i

vals=new Integer（currval）;

currval+=r.nextInt（100）+1;

}

values=Arrays.asList（vals）;

}

static long timeList（List lst）...{

long start=System.currentTimeMillis（）;

for（int i=0;i

int index=Collections.binarySearch（lst， values.get（i））;

if（index！=i）

System.out.println（“***錯误***”）;

}

return System.currentTimeMillis（）-start;

}

public static void main（String args[]）...{

System.out.println（“ArrayList消耗时间：”+timeList（new ArrayList（values）））;

System.out.println（“LinkedList消耗时间：”+timeList（new LinkedList（values）））;

}

}

输出是：ArrayList消耗时间：15

LinkedList消耗时间：2596

这个结果不是固定的，但是基本上ArrayList的时间要明显小于LinkedList的时间。因此在这种情况下不宜用LinkedList。

2空间复杂度

在LinkedList中有一个私有的内部类，定义如下：

private static class Entry {

Object element;

Entry next;

Entry previous;

}

每个Entry对象reference列表中的一个元素，同时还有在LinkedList中它的上一个元素和下一个元素。一个有1000个元素的LinkedList对象将有1000个链接在一起的Entry对象，每个对象都对应于列表中的一个元素。这样的话，在一个LinkedList结构中将有一个很大的空间开销，因为它要存储这1000个Entity对象的相关信息。

ArrayList使用一个内置的数组来存储元素，这个数组的起始容量是10。……