SDK提供了有序集合接口java.util.List的幾種實現，其中三種最為人們熟知的是Vector、ArrayList和LinkedList。有關這些List類的性能差別是一個經常被問及的問題。在這篇文章中，我要探討的就是LinkedList和Vector/ArrayList之間的性能差異。
為全面分析這些類之間的性能差異，我們必須知道它們的實現方法。因此，接下來我首先從性能的角度出發，簡要介紹這些類的實現特點。
一、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);
}
}
文章來源于領測軟件測試網 http://www.k11sc111.com/
