ArrayList & LinkedList源碼解析
本文記錄ArrayList & LinkedList源碼解析 基於JDK1.8
ArrayList
ArrayList實現了List介面 所有擁有List介面所有方法 可以看成可'調節'的數組 可以包含任何類型數據（包括null，可重複）ArrayList執行緒不是安全的
類結構
ArrayList類主要成員變數：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
// 初始化容量(數組初始長度) 10
private static final int DEFAULT_CAPACITY = 10;
// 表示空數組
private static final Object[] EMPTY_ELEMENTDATA = {};
// 也是空數組，和EMPTY_ELEMENTDATA區分開
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 裝ArrayList的數組
transient Object[] elementData; // non-private to simplify nested class access
// 數組長度
private int size;
}
方法解析
構造函數
public ArrayList()
public ArrayList() {
// elementData為DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(int initialCapacity)
public ArrayList(int initialCapacity) {
// initialCapacity初始化容量 由調用者傳入
// 如果initialCapacity大於0
if (initialCapacity > 0) {
// elementData為 Object類型的 initialCapacity大小的數組
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 如果初始值為0 elementData為 EMPTY_ELEMENTDATA 空數組
this.elementData = EMPTY_ELEMENTDATA;
} else {
// initialCapacity 小於0 拋錯
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList(Collection<? extends E> c)
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray();
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}
創建一個包含指定集合c數據的ArrayList 上面為什麼要多此一舉使用
Arrays.copyOf(elementData, size, Object[].class)複製一遍數組呢？這是因為在某些情況下
調用集合的toArray()方法返回的類型並不是Object[].class 比如：
Long[] array1 = {1L, 2L};
List<Long> list1 = Arrays.asList(array1);
Object[] array2 = list1.toArray();
System.out.println(array2.getClass() == Object[].class); // false
List<Long> list2 = new ArrayList<>();
System.out.println(list2.toArray().getClass() == Object[].class); // true
add方法
add(E e)向數組尾部添加元素
public boolean add(E e) {
// 確定數組容量 size 類型為int 默認值(即初始值)為 0
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// minCapacity = size + 1 = 1
// elementData = {}
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// Math.max返回最大的數組 DEFAULT_CAPACITY = 10 minCapacity = 1 返回 10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// minCapacity = 10
// elementData = {}
// 10 - 0 > 0
if (minCapacity - elementData.length > 0)
// 擴容
grow(minCapacity);
}
private void grow(int minCapacity) {
// oldCapacity = 0
int oldCapacity = elementData.length;
// >> 右移運算符 相當於newCapacity為oldCapacity的1.5倍
// oldCapacity / 2 此處 0 + 0 / 2 還是等於 0
int newCapacity = oldCapacity + (oldCapacity >> 1);
// newCapacity = 0 minCapacity = 10 0 - 10 < 0 條件成立
if (newCapacity - minCapacity < 0)
// newCapacity = 10
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// // 複製到新數組 數組容量為10
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// MAX_ARRAY_SIZE常量值為Integer.MAX_VALUE - 8 通過
// 這段邏輯我們可以知道，ArrayList最大容量為Integer.MAX_VALUE
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
綜述 可以知道
- 任何一個空的數組 第一次添加元素的時候 內部數組容量將被擴容為10
- 擴容時，newCapacity為oldCapacity的1.5倍
- 容量最大值為Integer.MAX_VALUE - 8
- 尾部添加元素不用移動任何元素 所以速度快
