ArrayList与LinkedList特性对比

发表于: java/j2ee | 作者: | 日期: 2011/3/24 05:03

ArrayList和LinkedList是List接口的两个不同实现,实现的思想不同,应用场景也不同。以下对ArrayList和LinkedList的特性进行了一下小结,并附了部分ArrayList和LinkedList源码。

ArrayList特性:

(1)快速随机访问
内部采用一个Object数组保存数据,所以可以随机访问每个元素而不用考虑性能问题。


public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}

(2)向其中添加元素速度慢
当你创建数组是并不能确定其容量,所以当改变这个数组时就必须在内存中做很多事情:


public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3) / 2 + 1;
if (newCapacity < minCapacity) newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } }

(3)操作其中对象的速度慢
当你要想数组中任意两个元素中间添加对象时,数组需要移动所有后面的对象。


public void add(int index, E element) {
if (index > size || index < 0) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); ensureCapacity(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }

LinkedList特性

(1)操作其中对象的速度快
只需要改变链接,新的节点可以在内存中的任何地方。


public E set(int index, E element) {
Entry e = entry(index);
E oldVal = e.element;
e.element = element;
return oldVal;
}

(2)不能随机访问
虽然存在 get() 方法,但是这个方法是通过遍历接点来定位的所以速度慢。

private Entry entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException(“Index: ” + index + “, Size: ” + size);
Entry e = header;
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i–)
e = e.previous;
}
return e;
}

总结:

如果你的需求是:(1)需要频繁的随机访问容器中的数据,(2)不需要频繁的对容器中的数据进行修改或者移动,那么考虑使用ArrayList;

如果你的需要是:(1)不需要频繁的随机访问容器中的数据,(2)需要频繁的对容器中的数据进行修改或者移动,那么考虑使用LinkedList;

: https://blog.darkmi.com/2011/03/24/1737.html

本文相关评论 - 1条评论都没有呢
Post a comment now » 本文目前不可评论

No comments yet.

Sorry, the comment form is closed at this time.