更多 Java 集合類方面的文章，請參見文集《Java 集合類》
共同點(diǎn)：
- 都實(shí)現(xiàn)了 List 接口
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
public class Vector<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
- 都可以插入 null
基本區(qū)別：
-
實(shí)現(xiàn)方式：
- ArrayList 和 Vector 基于數(shù)組實(shí)現(xiàn)浦箱，可以隨機(jī)訪問搔耕，實(shí)現(xiàn)了 RandomAccess 接口
- LinkedList 基于鏈表實(shí)現(xiàn)挥等，不可隨機(jī)訪問粥惧，實(shí)現(xiàn)了 Deque 接口
-
初始容量：
- ArrayList 初始容量為 10
- Vector 初始容量為 10
- LinkedList 基于鏈表實(shí)現(xiàn)匕积，初始容量為 0
-
擴(kuò)容方式：
- ArrayList 數(shù)組容量不夠時橡卤，擴(kuò)容 50%
int newCapacity = oldCapacity + (oldCapacity >> 1); - Vector 數(shù)組容量不夠時扮念，擴(kuò)容 100%
- LinkedList 基于鏈表實(shí)現(xiàn)，無需考慮擴(kuò)容
- ArrayList 數(shù)組容量不夠時橡卤，擴(kuò)容 50%
-
是否線程安全：
- ArrayList 線程不安全
- Vector 線程安全
- LinkedList 線程不安全
ArrayList 的實(shí)現(xiàn)原理
構(gòu)造
-
public ArrayList()可以構(gòu)造一個默認(rèn)初始容量為 10 的空列表碧库；private static final int DEFAULT_CAPACITY = 10;
-
public ArrayList(int initialCapacity)構(gòu)造一個指定初始容量的空列表柜与； -
public ArrayList(Collection<? extends E> c)構(gòu)造一個包含指定 collection 的元素的列表巧勤，這些元素按照該 collection 的迭代器返回它們的順序排列的。
調(diào)整數(shù)組容量
每當(dāng)向數(shù)組中添加元素時弄匕，都要去檢查添加后元素的個數(shù)是否會超出當(dāng)前數(shù)組的長度颅悉，如果超出，數(shù)組將會進(jìn)行擴(kuò)容迁匠，以滿足添加數(shù)據(jù)的需求剩瓶。
數(shù)組擴(kuò)容有兩個方法：
- 開發(fā)者可以通過一個 public 的方法
ensureCapacity(int minCapacity)來增加 ArrayList 的容量：
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
- 而在存儲元素等操作過程中，如果遇到容量不足城丧，會調(diào)用 private 方法
private void ensureCapacityInternal(int minCapacity)
實(shí)現(xiàn)：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
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);
}
數(shù)組的擴(kuò)容操作的代價是很高的延曙，因此在實(shí)際使用時，我們應(yīng)該盡量避免數(shù)組容量的擴(kuò)張亡哄。
- 當(dāng)我們可預(yù)知要保存的元素的多少時枝缔，要在構(gòu)造 ArrayList 實(shí)例時，就指定其容量蚊惯，以避免數(shù)組擴(kuò)容的發(fā)生愿卸。
- 或者根據(jù)實(shí)際需求，通過調(diào)用 ensureCapacity 方法來手動增加 ArrayList 實(shí)例的容量截型。
LinkedList 的實(shí)現(xiàn)原理
使用鏈表
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
雙端鏈表
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
