一、認識List接口

1.1 List的定義與繼承關系

在Java集合框架里，List是一個接口，它繼承自Collection接口。而Collection接口又繼承自Iterable接口，這就決定了List具備了Collection接口規范的常用方法，同時也擁有了可逐個元素遍歷的特性。

從數據結構角度來看，List本質上是一個線性表，即由n個具有相同類型元素組成的有限序列。在這個序列上，我們可以進行元素的增刪改查以及遍歷等操作，這為數據的有序管理提供了便利。

1.2 Collection接口的核心方法

Collection接口作為List的父接口，定義了一系列容器常用方法，這些方法在List中也得到了實現和擴展，具體如下：

• size()：返回集合中元素的個數，類型為int。
• contains(Object o)：判斷集合中是否包含指定元素o，返回值為boolean類型。
• iterator()：返回一個用于遍歷集合元素的Iterator對象。
• toArray()：將集合中的元素轉換為一個Object類型的數組。
• toArray(T[] a)：將集合中的元素轉換為指定類型T的數組。
• add(E e)：向集合中添加元素e，添加成功返回true，否則返回false。
• remove(Object o)：從集合中刪除指定元素o，刪除成功返回true，否則返回false。
• containsAll(Collection<?> c)：判斷集合是否包含另一個集合c中的所有元素，返回boolean類型。
• addAll(Collection<? extends E> c)：將另一個集合c中的所有元素添加到當前集合中，添加成功返回true。
• removeAll(Collection<?> c)：從當前集合中刪除所有存在于集合c中的元素，刪除成功返回true。
• removeIf(Predicate<? super E> filter)：根據指定的過濾條件filter，刪除集合中滿足條件的元素，返回boolean類型。
• retainAll(Collection<?> c)：保留當前集合中與集合c共有的元素，刪除其他元素，操作成功返回true。
• clear()：清空集合中的所有元素。
• equals(Object o)：判斷當前集合與指定對象o是否相等，返回boolean類型。
• hashCode()：返回當前集合的哈希值。
• spliterator()：返回一個用于分割集合元素的Spliterator對象。
• stream()：返回一個用于遍歷集合元素的順序流Stream。
• parallelStream()：返回一個用于并行遍歷集合元素的并行流Stream。
• isEmpty()：判斷集合是否為空，返回boolean類型。

1.3 List接口的獨特方法

除了繼承自Collection接口的方法外，List接口還根據線性表的特性，新增了一些獨特的方法，以滿足對元素進行更精細操作的需求，常用方法如下表所示：

方法	解釋
boolean add(E e)	在List的末尾插入元素e
void add(int index, E element)	將元素element插入到List中指定的index位置
boolean addAll(Collection<? extends E> c)	將集合c中的所有元素添加到List的末尾
E remove(int index)	刪除List中index位置的元素，并返回被刪除的元素
boolean remove(Object o)	刪除List中遇到的第一個指定元素o，刪除成功返回true
E get(int index)	獲取List中下標為index位置的元素
E set(int index, E element)	將List中下標為index位置的元素設置為element，并返回該位置原來的元素
void clear()	清空List中的所有元素
boolean contains(Object o)	判斷元素o是否存在于List中，存在返回true
int indexOf(Object o)	返回元素o在List中第一次出現的下標，若不存在則返回-1
int lastIndexOf(Object o)	返回元素o在List中最后一次出現的下標，若不存在則返回-1
List<E> subList(int fromIndex, int toIndex)	截取List中從fromIndex（包含）到toIndex（不包含）的部分元素，組成一個新的List返回

需要注意的是，List是一個接口，不能直接實例化使用。如果要使用List，必須實例化它的實現類，在Java集合框架中，ArrayList和LinkedList是List接口的常用實現類，本文后續將重點介紹ArrayList。

二、線性表與順序表基礎

在深入了解ArrayList之前，我們先來回顧一下線性表和順序表的相關概念，這是理解ArrayList底層原理的基礎。

2.1 線性表

線性表（linear list）是由n個具有相同特性的數據元素組成的有限序列，它是一種在實際應用中廣泛使用的數據結構。常見的線性表包括順序表、鏈表、棧、隊列等。

線性表在邏輯上呈現為線性結構，就像一條連續的直線，元素之間存在著一對一的相鄰關系。但在物理存儲結構上，線性表并不一定是連續的，它通常以數組和鏈式結構這兩種形式進行存儲。

