Java 集合系列08： List總結(LinkedList, ArrayList等使用場景和性能分析)
- 2019 年 10 月 5 日
- 筆記
第1部分 List概括
先回顧一下List的框架圖
這裡寫圖片描述 (01) List 是一個介面，它繼承於Collection的介面。它代表著有序的隊列。 (02) AbstractList 是一個抽象類，它繼承於AbstractCollection。AbstractList實現List介面中除size()、get(int location)之外的函數。 (03) AbstractSequentialList 是一個抽象類，它繼承於AbstractList。AbstractSequentialList 實現了「鏈表中，根據index索引值操作鏈表的全部函數」。
(04) ArrayList, LinkedList, Vector, Stack是List的4個實現類。 ArrayList 是一個數組隊列，相當於動態數組。它由數組實現，隨機訪問效率高，隨機插入、隨機刪除效率低。 LinkedList 是一個雙向鏈表。它也可以被當作堆棧、隊列或雙端隊列進行操作。LinkedList隨機訪問效率低，但隨機插入、隨機刪除效率低。 Vector 是矢量隊列，和ArrayList一樣，它也是一個動態數組，由數組實現。但是ArrayList是非執行緒安全的，而Vector是執行緒安全的。 Stack 是棧，它繼承於Vector。它的特性是：先進後出(FILO, First In Last Out)。
第2部分 List使用場景
學東西的最終目的是為了能夠理解、使用它。下面先概括的說明一下各個List的使用場景，後面再分析原因。
如果涉及到「棧」、「隊列」、「鏈表」等操作，應該考慮用List，具體的選擇哪個List，根據下面的標準來取捨。 (01) 對於需要快速插入，刪除元素，應該使用LinkedList。 (02) 對於需要快速隨機訪問元素，應該使用ArrayList。 (03) 對於「單執行緒環境」 或者 「多執行緒環境，但List僅僅只會被單個執行緒操作」，此時應該使用非同步的類(如ArrayList)。 對於「多執行緒環境，且List可能同時被多個執行緒操作」，此時，應該使用同步的類(如Vector)。
通過下面的測試程式，我們來驗證上面的(01)和(02)結論。參考程式碼如下：
import java.util.*; import java.lang.Class; /* * @desc 對比ArrayList和LinkedList的插入、隨機讀取效率、刪除的效率 * * @author skywang */ public class ListCompareTest { private static final int COUNT = ; private static LinkedList linkedList = new LinkedList(); private static ArrayList arrayList = new ArrayList(); private static Vector vector = new Vector(); private static Stack stack = new Stack(); public static void main(String[] args) { // 換行符 System.out.println(); // 插入 insertByPosition(stack) ; insertByPosition(vector) ; insertByPosition(linkedList) ; insertByPosition(arrayList) ; // 換行符 System.out.println(); // 隨機讀取 readByPosition(stack); readByPosition(vector); readByPosition(linkedList); readByPosition(arrayList); // 換行符 System.out.println(); // 刪除 deleteByPosition(stack); deleteByPosition(vector); deleteByPosition(linkedList); deleteByPosition(arrayList); } // 獲取list的名稱 private static String getListName(List list) { if (list instanceof LinkedList) { return "LinkedList"; } else if (list instanceof ArrayList) { return "ArrayList"; } else if (list instanceof Stack) { return "Stack"; } else if (list instanceof Vector) { return "Vector"; } else { return "List"; } } // 向list的指定位置插入COUNT個元素，並統計時間 private static void insertByPosition(List list) { long startTime = System.currentTimeMillis(); // 向list的位置0插入COUNT個數 for (int i=; i<COUNT; i++) list.add(, i); long endTime = System.currentTimeMillis(); long interval = endTime - startTime; System.out.println(getListName(list) + " : insert "+COUNT+" elements into the 1st position use time：" + interval+" ms"); } // 從list的指定位置刪除COUNT個元素，並統計時間 private static void deleteByPosition(List list) { long startTime = System.currentTimeMillis(); // 刪除list第一個位置元素 for (int i=; i<COUNT; i++) list.remove(); long endTime = System.currentTimeMillis(); long interval = endTime - startTime; System.out.println(getListName(list) + " : delete "+COUNT+" elements from the 1st position use time：" + interval+" ms"); } // 根據position，不斷從list中讀取元素，並統計時間 private static void readByPosition(List list) { long startTime = System.currentTimeMillis(); // 讀取list元素 for (int i=; i<COUNT; i++) list.get(i); long endTime = System.currentTimeMillis(); long interval = endTime - startTime; System.out.println(getListName(list) + " : read "+COUNT+" elements by position use time：" + interval+" ms"); } }
運行結果如下：
Stack : insert elements into the st position use time： ms Vector : insert elements into the st position use time： ms LinkedList : insert elements into the st position use time： ms ArrayList : insert elements into the st position use time： ms Stack : read elements by position use time： ms Vector : read elements by position use time： ms LinkedList : read elements by position use time： ms ArrayList : read elements by position use time： ms Stack : delete elements from the st position use time： ms Vector : delete elements from the st position use time： ms LinkedList : delete elements from the st position use time： ms ArrayList : delete elements from the st position use time： ms
從中，我們可以發現： 插入10萬個元素，LinkedList所花時間最短：29ms。 刪除10萬個元素，LinkedList所花時間最短：15ms。 遍歷10萬個元素，LinkedList所花時間最長：10809 ms；而ArrayList、Stack和Vector則相差不多，都只用了幾秒。
考慮到Vector是支援同步的，而Stack又是繼承於Vector的；因此，得出結論： (01) 對於需要快速插入，刪除元素，應該使用LinkedList。 (02) 對於需要快速隨機訪問元素，應該使用ArrayList。 (03) 對於「單執行緒環境」 或者 「多執行緒環境，但List僅僅只會被單個執行緒操作」，此時應該使用非同步的類。
第3部分 LinkedList和ArrayList性能差異分析
下面我們看看為什麼LinkedList中插入元素很快，而ArrayList中插入元素很慢！
LinkedList.java中向指定位置插入元素的程式碼如下：
// 在index前添加節點，且節點的值為element public void add(int index, E element) { addBefore(element, (index==size ? header : entry(index))); } // 獲取雙向鏈表中指定位置的節點 private Entry<E> entry(int index) { if (index < || index >= size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry<E> e = header; // 獲取index處的節點。 // 若index < 雙向鏈表長度的1/2,則從前向後查找; // 否則，從後向前查找。 if (index < (size >> )) { for (int i = ; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e; } // 將節點(節點數據是e)添加到entry節點之前。 private Entry<E> addBefore(E e, Entry<E> entry) { // 新建節點newEntry，將newEntry插入到節點e之前；並且設置newEntry的數據是e Entry<E> newEntry = new Entry<E>(e, entry, entry.previous); // 插入newEntry到鏈表中 newEntry.previous.next = newEntry; newEntry.next.previous = newEntry; size++; modCount++; return newEntry; }
從中，我們可以看出：通過add(int index, E element)向LinkedList插入元素時。先是在雙向鏈表中找到要插入節點的位置index；找到之後，再插入一個新節點。 雙向鏈表查找index位置的節點時，有一個加速動作：若index < 雙向鏈表長度的1/2，則從前向後查找; 否則，從後向前查找。
接著，我們看看ArrayList.java中向指定位置插入元素的程式碼。如下：
// 將e添加到ArrayList的指定位置 public void add(int index, E element) { if (index > size || index < ) throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size); ensureCapacity(size+); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + , size - index); elementData[index] = element; size++; }
ensureCapacity(size+1) 的作用是「確認ArrayList的容量，若容量不夠，則增加容量。」 真正耗時的操作是 System.arraycopy(elementData, index, elementData, index + 1, size - index);
Sun JDK包的java/lang/System.java中的arraycopy()聲明如下：
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
arraycopy()是個JNI函數，它是在JVM中實現的。sunJDK中看不到源碼，不過可以在OpenJDK包中看到的源碼。 實際上，我們只需要了解： System.arraycopy(elementData, index, elementData, index + 1, size - index); 會移動index之後所有元素即可。這就意味著，ArrayList的add(int index, E element)函數，會引起index之後所有元素的改變！
通過上面的分析，我們就能理解為什麼LinkedList中插入元素很快，而ArrayList中插入元素很慢。 「刪除元素」與「插入元素」的原理類似，這裡就不再過多說明。
接下來，我們看看 「為什麼LinkedList中隨機訪問很慢，而ArrayList中隨機訪問很快」。
先看看LinkedList隨機訪問的程式碼
// 返回LinkedList指定位置的元素 public E get(int index) { return entry(index).element; } // 獲取雙向鏈表中指定位置的節點 private Entry<E> entry(int index) { if (index < || index >= size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry<E> e = header; // 獲取index處的節點。 // 若index < 雙向鏈表長度的1/2,則從前先後查找; // 否則，從後向前查找。 if (index < (size >> )) { for (int i = ; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e; }
從中，我們可以看出：通過get(int index)獲取LinkedList第index個元素時。先是在雙向鏈表中找到要index位置的元素；找到之後再返回。 雙向鏈表查找index位置的節點時，有一個加速動作：若index < 雙向鏈表長度的1/2，則從前向後查找; 否則，從後向前查找。
下面看看ArrayList隨機訪問的程式碼
// 獲取index位置的元素值 public E get(int index) { RangeCheck(index); return (E) elementData[index]; } private void RangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size); }
從中，我們可以看出：通過get(int index)獲取ArrayList第index個元素時。直接返回數組中index位置的元素，而不需要像LinkedList一樣進行查找。
第4部分 Vector和ArrayList比較
相同之處
1 它們都是List
它們都繼承於AbstractList，並且實現List介面。 ArrayList和Vector的類定義如下：
// ArrayList的定義 public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable // Vector的定義 public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}
2 它們都實現了RandomAccess和Cloneable介面
實現RandomAccess介面，意味著它們都支援快速隨機訪問； 實現Cloneable介面，意味著它們能克隆自己。
3 它們都是通過數組實現的，本質上都是動態數組
ArrayList.java中定義數組elementData用於保存元素
// 保存ArrayList中數據的數組 private transient Object[] elementData;
Vector.java中也定義了數組elementData用於保存元素
// 保存Vector中數據的數組 protected Object[] elementData;
4 它們的默認數組容量是10
若創建ArrayList或Vector時，沒指定容量大小；則使用默認容量大小10。
ArrayList的默認構造函數如下：
// ArrayList構造函數。默認容量是10。 public ArrayList() { this(); }
Vector的默認構造函數如下：
// Vector構造函數。默認容量是10。 public Vector() { this(); }
5 它們都支援Iterator和listIterator遍歷
它們都繼承於AbstractList，而AbstractList中分別實現了 「iterator()介面返回Iterator迭代器」 和 「listIterator()返回ListIterator迭代器」。
不同之處
1 執行緒安全性不一樣
ArrayList是非執行緒安全； 而Vector是執行緒安全的，它的函數都是synchronized的，即都是支援同步的。 ArrayList適用於單執行緒，Vector適用於多執行緒。
2 對序列化支援不同
ArrayList支援序列化，而Vector不支援；即ArrayList有實現java.io.Serializable介面，而Vector沒有實現該介面。
3 構造函數個數不同 ArrayList有3個構造函數，而Vector有4個構造函數。Vector除了包括和ArrayList類似的3個構造函數之外，另外的一個構造函數可以指定容量增加係數。
ArrayList的構造函數如下：
// 默認構造函數 ArrayList() // capacity是ArrayList的默認容量大小。當由於增加數據導致容量不足時，容量會添加上一次容量大小的一半。 ArrayList(int capacity) // 創建一個包含collection的ArrayList ArrayList(Collection<? extends E> collection)
Vector的構造函數如下：
// 默認構造函數 Vector() // capacity是Vector的默認容量大小。當由於增加數據導致容量增加時，每次容量會增加一倍。 Vector(int capacity) // 創建一個包含collection的Vector Vector(Collection<? extends E> collection) // capacity是Vector的默認容量大小，capacityIncrement是每次Vector容量增加時的增量值。 Vector(int capacity, int capacityIncrement)
4 容量增加方式不同
逐個添加元素時，若ArrayList容量不足時，「新的容量」=「(原始容量x3)/2 + 1」。 而Vector的容量增長與「增長係數有關」，若指定了「增長係數」，且「增長係數有效(即，大於0)」；那麼，每次容量不足時，「新的容量」=「原始容量+增長係數」。若增長係數無效(即，小於/等於0)，則「新的容量」=「原始容量 x 2」。
ArrayList中容量增長的主要函數如下：
public void ensureCapacity(int minCapacity) { // 將「修改統計數」+1 modCount++; int oldCapacity = elementData.length; // 若當前容量不足以容納當前的元素個數，設置 新的容量=「(原始容量x3)/2 + 1」 if (minCapacity > oldCapacity) { Object oldData[] = elementData; int newCapacity = (oldCapacity * )/ + ; if (newCapacity < minCapacity) newCapacity = minCapacity; elementData = Arrays.copyOf(elementData, newCapacity); } }
Vector中容量增長的主要函數如下：
private void ensureCapacityHelper(int minCapacity) { int oldCapacity = elementData.length; // 當Vector的容量不足以容納當前的全部元素，增加容量大小。 // 若 容量增量係數>0(即capacityIncrement>0)，則將容量增大當capacityIncrement // 否則，將容量增大一倍。 if (minCapacity > oldCapacity) { Object[] oldData = elementData; int newCapacity = (capacityIncrement > ) ? (oldCapacity + capacityIncrement) : (oldCapacity * ); if (newCapacity < minCapacity) { newCapacity = minCapacity; } elementData = Arrays.copyOf(elementData, newCapacity); } }
5 對Enumeration的支援不同。Vector支援通過Enumeration去遍歷，而List不支援
Vector中實現Enumeration的程式碼如下：
public Enumeration<E> elements() { // 通過匿名類實現Enumeration return new Enumeration<E>() { int count = ; // 是否存在下一個元素 public boolean hasMoreElements() { return count < elementCount; } // 獲取下一個元素 public E nextElement() { synchronized (Vector.this) { if (count < elementCount) { return (E)elementData[count++]; } } throw new NoSuchElementException("Vector Enumeration"); } }; }
出處：http://www.cnblogs.com/skywang12345/p/3308900.html
