Java 中Vector、ArrayList和LinkedList 的区别[转]

转：http://pterodactyl.iteye.com/blog/617799

 

SDK 提供了有序集合接口java.util.List的几种实现，其中三种最为人们熟知的是Vector、ArrayList和LinkedList。有关这 些List类的性能差别是一个经常被问及的问题。在这篇文章中，我要探讨的就是LinkedList和Vector/Array

为全面分析这些类之间的性能差异，我们必须知道它们的实现方法。因此，接下来我首先从性能的角度出发，简要介绍这些类的实现特点。

一、Vector和ArrayList的实现
Vector和ArrayList都带有一个底层的Object[]数组，这个Object[]数组用来保存元素。通过索引访问元素时，只需简单地通过索引访问内部数组的元素：
public Object get(int index)
{ //首先检查index是否合法...此处不显示这部分代码 return
elementData[index]; }

 

内部数组可以大于Vector/ArrayList对象拥有元素的数量，两者的差值作为剩余空间，以便实现快速添加新元素。有了剩余空间，添加元素变得非常简单，只需把新的元素保存到内部数组中的一个空余的位置，然后为新的空余位置增加索引值：
public boolean add(Object o)
{ ensureCapacity(size + 1); //稍后介绍 elementData[size++] = o; return true;
//List.add(Object) 的返回值 }

把元素插入集合中任意指定的位置（而不是集合的末尾）略微复杂一点：插入点之上的所有数组元素都必须向前移动一个位置，然后才能进行赋值：
public void add(int index, Object element) {
//首先检查index是否合法...此处不显示这部分代码
ensureCapacity(size+1);
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}

剩 余空间被用光时，如果需要加入更多的元素，Vector/ArrayList对象必须用一个更大的新数组替换其内部Object[]数组，把所有的数组元 素复制到新的数组。根据SDK版本的不同，新的数组要比原来的大50%或者100%（下面显示的代码把数组扩大100%）：
public void ensureCapacity(int minCapacity) {
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = Math.max(oldCapacity * 2, minCapacity);
elementData = new Object[newCapacity];
System.arraycopy(oldData, 0, elementData, 0, size);
}
}

Vector 类和ArrayList类的主要不同之处在于同步。除了两个只用于串行化的方法，没有一个ArrayList的方法具有同步执行的能力；相反， Vector的大多数方法具有同步能力，或直接或间接。因此，Vector是线程安全的，但ArrayList不是。这使得ArrayList要比 Vector快速。对于一些最新的JVM，两个类在速度上的差异可以忽略不计：严格地说，对于这些JVM，这两个类在速度上的差异小于比较这些类性能的测 试所显示的时间差异。

通过索引访问和更新元素时，Vector和ArrayList的实现有着卓越的性能，因为不存在除范围检查之外的 其他开销。除非内部数组空间耗尽必须进行扩展，否则，向列表的末尾添加元素或者从列表的末尾删除元素时，都同样有着优秀的性能。插入元素和删除元素总是要 进行数组复制（当数组先必须进行扩展时，需要两次复制）。被复制元素的数量和[size-index]成比例，即和插入/删除点到集合中最后索引位置之间 的距离成比例。对于插入操作，把元素插入到集合最前面（索引0）时性能最差，插入到集合最后面时（最后一个现有元素之后）时性能最好。随着集合规模的增 大，数组复制的开销也迅速增加，因为每次插入操作必须复制的元素数量增加了。

二、LinkedList的实现
LinkedList通过一个双向链接的节点列表实现。要通过索引访问元素，你必须查找所有节点，直至找到目标节点：
public Object get(intindex) {
//首先检查index是否合法...此处不显示这部分代码
Entry e = header; //开始节点
//向前或者向后查找，具体由哪一个方向距离较
//近决定
if (index < size/2) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}

把元素插入列表很简单：找到指定索引的节点，然后紧靠该节点之前插入一个新节点：
public void add(int index, Object element) {
//首先检查index是否合法...此处不显示这部分代码
Entry e = header; //starting node
//向前或者向后查找，具体由哪一个方向距离较
//近决定
if (index < size/2) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
Entry newEntry = new Entry(element, e, e.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
}

线程安全的LinkedList和其他集合
如 果要从Java SDK得到一个线程安全的LinkedList，你可以利用一个同步封装器从Collections.synchronizedList(List)得到 一个。然而，使用同步封装器相当于加入了一个间接层，它会带来昂贵的性能代价。当封装器把调用传递给被封装的方法时，每一个方法都需要增加一次额外的方法 调用，经过同步封装器封装的方法会比未经封装的方法慢二到三倍。对于象搜索之类的复杂操作，这种间接调用所带来的开销不是很突出；但对于比较简单的方法， 比如访问功能或者更新功能，这种开销可能对性能造成严重的影响。

这意味着，和Vector相比，经过同步封装的LinkedList在 性能上处于显著的劣势，因为Vector不需要为了线程安全而进行任何额外的间接调用。如果你想要有一个线程安全的LinkedList，你可以复制 LinkedList类并让几个必要的方法同步，这样你可以得到一个速度更快的实现。对于所有其它集合类，这一点都同样有效：只有List和Map具有高 效的线程安全实现（分别是Vector和Hashtable类）。有趣的是，这两个高效的线程安全类的存在只是为了向后兼容，而不是出于性能上的考虑。

对于通过索引访问和更新元素，LinkedList实现的性能开销略大一点，因为访问任意一个索引都要求跨越多个节点。插入元素时除了有跨 越多个节点的性能开销之外，还要有另外一个开销，即创建节点对象的开销。在优势方面，LinkedList实现的插入和删除操作没有其他开销，因此，插入 -删除开销几乎完全依赖于插入-删除点离集合末尾的远近。

ArrayList和Vector通常比LinkedList和同步 封装之后的LinkedList有着更好的性能。即使在你认为LinkedList可能提供更高性能的情况下，你也可以通过修改元素加入的方式从 ArrayList争取更好的性能，例如翻转集合元素的次序。

有些情况下LinkedList会有更好的性能，例如，当大量元素需要同 时加入到大型集合的开头和末尾时。但一般而言，我建议你优先使用ArrayList/Vector类，只有当它们存在明显的性能问题而 LinkedList能够改进性能时，才使用LinkedList。

 

arraylist：封装了一个底层的Object[]，查找更新很快，添加较慢，具体看在什么位置添加。但线程不同步。操作比vector要快。

vector：封装了一个底层的Object[]，查找更新很快，添加较慢，具体看在什么位置添加。线程同步。

linklist：双向链表结构，添加很快，查找慢。线程不同步。