2.2 順序表

順序表是線性表的一種常見實現方式，它使用一段物理地址連續的存儲單元來依次存儲數據元素，一般情況下是通過數組來實現的。在順序表中，我們可以基于數組完成數據的增刪查改等操作。

自定義順序表（MyArrayList）實現

1. 前期準備：自定義異常類

為了更清晰地處理“空表操作”和“非法索引”這兩類錯誤，我們定義兩個運行時異常（繼承自RuntimeException）：

• 空表異常：當操作空表時拋出

public class EmptyException extends RuntimeException {public EmptyException(String message) {super(message);}
}

• 索引非法異常：當索引超出有效范圍時拋出

public class PosIllegalException extends RuntimeException {public PosIllegalException(String message) {super(message);}
}

2. MyArrayList核心結構

首先定義順序表的成員變量和構造方法，完成初始初始化：

import java.util.Arrays;public class MyArrayList {// 1. 成員變量private static final int DEFAULT_CAPACITY = 10; // 默認初始容量（10）private int[] array; // 底層數組：存儲數據private int size = 0; // 有效元素個數：初始為0（空表）// 2. 構造方法：默認初始化（容量10）public MyArrayList() {this.array = new int[DEFAULT_CAPACITY];}
}

3. 工具方法：簡化重復邏輯

先實現兩個通用工具方法，避免后續操作中重復編寫邊界校驗代碼：

（1）判斷空表與容量滿

• 判斷是否為空表

public boolean isEmpty() {return size == 0;
}

• 判斷容量是否已滿

public boolean isFull() {return size == array.length;
}

（2）邊界校驗

• 校驗索引合法性：pos必須在 [0, size) 范圍內

public void checkPos(int pos) throws PosIllegalException {if (pos < 0 || pos >= size) {throw new PosIllegalException("索引非法！當前有效元素個數：" + size + "，傳入索引：" + pos);}
}

• 校驗是否為空表：空表不允許執行“獲取元素”“刪除元素”等操作

public void checkEmpty() throws EmptyException {if (isEmpty()) {throw new EmptyException("操作失敗！當前順序表為空");}
}

（3）動態擴容

當容量滿（isFull() == true）時，通過Arrays.copyOf()將數組容量擴大為原來的2倍，實現“動態增長”：

public void grow() {// 擴容邏輯：新數組容量 = 原容量 * 2this.array = Arrays.copyOf(this.array, this.array.length * 2);System.out.println("擴容成功！新容量：" + this.array.length);
}

4. 核心功能實現：增刪改查

（1）添加元素

添加元素分為兩種場景：尾插（默認添加到表尾）和指定位置插入（插入到索引pos處）。

① 尾插 add(int e)

先判斷是否滿容量，滿則擴容；再將元素放入array[size]，最后size++（有效元素個數+1）。

public void add(int e) {if (isFull()) {grow(); }array[size] = e; size++; 
}

② 指定位置插入 add(int pos, int e)

先校驗索引合法性，再判斷是否擴容；然后將[pos, size-1]的元素向后移動1位，最后在pos處放入元素并size++。

