Java 中的 List 是非常常用的資料型別，List 是有序的 Collection，Java List 一共有三個實作類，分別是：ArrayList、Vector、LinkedList
本文分析基于 JDK8
ArrayList
ArrayList 繼承自 AbstractList，實作了 List 介面，底層基于陣列實作容量大小動態變化，初始容量為 10，允許值為 null，有序，非執行緒安全，擅長隨機訪問
ArrayList 還實作了 RandomAccess、Cloneable、Serializable 介面，所以 ArrayList 是支持快速訪問、復制、序列化的
-
RandomAccess
標記介面，用來表明其支持快速隨機訪問，如果是實作了這個介面的 List，那么使用 for 回圈的方式獲取資料會優于用迭代器獲取資料
-
Serializable
標記該類支持序列化
-
Cloneable
允許在堆中克隆出一塊和原物件一樣的物件，并將這個物件的地址賦予新的參考，ArrayList 提供的是一種深克隆機制，即克隆除自身物件以外的所有物件，包括自身所包含的所有物件實體，實作方式是先呼叫 super.clone() 方法克隆出一個新物件，然后再手動將原陣列中的值復制到一個新的陣列，并賦值
ArrayList 擴容機制
擴容機制應該是面試中最常問的了，其他關于 ArrayList 的一些瑣碎方法我就不細說了，主要介紹一下擴容機制，首先了解一下 ArrayList 的成員屬性
// 表示 ArrayList 的默認容量大小
private static final int DEFAULT_CAPACITY = 10;
// 一個空的 Object 陣列物件，長度為 0，如果使用默認建構式創建，則 elementData 默認是該值
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = https://www.cnblogs.com/Yee-Q/p/{};
// 最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// ArrayList 中存放的實際元素個數
private int size;
// 當前元素物件存放的陣列，不參與序列化
transient Object[] elementData;
執行 add 方法時，會先執行 ensureCapacityInternal 方法，判斷當前陣列容量是否足夠，不夠就擴容，然后將待添加元素加到 elementData 末尾
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData =https://www.cnblogs.com/Yee-Q/p/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// minCapacity > elementData.length 則擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
再分析一下 ensureCapacityInternal 方法，此時 minCapacity 是 size + 1，這里有兩個嵌套方法 calculateCapacity 和 ensureExplicitCapacity，作用分別如下：
-
calculateCapacity
如果當前陣列為空，則先設定容量為默認值 10，此時還未初始化陣列
-
ensureExplicitCapacity
確認實際的容量，如果不夠就擴容，關鍵的擴容函式 grow 就在這里
擴展陣列大小，首先將容量擴大為原來的 1.5 倍，如果陣列是空陣列，則將陣列初始化，默認容量為 10，如果不是，再判斷是否超出最大容量，超過直接賦予最大值，否則賦予新值，復制原陣列到新陣列
private void grow(int minCapacity) {
// 擴容前的容量
int oldCapacity = elementData.length;
// oldCapacity 右移一位，等于除以二
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 擴容之后還是不夠，直接賦予新值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 擴容之后超出最大容量，直接賦予最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 復制原陣列的值到新陣列
elementData = https://www.cnblogs.com/Yee-Q/p/Arrays.copyOf(elementData, newCapacity);
}
LinkedList
LinkedList 繼承自 AbstractSequentialList，實作了 List 和 Deque 介面，基于雙向鏈表實作，每個節點都包含了對前一個和后一個元素的參考，可以被當作堆疊、佇列或雙端佇列進行操作，有序，非執行緒安全
// 指向鏈表的第一個節點
transient Node<E> first;
// 指向鏈表的最后一個節點
transient Node<E> last;
JDK8 中 LinkedList 有一個靜態內部類 Node，它包括的屬性有：當前節點所包含的值，上一個節點，下一個節點
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;
}
}
除此之外就沒啥好分析的了，LinkedList 不存在容量不足的問題，克隆函式也是將所有元素全都克隆到新的 LinkedList 物件
Vector
Vector 是一個矢量佇列，和 ArrayList 類似，繼承自 AbstractList，實作了 List 介面，就連額外介面也是一樣，不同之處在于：
- Vector 使用 synchronized 保證執行緒同步
- Vector 中遺留了大量傳統的方法，這些方法不屬于集合框架
Vector 有四個構造方法
// 創建一個默認大小為 10 的向量
public Vector()
// 創建指定大小的向量
public Vector(int initialCapacity)
// 創建指定大小的向量，并且指定增量，增量表示向量每次增加的元素數目
public Vector(int initialCapacity, int capacityIncrement)
// 創建一個包含集合 c 元素的向量
public Vector(Collection<? extends E> c)
Vector 的資料結構和 ArrayList 差不多，它包含了三個成員變數：
// 存放元素的動態陣列
protected Object[] elementData;
// 動態陣列的實際大小
protected int elementCount;
// 動態陣列的增長系數
protected int capacityIncrement;
隨著 Vector 中元素的增加，Vector 的容量也會動態增長，capacityIncrement 是與容量增長相關的增長系數，具體增長細節在 grow 函式中，和 ArrayList 類似
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 如果 capacityIncrement > 0，新的容量大小 = 舊的容量大小 + 增長系數
// 否則容量擴大為原來的兩倍
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = https://www.cnblogs.com/Yee-Q/p/Arrays.copyOf(elementData, newCapacity);
}
Stack
Stack 是 Vector 的子類，實作了一個標準的后進先出的堆疊，Stack 也是通過陣列實作的，當然了，我們也可以將 LinkedList 當作堆疊來使用
Stack 只定義了默認建構式，用來創建一個空堆疊
public Stack()
Stack 除了具有 Vector 的所有 API，還有自己實作的方法
// 判斷堆疊是否為空
public boolean empty()
// 查看堆疊頂部的物件，但不從堆疊中移除它
public synchronized E peek()
// 移除堆疊頂部的物件，并作為此函式的值回傳該物件
public synchronized E pop()
// 把物件壓入堆疊頂部
public E push(E item)
// 回傳物件在堆疊中的位置，以 1 為基數
public synchronized int search(Object o)
Stack 的擴容機制基于 Vector，不過由于沒有指定增長系數，所有默認為 0，每次擴容陣列長度增大為原來的兩倍
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/113515.html
標籤：Java
上一篇：前端面試—HTML面試題匯總