一、 集合框架頂層抽象與List契約

• Collection⁠ vs ⁠List⁠：⁠Collection⁠只保證能容納元素；⁠List⁠額外增加了元素順序性與精確整數索引存取契約。
• 主要實作分支：
  ⁠ArrayList⁠：底層基於連續動態陣列（Resizable-array）。
  ⁠LinkedList⁠：底層基於雙向鏈結串列（Doubly-linked list）。

二、 ⁠ArrayList⁠底層源碼與擴容機制（Grow Algorithm）

• 延遲初始化（Lazy Allocation）：

1. 使用無參數建構子new ArrayList<>()⁠時，不會立刻配置Heap空間，而是指向共享空陣列⁠DEFAULTCAPACITY_EMPTY_ELEMENTDATA⁠
2. 首次 ⁠add()⁠觸發配置：第一次寫入元素時，底層正式分配預設大小為10⁠的連續陣列。

• 擴容公式與幅度：

1. 觸發條件：元素總數即將超過容量（⁠size + 1 > elementData.length⁠）。
2. 原始碼公式：⁠int newCapacity = oldCapacity + (oldCapacity >> 1);⁠
3. 擴容幅度：新容量為原本的1.5倍（右移1位相當於除以2再相加）。

• 記憶體拷貝成本（System.arraycopy）：

1. 擴容需在 Heap 申請更大一塊連續空間，透過JNI原生呼叫⁠System.arraycopy()⁠逐一搬遷舊陣列引用，舊陣列則丟給GC回收
2. 最佳化守則：若已知資料筆數，建立時務必指定初始容量（如 ⁠new ArrayList<>(1000)⁠），避免頻繁擴容與重複搬遷。

三、 現代硬體架構下極度不推薦LinkedList⁠的三大原因

• 快取局部性（Cache Locality）的降維打擊：

1. CPU以快取行為單位載入資料。
2. ArrayList⁠ 佔用連續記憶體，CPU讀取一筆時會順道載入相鄰元素，快取命中率極高。
3. LinkedList⁠節點分散在Heap各處，遍歷時頻繁發生Cache Miss，迫使CPU不斷向慢速主記憶體重新抓取資料。

• 「中間插入O(1)」的理論謊言：

1. LinkedList⁠只有在指標已指向該節點時插入才是O(1)。
2. 若呼叫list.add(index, data)⁠，底層仍需花O(N)雙向遍歷尋找位置。在數萬筆以內的中小資料集中，⁠ArrayList⁠的記憶體位移拷貝速度遠快於LinkedList⁠的鏈結走訪。

• 節點包裝帶來的記憶體浪費：

1. 每個節點都是獨立的Node⁠物件（包含自身數據引用、⁠next⁠指標、⁠prev⁠指標與12~16 Bytes物件頭）。
2. 存放相同數量資料時，⁠LinkedList⁠額外耗費2～4倍記憶體，大幅加重GC負擔。

四、 快速失敗機制（Fail-Fast）

• modCount⁠ 狀態計數器：⁠ArrayList⁠內部維護⁠modCount⁠變數，只要發生新增或刪除就自動遞增。
• 觸發ConcurrentModificationException⁠：

1. 使用for-each⁠或Iterator⁠走訪時，迭代器會記錄當前⁠expectedModCount⁠。
2. 遍歷途中若直接透過集合本身方法（如list.remove()⁠變更結構，下次迭代發現modCount != expectedModCount⁠，便立即拋出例外阻斷執行。

• 安全刪除途徑：

1. 透過迭代器專屬方法：⁠iterator.remove()⁠。
2. 透過現代Java集合方法：⁠list.removeIf(item -> ...)⁠。

五、 List實作選擇判斷

• 日常開發預設選擇：⁠ArrayList⁠。
• 雙端隊列/佇列結構：避免使用 LinkedList⁠，全面改用 ArrayDeque⁠基於循環陣列，效能全面佔優。
• 併發多執行緒寫入：兩者皆非線程安全，讀多寫少情境考慮⁠CopyOnWriteArrayList⁠，一般情境建議由外部加鎖或搭配併發工具類。