public void add(int pos, int e) {try {checkPos(pos); if (isFull()) {grow(); }// 元素后移：從最后一個元素（size-1）開始，到pos結束，依次向后移1位for (int i = size - 1; i >= pos; i--) {array[i + 1] = array[i];}array[pos] = e; size++; } catch (PosIllegalException e) {e.printStackTrace(); }
}

（2）查詢元素

查詢分為兩種場景：根據索引查元素（getElement(int pos)）和根據元素查索引（indexOf(int e)），以及判斷元素是否存在（contains(int toFind)）。

① 根據索引查元素

先校驗空表和索引合法性，再直接返回array[pos]（隨機訪問，O(1)）。

public int getElement(int pos) {try {checkEmpty(); checkPos(pos);return array[pos]; } catch (EmptyException | PosIllegalException e) {e.printStackTrace();}return -1; // 異常時返回默認值}

② 根據元素查索引

遍歷[0, size-1]的元素，找到第一個匹配的元素并返回其索引；未找到則返回-1。

public int indexOf(int e) {for (int i = 0; i < size; i++) {if (array[i] == e) {return i;}}return -1;
}

③ 判斷元素是否存在

復用indexOf()方法，若返回值 != -1則表示元素存在。

// 判斷元素toFind是否在順序表中
public boolean contains(int toFind) {return indexOf(toFind) != -1;
}

（3）修改元素（set(int pos, int e)）

先校驗索引合法性，再直接將array[pos]賦值為新元素（O(1)操作）。

// 將索引pos處的元素修改為e
public void set(int pos, int e) {checkPos(pos); // 校驗索引合法性array[pos] = e; // 直接修改
}

（4）刪除元素（remove(int e)）

先校驗空表，再通過indexOf()找到元素索引；若存在，將[pos+1, size-1]的元素向前移動1位，最后size--（有效元素個數-1）。

public void remove(int e) {try {checkEmpty(); int pos = indexOf(e);if (pos == -1) {System.out.println("刪除失敗！元素" + e + "不存在");return;}// 元素前移：從pos+1開始，到size-1結束，依次向前移1位for (int i = pos; i < size - 1; i++) {array[i] = array[i + 1];}size--; } catch (EmptyException e) {e.printStackTrace();}
}

（5）其他輔助功能

• 清空順序表：只需將size置為0（無需清空數組，后續添加會覆蓋）

public void clear() {size = 0;
}

• 打印順序表所有元素

public void display() {try {checkEmpty(); // 校驗是否空表for (int i = 0; i < size; i++) {System.out.print(array[i] + " ");}System.out.println(); // 換行} catch (EmptyException e) {e.printStackTrace();}
}

• 獲取有效元素個數

public int getSize() {return size;
}

三、ArrayList詳解

3.1 ArrayList的簡介

ArrayList是Java集合框架中的一個普通類，它實現了List接口，同時還實現了RandomAccess、Cloneable和Serializable接口，這使得ArrayList具備了多種特性：

1. 泛型實現：ArrayList是以泛型方式實現的，在使用時必須先進行實例化，指定要存儲的元素類型，這樣可以保證類型安全，避免在運行時出現類型轉換異常。
2. 支持隨機訪問：由于實現了RandomAccess接口，ArrayList支持通過下標快速訪問元素，這也是ArrayList相較于LinkedList的一個重要優勢。
3. 可克隆：實現Cloneable接口表明ArrayList是可以被克隆的，我們可以通過調用clone()方法來創建一個ArrayList對象的副本。
4. 可序列化：實現Serializable接口意味著ArrayList支持序列化操作，能夠將對象轉換為字節流進行傳輸或持久化存儲，在需要的時候再將字節流恢復為對象。
5. 線程不安全：與Vector不同，ArrayList不是線程安全的。在單線程環境下可以放心使用，而在多線程環境中，如果需要保證線程安全，可以選擇使用Vector或者CopyOnWriteArrayList。
6. 動態順序表：ArrayList的底層是一段連續的存儲空間，并且能夠根據元素的添加情況進行動態擴容，本質上是一個動態類型的順序表。

3.2 ArrayList的構造方法

ArrayList提供了三種常用的構造方法，以滿足不同的創建需求，具體如下表所示：

方法	解釋
ArrayList()	無參構造方法，創建一個初始容量為空的ArrayList對象，在后續添加元素時會進行動態擴容
ArrayList(Collection<? extends E> c)	利用其他實現了Collection接口的集合c來構建ArrayList，將集合c中的所有元素添加到新創建的ArrayList中
ArrayList(int initialCapacity)	指定ArrayList的初始容量initialCapacity，創建一個具有指定初始容量的ArrayList對象，這種方式可以在已知大致元素數量的情況下，減少后續擴容的次數，提高性能

下面通過代碼示例來展示ArrayList的創建方式：

public static void main(String[] args) {// 構造一個空的ArrayList，推薦寫法，指定存儲Integer類型元素List<Integer> list1 = new ArrayList<>();// 構造一個初始容量為10的ArrayListList<Integer> list2 = new ArrayList<>(10);list2.add(1);list2.add(2);list2.add(3);// list2.add("hello"); // 編譯失敗，因為List<Integer>已限定只能存儲Integer類型元素// 利用已有的list2構造list3，構造好之后list3與list2中的元素一致ArrayList<Integer> list3 = new ArrayList<>(list2);// 不推薦的寫法，省略了元素類型，這樣list4可以存儲任意類型的元素，使用時容易出現問題List list4 = new ArrayList();list4.add("111");list4.add(100);
}

3.3 ArrayList的常見操作

ArrayList的常用操作方法與List接口中定義的方法基本一致，下面通過代碼示例來演示這些方法的具體使用：

public static void main(String[] args) {List<String> list = new ArrayList<>();// 向list中添加元素list.add("JavaSE");list.add("JavaWeb");list.add("JavaEE");list.add("JVM");list.add("測試課程");System.out.println(list); // 輸出：[JavaSE, JavaWeb, JavaEE, JVM, 測試課程]// 獲取list中有效元素的個數System.out.println(list.size()); // 輸出：5// 獲取和設置指定下標位置的元素，注意下標必須在[0, size)范圍內System.out.println(list.get(1)); // 輸出：JavaWeblist.set(1, "JavaWEB");System.out.println(list.get(1)); // 輸出：JavaWEB// 在指定下標位置插入元素，該位置及后續元素會統一向后搬移一個位置list.add(1, "Java數據結構");System.out.println(list); // 輸出：[JavaSE, Java數據結構, JavaWEB, JavaEE, JVM, 測試課程]// 刪除指定元素，找到后刪除，該元素之后的元素會統一向前搬移一個位置list.remove("JVM");System.out.println(list); // 輸出：[JavaSE, Java數據結構, JavaWEB, JavaEE, 測試課程]// 刪除指定下標位置的元素，注意下標不要超過有效元素個數，否則會拋出下標越界異常list.remove(list.size() - 1);System.out.println(list); // 輸出：[JavaSE, Java數據結構, JavaWEB, JavaEE]// 檢測list中是否包含指定元素，包含返回true，否則返回falseif (list.contains("測試課程")) {list.add("測試課程");}System.out.println(list); // 輸出：[JavaSE, Java數據結構, JavaWEB, JavaEE]（因為list中不包含"測試課程"，所以未添加）// 查找指定元素第一次和最后一次出現的位置list.add("JavaSE");System.out.println(list.indexOf("JavaSE")); // 輸出：0（從前往后找）System.out.println(list.lastIndexOf("JavaSE")); // 輸出：4（從后往前找）// 截取list中[0, 4)之間的元素，構成一個新的SubList返回，注意新列表與原列表共用同一個存儲數組List<String> ret = list.subList(0, 4);System.out.println(ret); // 輸出：[JavaSE, Java數據結構, JavaWEB, JavaEE]// 清空list中的所有元素list.clear();System.out.println(list.size()); // 輸出：0
}

注意：

1. remove方法可以通過傳入元素或下標刪除，構成重載。如果順序表中存放的是整形，要通過元素進行移除，就要傳入對象而非整形。
   例如：移除元素1

list.remove(new Integer(1));

2. subList()只是拿到了列表的下標，返回的列表與原列表共用同一個存儲數組。因此對返回的列表修改，也會改變原列表。

//list1={1,2,3,4,5}
List<Integer> list2 = list.subList(1,3);
list2.set(0,99);
System.out.println(list1);//輸出{1,99,3,4,5}

3.4 ArrayList的遍歷方式

ArrayList提供了三種常用的遍歷方式，分別是for循環+下標、foreach循環以及使用迭代器，下面通過代碼示例進行展示：

public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);

• 方式一：使用下標+for循環遍歷

    for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}System.out.println(); // 輸出：1 2 3 4 5 

• 方式二：借助foreach循環遍歷

    for (Integer integer : list) {System.out.print(integer + " ");}System.out.println(); // 輸出：1 2 3 4 5 

• 方式三：使用迭代器遍歷

    Iterator<Integer> it = list.listIterator();//獲取迭代器while (it.hasNext()){ //如果有下一個元素就向后移動，并打印System.out.print(it.next() + " ");}System.out.println(); // 輸出：1 2 3 4 5 
}

在實際開發中，ArrayList最常用的遍歷方式是for循環+下標和foreach循環。迭代器是一種設計模式，它提供了一種統一的遍歷集合元素的方式，在后續接觸更多容器時，會對迭代器有更深入的了解。

3.5 ArrayList的擴容機制

ArrayList是一個動態類型的順序表，這意味著在向其中添加元素的過程中，如果底層的存儲空間不足，它會自動進行擴容。下面我們通過分析ArrayList的源碼來深入了解其擴容機制。

首先來看ArrayList中的一些關鍵成員變量：

// 用于存儲元素的數組
Object[] elementData; 
// 默認的空數組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; 
// 默認的初始容量大小
private static final int DEFAULT_CAPACITY = 10; 

當我們調用add(E e)方法向ArrayList中添加元素時，會首先調用ensureCapacityInternal(size + 1)方法來確保底層數組有足夠的空間存儲新元素，具體代碼如下：

public boolean add(E e) {ensureCapacityInternal(size + 1); // 確保數組容量足夠，size為當前元素個數elementData[size++] = e; // 將新元素添加到數組中，并將元素個數加1return true;
}

ensureCapacityInternal方法又會調用ensureExplicitCapacity方法，而ensureExplicitCapacity方法會先判斷是否需要擴容，如果需要則調用grow方法進行擴容，代碼如下：

private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}private static int calculateCapacity(Object[] elementData, int minCapacity) {// 如果當前數組是默認的空數組，返回默認初始容量（10）和minCapacity中的較大值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);
}

