JDK原始碼閱讀：ArrayList原理
持續創作，加速成長！這是我參與「掘金日新計劃 · 10 月更文挑戰」的第9天，點選檢視活動詳情
ArrayList原理
ArrayList集合底層資料結構
ArrayList集合介紹
List 介面的可調整大小的陣列實現。
陣列：一旦初始化長度就不可以發生改變
陣列結構特性
增刪慢：每次刪除元素，都需要更改陣列長度、拷貝以及移動元素位置。
查詢快：由於陣列在記憶體中是一塊連續空間，因此可以根據地址+索引的方式快速獲取對應位置上的元素。
ArrayList繼承關係
Serializable序列化介面
類的序列化由實現java.io.Serializable介面的類啟用。 不實現此介面的類將不會使任何狀態序列化或反序列化。 可序列化類的所有子型別都是可序列化的。 序列化介面沒有方法或欄位，僅用於標識可序列化的語義。
序列化是將物件狀態轉換為可保持或傳輸的格式的過程。
與序列化相對的是反序列化，它將流轉換為物件。
比如將物件的資料序列化後寫入到檔案；
將檔案中物件的資料讀取出來後反序列化解析成物件。
在需要進行物件資料網路傳輸或持久化時，需要將物件進行序列化
原始碼
public interface Serializable {
}
從原始碼上看Serializable是一個空介面，Java裡稱為標識介面，當類實現Serializable介面，相當於給該類標記了“可被序列化”的元資料，打上了“可被序列化”的標籤。
序列化/反序列化測試
static class SerTest01 {
public static void main(String[] args) throws IOException, ClassNotFoundException {
// 測試序列化寫入檔案
writeObject();
// 測試反序列化檔案讀取
readObject();
}
// 將物件資料寫入檔案
private static void writeObject() throws IOException {
// 序列化：將物件的資料寫入到檔案(寫物件)
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("testoutfile\obj.txt"));
User user = new User("李四", 78);
// 將物件資料寫入檔案
oos.writeObject(user);
// 關閉流
oos.close();
}
// 將物件資料寫入檔案
private static void readObject() throws IOException, ClassNotFoundException {
// 反序列化：將檔案中物件的資料讀取出來(讀物件)
ObjectInputStream ois = new ObjectInputStream(new FileInputStream("..\obj.txt"));
User user = (User) ois.readObject();
// 將物件資料寫入檔案
System.out.println(user.toString());
// 關閉流
ois.close();
}
}
// User實體類
public class User implements Serializable {
/**
* 類的序列化由實現`java.io.Serializable`介面的類啟用。
* 不實現此介面的類將不會使任何狀態序列化或反序列化。
* 可序列化類的所有子型別都是可序列化的。
* 序列化介面沒有方法或欄位，僅用於標識可序列化的語義。
*/
public final long serialVersionUID = 1510141000893066237L;
private String name;
private Integer age;
public User() {
}
public User(String name, Integer age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getAge() {
return age;
}
public void setAge(Integer age) {
this.age = age;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[").append("name = ").append(this.name).append(", ").append("age = ").append(this.age).append("]");
return sb.toString();
}
}
實現了Serializable介面的User類可以被ObjectOutputStream轉換為位元組流寫入檔案，同時也可以通過ObjectInputStream再將其從檔案讀取並解析為物件。
如果User實體類不實現Serializable則無法序列化或反序列化，就會丟擲異常NotSerializableException。執行會出現下圖報錯
判斷是否實現Serializable的原始碼
if (obj instanceof String) {
writeString((String) obj, unshared);
} else if (cl.isArray()) {
writeArray(obj, desc, unshared);
} else if (obj instanceof Enum) {
writeEnum((Enum<?>) obj, desc, unshared);
} else if (obj instanceof Serializable) {
writeOrdinaryObject(obj, desc, unshared);
} else {
if (extendedDebugInfo) {
throw new NotSerializableException(
cl.getName() + "\n" + debugInfoStack.toString());
} else {
throw new NotSerializableException(cl.getName());
}
}
這裡可以看到，Java對字串、陣列、列舉類、普通類進行序列化時單獨判斷的，當普通類沒有實現Serializable介面就會丟擲異常NotSerializableException。
RandomAccess隨機訪問
List實現使用的標記介面，表明它們支援快速（通常是恆定時間）隨機訪問。此介面的主要目的是允許通用演算法更改其行為，以便在應用於隨機訪問列表或順序訪問列表時提供良好的效能。
用於操作隨機訪問列表（例如ArrayList ）的最佳演算法在應用於順序訪問列表（例如LinkedList ）時會產生二次行為。鼓勵通用列表演算法在應用演算法之前檢查給定列表是否是此介面的例項，如果將其應用於順序訪問列表會提供較差的效能，並在必要時更改它們的行為以保證可接受的效能。
眾所周知，隨機訪問和順序訪問之間的區別通常是模糊的。例如，如果某些List實現變得很大，則提供漸近線性訪問時間，但在實踐中訪問時間是恆定的。這樣的List實現一般應該實現這個介面。根據經驗，如果對於類的典型例項，如果出現以下迴圈，則List實現應該實現此介面：
// 隨機訪問，list.get(i)根據索引遍歷
for (int i=0, n=list.size(); i < n; i++)
list.get(i);
執行速度比這個迴圈快：
// 順序訪問，迭代器進行遍歷
for (Iterator i=list.iterator(); i.hasNext(); )
i.next();
原始碼
public interface RandomAccess {
}
測試順序訪問和隨機訪問速度
/**
* 測試隨機訪問比順序訪問快，這裡僅對ArrayList做遍歷操作
*
* @param args
*/
public static void main(String[] args) {
// 建立ArrayList集合
List<String> list = new ArrayList<>();
// 新增50W條資料
for (int i = 0; i < 500000; i++) {
list.add(i + "a");
}
System.out.println("----通過索引(隨機訪問)----");
long startTime = System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) {
list.get(i);
}
long endTime = System.currentTimeMillis();
System.out.println("隨機訪問用時: " + (endTime - startTime));
System.out.println("----通過迭代器(順序訪問)----");
startTime = System.currentTimeMillis();
Iterator<String> it = list.iterator();
while (it.hasNext()) {
it.next();
}
endTime = System.currentTimeMillis();
System.out.println("順序訪問用時: " + (endTime - startTime));
}
//----通過索引(隨機訪問)----
//隨機訪問用時: 3
//----通過迭代器(順序訪問)----
//順序訪問用時: 4
從輸出結果來看ArrayList隨機訪問比順序訪問快，接下來對比下LinkedList
```
public static void main(String[] args) {
// 建立ArrayList集合
List
從輸出結果來看LinkedList的順序遍歷比隨機訪問快。
LinkedList原始碼
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
// 具體實現原始碼此處不進行討論，省略...
}
可以看到LinkedList並沒有實現RandomAccess介面，符合RandomAccess介面介紹內容，此外LinkedList結構也確定了它的順序遍歷比隨機訪問快。
實際應用場景中建議使用instanceof判斷集合是否實現了RandomAccess介面，再根據實際情況使用隨機訪問或順序訪問。
if(list instanceof RandomAccess)
// 隨機訪問
else
// 順序訪問
Cloneable克隆介面
一個類實現了Cloneable介面，以向Object.clone()方法指示該方法可以合法地對該類的例項進行逐個欄位的複製。
在未實現Cloneable介面的例項上呼叫 Object.clone() 方法會導致丟擲異常CloneNotSupportedException 。
原始碼
public interface Cloneable {
}
Cloneable也是一個標識介面，此介面不包含clone方法。因此，不可能僅憑藉實現該介面的例項來克隆物件。即使以反射方式呼叫 clone 方法，也不能保證它會成功。
clone()使用例項
public static void main(String[] args) {
// 建立使用者物件集合
ArrayList<User> list = new ArrayList<User>();
list.add(new User("李四", 78));
list.add(new User("張三", 28));
Object o = list.clone();
System.out.println(o);
System.out.println(list);
System.out.println(o == list);
}
// false
// [[name = 李四, age = 78], [name = 張三, age = 28]]
// [[name = 李四, age = 78], [name = 張三, age = 28]]
從輸出看，clone()建立了一個新的物件，內容與原物件一致。
ArrayList實現了Cloneable介面，故而該類可以可以呼叫Object.clone()方法實現物件克隆。
若類沒有實現Cloneable介面，該例項呼叫 Object.clone() 方法會導致丟擲異常CloneNotSupportedException 。
clone原始碼
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
普通類支援 Object.clone() 方法
修改User類，使得支援 Object.clone() 方法
public class User implements Serializable, Cloneable {
public final long serialVersionUID = 1510141000893066237L;
// 屬性 getter setter toString...
// 重寫clone
@Override
public Object clone() throws CloneNotSupportedException {
return super.clone();
}
}
User類實現Cloneable介面，並重寫 Object.clone() 方法。
重寫原則
- 子類返回型別小於等於父類方法返回型別
- 子類丟擲異常小於等於父類方法丟擲異常
- 子類訪問許可權大於等於父類方法訪問許可權（public>protected>friendly，private不能被繼承）
static class Cloneable01 {
public static void main(String[] args) throws CloneNotSupportedException {
User user1 = new User("張", 12);
Object user2 = user1.clone();
System.out.println(user1);
System.out.println(user2);
System.out.println(user1 == user2);
}
}
// [name = 張, age = 12]
// [name = 張, age = 12]
// false
淺拷貝
新建Address類，如下所示
public class Address implements Serializable {
public final long serialVersionUID = 1578511564815489L;
private String city;
public Address() {
}
public Address(String city) {
this.city = city;
}
public String getCity() {
return city;
}
public void setCity(String city) {
this.city = city;
}
@Override
public String toString() {
return city;
}
}
修改User類如下所示
public class User implements Serializable, Cloneable {
public final long serialVersionUID = 1510141000893066237L;
private String name;
private Integer age;
private Address address;
// setter getter...
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[").append("name = ").append(this.name).append(", ").append("age = ").append(this.age);
if (address != null)
sb.append(", address = ").append(this.address.toString());
sb.append("]");
return sb.toString();
}
@Override
public Object clone() throws CloneNotSupportedException {
return super.clone();
}
}
淺拷貝測試類
/**
* 淺拷貝
*/
static class Cloneable02 {
public static void main(String[] args) throws CloneNotSupportedException {
Address address = new Address("北京");
User user1 = new User("張", 12, address);
User user2 = (User)user1.clone();
System.out.println(user1);
System.out.println(user2);
System.out.println(user1 == user2);
System.out.println(user2.getAddress() == user1.getAddress());
address.setCity("海口");
user1.setAddress(address);
System.out.println(user1);
System.out.println(user2);
}
}
//[name = 張, age = 12, address = 北京]
//[name = 張, age = 12, address = 北京]
//false
//true
//[name = 張, age = 12, address = 海口]
//[name = 張, age = 12, address = 海口]
從輸出結果可以得知User類的基本資料型別可以達到完全複製，引用資料型別卻不可以。
原因在於在User物件user1被克隆的時候，其屬性address作為引用型別僅僅是拷貝了一份引用，兩者指向的地址仍是一致的。因此當address的值發生改變時，被克隆物件user2的屬性address的值也會改變。
深拷貝
修改Address類，如下所示
public class Address implements Serializable, Cloneable {
public final long serialVersionUID = 1578511564815489L;
// getter setter toString...
@Override
public Object clone() throws CloneNotSupportedException {
return super.clone();
}
}
Address類實現Cloneable介面，並重寫 Object.clone() 方法。
修改User類如下所示
public class User implements Serializable, Cloneable {
// 屬性 setter getter toString...
/**
* 呼叫引用物件的clone()，實現深拷貝
*
* @return
* @throws CloneNotSupportedException
*/
@Override
public Object clone() throws CloneNotSupportedException {
User user = (User) super.clone();
Address address = (Address) this.address.clone();
user.setAddress(address);
return user;
}
}
之前重寫的super.clone()是不能拷貝引用物件的，那麼呼叫Address類的clone() 方法，拷貝address屬性後再賦值給user物件。
深拷貝測試類
/**
* 深拷貝 實現地方在User、Address類
*/
static class Cloneable03 {
public static void main(String[] args) throws CloneNotSupportedException {
Address address = new Address("北京");
User user1 = new User("張", 12, address);
User user2 = (User) user1.clone();
System.out.println(user1);
System.out.println(user2);
System.out.println(user1 == user2);
System.out.println(user2.getAddress() == user1.getAddress());
address.setCity("海口");
user1.setAddress(address);
System.out.println(user1);
System.out.println(user2);
}
}
//[name = 張, age = 12, address = 北京]
//[name = 張, age = 12, address = 北京]
//false
//false
//[name = 張, age = 12, address = 海口]
//[name = 張, age = 12, address = 北京]
測試類沒有程式碼修改，主要修改在User、Address類。
從輸出結果來看，已經實現對address引用物件的深拷貝。
ArrayList原始碼
構造方法
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 預設長度為0的陣列
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 儲存 ArrayList 元素的陣列緩衝區。 ArrayList 的容量就是這個陣列緩衝區的長度。
transient Object[] elementData;
// 給elementData賦值
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
}
通過無參構造方法建立集合物件，僅僅將DEFAULTCAPACITY_EMPTY_ELEMENTDATA （一個預設長度為0的陣列）的地址賦值給elementData（儲存ArrayList元素的陣列緩衝區）
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 用於空例項的共享空陣列例項。
private static final Object[] EMPTY_ELEMENTDATA = {};
// 構造一個具有指定初始容量的空列表。
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// 長度大於0，建立指定長度的陣列
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 長度為0，將空陣列的地址賦值給elementData
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
}
根據 ArrayList 構造方法引數建立指定長度的陣列，如果指定長度等於0，直接給elementData賦值EMPTY_ELEMENTDATA（空陣列例項）
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 按照集合的迭代器返回的順序構造一個包含指定集合元素的列表
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;
}
}
// 實現Collection介面
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
}
class Arrays {
// 複製指定的陣列，截斷或填充空值（如有必要），使副本具有指定的長度。
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
// 複製指定的陣列，截斷或填充空值（如有必要），使副本具有指定的長度。
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
// 不管三元運算子的結果如何,都會建立一個新的陣列
// 新陣列的長度一定是和集合的size一樣
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
// 陣列的拷貝
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
// 返回新陣列
return copy;
}
// 建立具有指定元件型別和長度的新陣列。
public static Object newInstance(Class<?> componentType, int length)
throws NegativeArraySizeException {
return newArray(componentType, length);
}
}
使用ArrayList<User> userList = new ArrayList<User>(list)構造一個集合時，會進入到此構造方法，通過一個三目表示式判斷是構建一個Object集合還是newType中元素型別的集合。
add()方法
新增單個元素
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// ArrayList的大小
private int size;
// 預設大小為空的例項，共享空陣列例項
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 集合存元素的陣列
Object[] elementData;
// 預設的容量
private static final int DEFAULT_CAPACITY = 10;
// 陣列的最大大小，2^31-1-8 = 2147483647-8，一些 VM 在陣列中保留一些標題字。嘗試分配更大的陣列可能會導致 OutOfMemoryError：請求的陣列大小超過 VM 限制
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 將指定元素附加到此列表的末尾
public boolean add(E e) {
// 每次新增元素之前先動態調整陣列大小，避免溢位
ensureCapacityInternal(size + 1); // Increments modCount!!
// 每次都會把新新增的元素放到陣列末尾,ArrayList順序存放的原因
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 這裡會判斷下當前ArrayList是否為空，為空則先初始化陣列，
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 計算ArrayList容量，🍀這裡可以看到當ArrayList為空，且第一次向容器新增元素時，會對ArrayList進行擴容，最小容量為10。
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果當前容器為空，那麼獲取初始化陣列的大小，陣列大小不能小於DEFAULT_CAPACITY（10）
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 預設容量為空的陣列
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果當前元素數量達到了容器上限，就對容器進行擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// oldCapacity為當前容器大小
int oldCapacity = elementData.length;
// 擴容的核心演算法，擴容為原容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 因為第一次容器有可能為空，elementData.length==0，newCapacity會小於minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// newCapacity不能大於MAX_ARRAY_SIZE，因為陣列能分配的最大空間就是Integer.MAX_VALUE，
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 確定好陣列大小後，對陣列進行拷貝，Arrays.copyOf的底層是一個native(非Java實現)方法。
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 有些VM會在陣列中保留一些標題字，當仍需要更大容量時，則會賦予Integer.MAX_VALUE；當超出時會溢位，報錯OOM。
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
}
在指定索引處新增元素
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
新增元素的時候，首先都要檢查擴容，在add(int index, E element)方法中多一步操作，就是將指定位置以後的所有元素向後移動一位，留出當前位置用來存放新增的元素。
將集合的所有元素一次性新增到集合
public boolean addAll(Collection<? extends E> c) {
//把有資料的集合轉成陣列
Object[] a = c.toArray();
//有資料集合長度賦值給numNew
int numNew = a.length;
//校驗以及擴容
ensureCapacityInternal(size + numNew); // Increments modCount
//真正拷貝的程式碼
System.arraycopy(a, 0, elementData, size, numNew);
//集合的長度進行更改
size += numNew;
//根據numNew的值返回是否新增成功
return numNew != 0;
}
public boolean addAll(int index, Collection<? extends E> c) {
//校驗索引
rangeCheckForAdd(index);
//將資料來源轉成陣列
Object[] a = c.toArray();
//記錄資料來源的長度 3
int numNew = a.length;
//目的就是為了給集合儲存資料的陣列進行擴容
ensureCapacityInternal(size + numNew);
//numMoved:代表要移動元素的個數 --> 1個
//numMoved: 資料目的(集合list1)的長度-呼叫addAll的第一個引數 (索引1)
int numMoved = size - index;
//判斷需要移動的個數是否大於0
if (numMoved > 0)
//使用System中的方法arraycopy進行移動
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//才是真正將資料來源(list)中的所有資料新增到資料目的(lsit1)
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
addAll方法原理也是一樣的，多了一步將集合元素新增過程。
set方法
public E set(int index, E element) {
//校驗索引
rangeCheck(index);
//根據索引取出元素 --> 被替換的元素
E oldValue = elementData(index);
//把element存入到elementData陣列中
elementData[index] = element;
//返回被替換的元素
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
set方法根據索引將元素取出後，再陣列中元素替換掉。
get方法
public E get(int index) {
//校驗索引
rangeCheck(index);
//根據索引獲取陣列(集合)中的元素
return elementData(index);
}
get方法根據索引將元素取出後，直接返回。
remove方法
remove單個元素
// 🐊移除此列表中指定位置的元素。將任何後續元素向左移動（從它們的索引中減去 1）
public E remove(int index) {
// 索引範圍判斷，超出報IndexOutOfBoundsException
rangeCheck(index);
// 運算元自增1
modCount++;
// oldValue記錄index索引當前值
E oldValue = elementData(index);
// 計算集合需要移動元素的個數
int numMoved = size - index - 1;
if (numMoved > 0)
// 進行陣列拷貝，把索引位index後的元素向前移動一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 把集合最後一位元素賦null，儘早讓垃圾回收機制回收
elementData[--size] = null; // clear to let GC do its work
// 將記錄的原索引位元素值返回
return oldValue;
}
// 🐊從此列表中刪除第一次出現的指定元素（如果存在）。如果列表不包含該元素，則它不變。
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
// 用==比較null元素
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
// 用equals比較非null元素
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
// 不存在該元素，不修改本列表，直接返回false
return false;
}
// 私有方法，刪除元素省去了索引範圍判斷，且不需要返回原值，直接進行陣列拷貝
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
刪除集合元素
``` // 從此列表中刪除包含在指定集合中的所有元素 public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, false); } // 僅保留此列表中包含在指定集合中的元素。換句話說，從這個列表中刪除所有不包含在指定集合中的元素。 public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true); }
// 批量刪除集合元素 private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { for (; r < size; r++) // 判斷集合包含元素，刪除集合c外的其他元素 if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. // 當r!=size時，判定上一步出現異常，需要將之前修改過的陣列再還原 if (r != size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true; } } return modified; } ```
removeAll和retainAll通過呼叫的方法是一個，僅通過一個開關實現截然相反的操作，
從Java原始碼上分析為什麼LinkedList隨機訪問比順序訪問要慢這麼多？
// 隨機訪問
for(int i=0;i<list.size();i++) {
list.get(i);
}
// 順序訪問
Iterator<E> it = list.iterator();
while(it.hasNext()){
it.next();
}
LinkedList的get()方法原始碼
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
// 返回此列表中指定位置的元素。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
// 判斷引數是否是現有元素的索引。
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
// ArrayList 的大小
private int size;
// 儲存 ArrayList 元素的陣列緩衝區。
transient Object[] elementData;
// 返回指定元素索引處的（非空）節點。
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
// index小於長度一半時，是從連結串列頭部往後找
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
// index大於長度一半時，是從連結串列尾部往前找
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
隨機訪問使用list.get(i)方法，從原始碼中我們可以得知，每次list.get(i)都遍歷找到該元素位置再返回，當我們需要遍歷一次list，其實list.get(i)會遍歷很多次，做了重複性工作。
list.iterator()原始碼
```
Iterator
// 判斷nextIndex是否在範圍內 public boolean hasNext() { return nextIndex < size; }
// 獲取下一個元素
public E next() {
// 檢查集合實際修改次數和預期次數是否一樣
checkForComodification();
// 再次判斷是否有元素
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
// 檢查集合實際修改次數和預期次數是否一樣
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
// 🍀在獲取迭代器的時候也會進行折半判斷的過程，但index=0
Node
從迭代器原始碼中我們得知，在進行順序訪問時，只在第一次，index=0時進行了一個折半判斷，此後按照順序依次向後傳遞獲取元素，實際只進行了一次遍歷過程。由此可見，LinkedList的順序遍歷比隨機遍歷快很多。