1. 線性表

線性表（Linear List）是n個具有相同特性的數據元素的有限序列。線性表是一種在實際中廣泛使用的數據結構，常見線性表：順序表、鏈表、棧、隊列…

線性表在邏輯上是線性結構，也就是連續的一條直線。但是在物理上不一定是連續的，線性表在物理上存儲時，通常以數組和鏈式結構的形式存儲。

2. 順序表

順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。在數組上完成數據的增刪查改。

順序表的實現

package myDataStructure.ArrayList;/*** @Author: Author* @CreateTime: 2025-03-18* @Description:*/
public interface SeqList<T> {// 新增元素,默認在數組最后新增void add(T data);// 在 pos 位置新增元素void add(int pos, T data);// 判定是否包含某個元素boolean contains(T toFind);// 查找某個元素對應的位置int indexOf(T toFind);// 獲取 pos 位置的元素T get(int pos);// 給 pos 位置的元素設為 valuevoid set(int pos, T value);// 刪除第一次出現的關鍵字keyvoid remove(T toRemove);// 獲取順序表長度int size();// 清空順序表void clear();
}

package myDataStructure.ArrayList;import java.util.Arrays;/*** @Author: Author* @CreateTime: 2025-03-18* @Description: 支持泛型的動態數組的實現*/
public class MyArrayList<T> implements SeqList<T>{private Object[] array; // 內部使用 Object[] 存儲數據，因為 Java 的泛型會在運行時擦除類型信息。private int size;public MyArrayList(){array=new Object[10];}// 動態擴容private void checkCapacity(){if (array.length==size){array=Arrays.copyOf(array,size*2);}}// 添加操作的邊界檢查private void rangeCheckForAdd(int index) {if (index<0||index>size){throw new IndexOutOfBoundsException("index超出范圍");}}// 讀取修改操作的邊界檢查private void rangeCheckForGetAndSet(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("index超出范圍");}}@Overridepublic void add(T data) {checkCapacity();array[size]=data;size++;}@Overridepublic void add(int pos, T data) {checkCapacity();rangeCheckForAdd(pos);for(int i=size;i>pos;i--){array[i]=array[i-1];}array[pos]=data;size++;}@Overridepublic boolean contains(T toFind) {if (toFind==null){// 如果 toFind 是null,直接調用 array[i].equals(toFind) 會導致 NullPointerExceptionfor (int i = 0; i < size; i++) {if (array[i] == null) {return true;}}}else {for (int i=0;i<size;i++){if (array[i].equals(toFind)){return true;}}}return false;}@Overridepublic int indexOf(T toFind) {if (toFind == null) {for (int i = 0; i < size; i++) {if (array[i] == null) {return i;}}} else {for (int i = 0; i < size; i++) {if (toFind.equals(array[i])) {return i;}}}return -1;}@Overridepublic T get(int pos) {rangeCheckForGetAndSet(pos);return (T)array[pos];}@Overridepublic void set(int pos, T value) {rangeCheckForGetAndSet(pos);checkCapacity();array[pos]=value;}@Overridepublic void remove(T toRemove) {int pos=indexOf(toRemove);if (pos==-1){return; // 元素不存在，直接返回}for (int i=pos;i<size-1;i++){array[i]=array[i+1];}array[size-1]=null;// 清理最后一個元素size--;}@Overridepublic int size() {return size;}@Overridepublic void clear() {size=0;}public String toString(){StringBuilder sb = new StringBuilder("[");for (int i = 0; i < size; i++) {sb.append(array[i]);if (i < size - 1) {sb.append(", ");}}sb.append("]");return sb.toString();}
}

3. ArrayList

在集合框架中，ArrayList是一個普通的類，實現了List接口，具體框架圖如下：
圖片

1. ArrayList是以泛型方式實現的，使用時必須要先實例化
2. ArrayList實現了RandomAccess接口，表明ArrayList支持隨機訪問
3. ArrayList實現了Cloneable接口，表明ArrayList是可以clone的
4. ArrayList實現了Serializable接口，表明ArrayList是支持序列化的
5. 和Vector不同，ArrayList不是線程安全的，在單線程下可以使用，在多線程中可以選擇CopyOnWriteArrayList
6. ArrayList底層是一段連續的空間，并且可以動態擴容，是一個動態類型的順序表

4. ArrayList的問題以及思考

##4.1 插入或刪除元素的性能問題（時間復雜度 O(N)）

ArrayList 底層是基于數組實現的，插入或刪除元素時，所有后續元素需要整體移動，導致時間復雜度為 O(N)。

• 使用鏈表（LinkedList）：
  • 對于頻繁插入或刪除操作的場景，LinkedList 是更好的選擇。
  • LinkedList 是基于雙向鏈表實現的，插入和刪除的時間復雜度為 O(1)（只需調整指針），但隨機訪問的時間復雜度為 O(N)。
  • 適用場景：需要頻繁插入或刪除的場景，但隨機訪問較少。
• 使用 ArrayDeque：
  • 如果操作集中在首尾兩端，可以使用 ArrayDeque，它支持高效的首尾插入和刪除操作。
• 優化插入/刪除的邏輯：
  • 如果需要頻繁插入或刪除，盡量批量操作，而不是逐個操作。例如，先將需要插入的數據存儲在臨時集合中，最后一次性合并到目標集合。

4.2 增容的性能消耗問題

ArrayList 增容時需要重新分配新空間，并將舊數組的數據拷貝到新數組中，這會帶來性能開銷。

• 預估容量，合理初始化 ArrayList 的初始容量：

  • 在創建ArrayList時，盡量根據實際需求指定初始容量，避免頻繁增容。例如：

    ArrayList<Integer> list = new ArrayList<>(1000);
    

    這樣可以減少擴容操作的發生。

• 使用 ArrayList.ensureCapacity() 方法：

  • 如果知道大概需要插入的元素數量，可以在插入數據前調用ensureCapacity()方法手動擴容，避免多次增容。例如：

    list.ensureCapacity(1000);
    

• 使用其他動態數據結構：

  • 如果擴容的性能開銷成為瓶頸，可以考慮使用其他動態數據結構（如 LinkedList 或 ArrayDeque），具體選擇取決于場景需求。

4.3 空間浪費問題

ArrayList 增容時容量通常增長為原來的 2 倍，會導致未使用的空間浪費。

• 手動調整容量：

  • 在確定不再需要新增元素時，可以調用ArrayList.trimToSize()方法，將ArrayList的容量調整為當前元素的實際大小，減少空間浪費。例如：

    list.trimToSize();
    

• 使用其他集合類（如 LinkedList）：

  • 如果對空間利用率要求較高，可以考慮使用 LinkedList，因為它的空間分配是動態的，不會預留多余的空間。

• 動態調整容量增長策略：

  • 如果對 ArrayList 的增容策略不滿意，可以自定義一個集合類，繼承自 ArrayList，并重寫其擴容邏輯。例如，可以改為按固定大小增長，而不是倍增。