在我們開發者眼中，這就是一個“動態數組”，可以“動態”地調整數組的大小，雖然說數組從定義了長度後，就不能改變大小。
實現“動態”調整的基本原理就是：按照某個調整策略，重新創建一個調整後一樣大小的數組，然後將原來的數組賦值回去。
下面我們來解析一下幾個與數組不一樣的方法。
看看ArrayList中主要的幾個字段（源碼剖析）：
// 默認的初始數組大小
private static final int DEFAULT_CAPACITY = 10;
// 空數組的表示
private static final Object[] EMPTY_ELEMENTDATA = {};
// 數據保存的數組，主體就是它
private transient Object[] elementData;
// 數組元素個數（不一定等於數組的length）
private int size;
添加元素（源碼剖析）：
public boolean add(E e) {
// 判斷數組需不需要擴容，需要就擴容（動態調整數組大小的關鍵方法）
ensureCapacityInternal(size + 1);
// 數組元素賦值，數組元素個數+1
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
// 監測是否是數組越界
rangeCheckForAdd(index);
// 判斷數組需不需要擴容，需要就擴容（動態調整數組大小的關鍵方法）
ensureCapacityInternal(size + 1);
// index和index的元素向後移動
System.arraycopy(elementData, index, elementData, index + 1, size - index);
// index位置上賦值
elementData[index] = element;
// 數組元素+1
size++;
}
刪除元素，這裡注意，並沒有真正的縮小數組的大小，只是修改size的值（源碼剖析）：
public E remove(int index) {
// 數組越界檢查，會拋出異常哦
rangeCheck(index);
// 記錄修改次數，在迭代器那裡會有用
modCount++;
// 找到要刪除的數據
E oldValue = elementData(index);
// 需要移動的元素個數
int numMoved = size - index - 1;
if (numMoved > 0)
// 復制數組，移動元素
System.arraycopy(elementData, index+1, elementData, index,numMoved);
// 移除引用，方便GC回收
elementData[--size] = null;
return oldValue;
}
public boolean remove(Object o) {
if (o == null) {
// 遍歷數組，查找到第一個為null值的元素，然後刪除
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
// 快速刪除
fastRemove(index);
return true;
}
} else {
// 同樣是遍歷數組，查找
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
// 找到，刪除
fastRemove(index);
return true;
}
}
// 找不到
return false;
}
// 與E remove(int index)的差不多，我就不多說了。
// 這裡我就不明白，remove(int index)和fastRemove(int index)明明可以代碼復用，為何不復用代碼呢？
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// 置null，讓GC可以回收它
elementData[--size] = null;
}
看看最重要的數組擴容方法（源碼剖析）：
private void ensureCapacityInternal(int minCapacity) {
// 判斷數組是否為空數組
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
// 修改次數+1
modCount++;
// 判斷需不需要擴容：比較數組大小和需要擴容的大小
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 增加容量開始
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// x1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
// 擴容的大小太小了
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 擴容的大小不會超過最大容量Integer.MAX_VALUE-8
newCapacity = hugeCapacity(minCapacity);
// 數組復制
elementData = Arrays.copyOf(elementData, newCapacity);
}
ArrayList被稱為“動態數組的原理”，大致就如源碼解析中注釋。裡面還有其他數組操作的方法，這裡就不多講，其實思路也是差不多的，一切以源碼為准。
（雙向）鏈表+隊列（Deque）。以前我一直以為LinkedList只是個鏈表而已，沒想到它可以當隊列用。
看看結點代碼，一看就知道是雙向的結點（源碼）：
private static class Node {
E item;
Node next; // 後繼節點
Node prev; // 前置節點
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
幾個重要字段（源碼解析）：
// transient：不被序列化
// 結點個數
transient int size = 0;
// 第一個結點
transient Node first;
// 最後一個結點
transient Node last;
簡單的看看鏈表的代碼（源碼解析）：
// 添加結點
public void add(int index, E element) {
// 檢查index是否越界
checkPositionIndex(index);
if (index == size)
// 添加最後一個
linkLast(element);
else
// 添加到原index結點前面
linkBefore(element, node(index));
}
// 刪除結點
public E remove(int index) {
// 檢查index是否越界
checkElementIndex(index);
// 解除結點鏈接
return unlink(node(index));
}
// 查找結點
public E get(int index) {
// 檢查越界了沒
checkElementIndex(index);
// 開始查找
return node(index).item;
}
// “真正”是使用這個方法來查找
Node node(int index) {
// 折半查找~，果然是會利用雙向鏈表的優點
if (index < (size >> 1)) { // 從前面找找前半邊
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { // 從後面找找後半邊
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
簡單的看看隊列的代碼（源碼解析）：
// 入隊
public boolean offer(E e) {
return add(e);
}
// 也是入隊
public boolean add(E e) {
// 接到最後一個結點
linkLast(e);
// 個人覺得這個return true沒必要，完全可以無返回值void，以為如果入隊失敗linkLast會拋異常。既然是拋異常了，就不會return false了，那就沒必要return true。
return true;
}
// “溫柔地”取隊頭元素，隊為空不會拋出異常，只會返回null
public E peek() {
final Node f = first;
return (f == null) ? null : f.item;
}
// “粗暴地”取隊頭元素，隊為空拋出NoSuchElementException異常
public E element() {
return getFirst();
}
// “溫柔地”出隊，隊為空不會拋出異常，只會返回null
public E poll() {
final Node f = first;
return (f == null) ? null : unlinkFirst(f);
}
// “粗暴地”出隊，隊為空拋出NoSuchElementException異常
public E remove() {
return removeFirst();
}
加鎖版的ArrayList（線程安全）。方法實現與ArrayList差不多，不同的是線程不安全的方法都加上鎖（synchronized）了，這裡就不講啦。
一般不使用Vector而使用ArrayList，除非在多線程環境下（萬不得已）才使用Vector。
棧，父類是Vector，所以你懂的（加鎖版動態數組）。既然父類“安全”了，作為子類的棧也要“安全”了（加鎖！），這麼說棧也不是很快嘛~。
Stack規定數組最後一個元素為棧頂元素。
入棧（源碼解析）:
// 不加鎖？父類Vector的addElement已經加鎖了，所以不加多余的鎖。
public E push(E item) {
// 添加元素到數組最後一個元素的後面
addElement(item);
// 返回壓入棧的元素
return item;
}
出棧（源碼解析）:
// 出棧
public synchronized E pop() {
E obj;
// 棧中元素個數
int len = size();
// 取棧頂元素
obj = peek();
// 移除最後的一個元素（就是移除棧頂元素啦）
removeElementAt(len - 1);
// 返回移除的棧頂元素
return obj;
}
// 取棧頂元素
public synchronized E peek() {
int len = size();
if (len == 0)
// 空棧異常
throw new EmptyStackException();
// 取數組最後一個元素
return elementAt(len - 1);
}
棧中元素查找，從棧頂（最後一個數組元素）到棧底（第一個數組元素）（源碼解析）:
public synchronized int search(Object o) {
// 找到最後一個符合要求的元素
int i = lastIndexOf(o);
if (i >= 0) {
// 找到了
return size() - i;
}
// 沒找到
return -1;
}
PriorityQueue實現了優先隊列（默認最小堆）。
實現優先隊列的難點：需要調整堆。
調整堆的方法有：上濾和下濾。
幾個重要字段（源碼解析）：
// 默認的初始化容器大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// 元素數組
private transient Object[] queue;
// 元素個數
private int size = 0;
// 比較器（可拓展），可以為空，為空的話E就必須實現Comparable接口。
private final Comparator comparator;
// 修改次數
private transient int modCount = 0;
添加元素（入隊）（源碼解析）：
public boolean add(E e) {
return offer(e);
}
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
// 修改次數+1
modCount++;
int i = size;
// 判斷是否應該擴充數組
if (i >= queue.length)
// 數組擴容
grow(i + 1);
// 數組元素增加1
size = i + 1;
if (i == 0)
// 第一個入隊的元素
queue[0] = e;
else
// 因為有元素加入，需要調整堆（從下到上）：上濾
siftUp(i, e);
return true;
}
我們來看看調整堆的方法（源碼解析）：
上濾（源碼解析）：
// 選擇比較器上濾還是Comparable對象的上濾
private void siftUp(int k, E x) {
if (comparator != null)
// 優先選擇有比較器的進行上濾
siftUpUsingComparator(k, x);
else
// Comparable對象的上濾
siftUpComparable(k, x);
}
// Comparable對象的上濾
private void siftUpComparable(int k, E x) {
// 強制轉換成Comparable對象，這樣才能有下面的比較
Comparable key = (Comparable) x;
while (k > 0) {
// k是子結點在數組中的下標，(k-1)/2可以求出父結點下標
int parent = (k - 1) >>> 1;
// 取得父結點
Object e = queue[parent];
// 如果key大於或等於父節點
if (key.compareTo((E) e) >= 0)
break;
// key小於父結點
// 父結點與子結點交換值
queue[k] = e;
// k跑到父結點的位置
k = parent;
}
// 賦值到合適位置
queue[k] = key;
}
// 使用比較器的上濾（解析和siftUpComparable一樣）
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
下濾（源碼解析）：
// 下濾（和上濾一樣有兩次方式）
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
// Comparable對象的下濾
private void siftDownComparable(int k, E x) {
Comparable key = (Comparable)x;
// 計算出非葉子結點個數
int half = size >>> 1;
while (k < half) {
// 計算出左孩子的位置
int child = (k << 1) + 1;
// 取得左孩子的對象
Object c = queue[child];
// 右孩子的位置
int right = child + 1;
// 如果右孩子存在，並且左孩子大於右孩子
if (right < size &&
((Comparable) c).compareTo((E) queue[right]) > 0)
// 選擇右孩子作為與父結點的比較對象
c = queue[child = right];
// 父子結點比較
if (key.compareTo((E) c) <= 0)
// 如果父節點小於或等於子結點，則找到要調整的位置
break;
// 子結點值賦值到父結點
queue[k] = c;
// 換子結點進入下次循環的比較
k = child;
}
// 找到調整的位置，賦值
queue[k] = key;
}
// 使用比較器的下濾（解析和siftDownComparable一樣）
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}
總結：閱讀一下java容器包中的類後，對數據結構的了解又加深了一層，確實源碼裡的都是“好東西”。這裡的講的類還不全面，未完持續！
