JDK提供了一組主要的數據結構的實現，如List、Set、Map等常用結構，這些結構都繼承自java.util.collection接口。
List接口
List有三種不同的實現，ArrayList和Vector使用數組實現，其封裝了對內部數組的操作。LinkedList使用了循環雙向鏈表的數據結構，LinkedList鏈表是由一系列的鏈表項連接而成，一個鏈表項包括三部分：鏈表內容、前驅表項和後驅表項。
LinkedList的表項結構如圖：
LinkedList表項間的連接關系如圖：
可以看出，無論LinkedList是否為空，鏈表都有一個header表項，它即表示鏈表的開頭也表示鏈表的結尾。表項header的後驅表項便是鏈表的第一個元素，其前驅表項就是鏈表的最後一個元素。
對基於鏈表和基於數組的兩種List的不同實現做一些比較：
1、增加元素到列表的末尾：
在ArrayList中源代碼如下：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
add()方法性能的好壞取決於grow()方法的性能：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
可以看出，當ArrayList對容量的需求超過當前數組的大小是，會進行數組擴容，擴容的過程中需要大量的數組復制，數組復制調用System.arraycopy（）方法，操作效率是非常快的。
在LinkedList源碼中add()方法：
public boolean add(E e) {
linkLast(e);
return true;
}
linkLast（）方法如下：
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
LinkedList是基於鏈表實現，因此不需要維護容量大小，但是每次都新增元素都要新建一個Node對象，並進行一系列賦值，在頻繁系統調用中，對系統性能有一定影響。性能測試得出，在列表末尾增加元素，ArrayList比LinkedList性能要好，因為數組是連續的，在末尾增加元素，只有在空間不足時才會進行數組擴容，大部分情況下追加操作效率還是比較高的。
更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2016-03/129625p2.htm