grow方法是ArrayList擴容的核心方法，它會根據當前數組的長度計算新的容量，并進行擴容操作，具體代碼如下：

// 數組的最大容量，為Integer.MAX_VALUE - 8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;private void grow(int minCapacity) {// 獲取當前數組的長度（舊容量）int oldCapacity = elementData.length;// 預計按照1.5倍的方式擴容（通過右移一位實現，相當于oldCapacity * 0.5）int newCapacity = oldCapacity + (oldCapacity >> 1);// 如果計算出的新容量小于所需的最小容量，就將新容量設置為所需的最小容量if (newCapacity - minCapacity < 0)newCapacity = minCapacity;// 如果新容量超過了數組的最大容量，需要重新計算新容量if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// 調用Arrays.copyOf方法創建一個新的數組，并將原數組中的元素拷貝到新數組中，完成擴容elementData = Arrays.copyOf(elementData, newCapacity);
}private static int hugeCapacity(int minCapacity) {// 如果所需的最小容量小于0，說明發生了內存溢出，拋出OutOfMemoryError異常if (minCapacity < 0)throw new OutOfMemoryError();// 如果所需的最小容量大于數組的最大容量，返回Integer.MAX_VALUE，否則返回數組的最大容量return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

綜合以上源碼分析，我們可以將ArrayList的擴容機制總結為以下幾個步驟：

1. 檢測擴容需求：在添加元素時，首先計算所需的最小容量，然后判斷當前數組的容量是否能夠滿足該需求，如果不能則觸發擴容操作。
2. 計算新容量：
   • 初步預估新容量為當前容量的1.5倍（通過oldCapacity + (oldCapacity >> 1)計算）。
   • 如果預估的新容量小于所需的最小容量，就將新容量設置為所需的最小容量。
   • 在確定最終新容量之前，還會檢測新容量是否超過了數組的最大容量（Integer.MAX_VALUE - 8），如果超過則根據所需最小容量的大小，將新容量設置為Integer.MAX_VALUE或數組的最大容量。
3. 執行擴容：調用Arrays.copyOf方法創建一個具有新容量的數組，并將原數組中的元素拷貝到新數組中，從而完成擴容操作。

3.6 ArrayList的問題與思考

雖然ArrayList在很多場景下都非常實用，但它也存在一些問題：

1. 插入刪除效率低：由于ArrayList底層使用連續的存儲空間，當在任意位置插入或刪除元素時，需要將該位置后續的元素整體往前或往后搬移，這會導致插入和刪除操作的時間復雜度為O(N)，在元素數量較多時，效率較低。
2. 擴容消耗：當ArrayList需要擴容時，需要申請新的存儲空間，將原數組中的元素拷貝到新數組中，然后釋放舊的存儲空間，這個過程會產生一定的系統開銷。
3. 空間浪費：ArrayList的擴容通常是按照當前容量的1.5倍進行的，這就可能導致一定的空間浪費。例如，當前容量為100，當元素填滿后會擴容到200，如果之后只再插入5個元素，那么就會浪費95個元素的存儲空間。

那么，如何解決這些問題呢？這就需要我們根據具體的業務場景選擇合適的數據結構。例如，如果需要頻繁進行插入和刪除操作，可以考慮使用LinkedList，它通過鏈式存儲結構，避免了元素的整體搬移，插入和刪除操作的效率更高，但隨機訪問效率較低。在實際開發中，我們需要根據數據的操作特點，權衡各種數據結構的優缺點，選擇最適合的方案。