List系列的集合核心設計： 針對有序、可重復的集合設計,整體架構

list接口

List接口是Collection的子接口

public interface List<E> extends Collection<E> {

list 核心特性以及擴展Collection的體現

1.有序性：元素按照插入順序存儲，并保留該順序

        List<String> mainList = new ArrayList<>();mainList.add("A");mainList.add("B");System.out.println(mainList);//[A, B]

2.索引訪問:可以通過索引（從0開始）來訪問、搜索、插入和刪除元素

①.根據索引操作元素

public interface List<E> extends Collection<E> {//(1) 元素操作 通過索引（int index）精確訪問add(int index, E element);//在指定索引處插入元素get(int index);// 獲取列表中指定索引位置的元素set(int index, E element) //替換指定索引處的元素，返回舊值remove(int index);//刪除指定索引處的元素，返回被刪除的元素}

示例

List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
list.add(1, "X");  // [A, X, B, C]
String old = list.set(2, "Y");  // old = "B"，新列表 [A, X, Y, C]

②.支持通過索引進行搜索，這些在Collection接口中是沒有的

public interface List<E> extends Collection<E> {//List 支持基于順序的元素搜索，提供更豐富的定位方法int indexOf(Object o);//返回元素第一次出現的索引，不存在則返回 -1int lastIndexOf(Object o);//返回元素最后一次出現的索引，不存在則返回 -1}

示例

List<Integer> nums = Arrays.asList(1, 3, 5, 3, 7);
int firstIndex = nums.indexOf(3);     // -1
int firstIndex2 = nums.indexOf(2);     // 1
int lastIndex = nums.lastIndexOf(3);  // 3
int firstIndex2 = nums.indexOf(2);     // -1

3.允許重復元素：可以包含重復的元素
4.允許null元素:可以包含null元素

        List<String> mainList = new ArrayList<>();mainList.add(null);mainList.add(null);mainList.add(null);System.out.println(mainList);//[null, null, null]

5.子列表subList的支持
ubList方法，可以獲取子列表，需要特定索引位置分割原集合，這也是List獨有的特性

public interface List<E> extends Collection<E> {//List 支持通過索引范圍截取子列表，生成與原列表聯動的視圖：List<E> subList(int fromIndex, int toIndex);//返回列表中指定區間的子列表（視圖，修改影響原列表）}

代碼示例

List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C", "D"));
List<String> sub = list.subList(1, 3);  // [B, C] 截取到的子列表 包含前索引1元素，不包含后索引3元素
sub.set(0, "X");  // sub列表變成[X, C]，同時聯動變動 原列表變為 [A, X, C, D]
list.add("E"); //截取了子列表sub再變更原列表，之后再遍歷sub會報錯
System.out.println(sub)// 打印sub就是遍歷sub，報錯拋出ConcurrentModificationException異常

注意事項:
1.subList(1, 3)截取原列表參數索引范圍不能超過列表元素數量大小，否則報錯
2.subList(1, 3)截取原列表參數索引范圍截取元素是 是 前索引參數<=截取子列表 < 后索引參數
3.修改子列表元素內容會聯動更改原列表內容
4.截取了子列表sub再變更原列表，這個時候打印sub列表(打印sub列表就是遍歷sub列表)會報錯拋出ConcurrentModificationException異常，快速失敗機制(fail-fast)

6.批量操作增強
List 擴展了批量操作方法，支持基于索引的批量操作

	//在指定位置插入集合的所有元素（Collection 的 addAll() 只能追加到末尾）boolean addAll(int index, Collection<? extends E> c);

示例代碼

List<String> list = new ArrayList<>(Arrays.asList("A", "D"));
List<String> toAdd = Arrays.asList("B", "C");
list.addAll(1, toAdd);  // 結果 [A, B, C, D]

7.雙向迭代器ListIterator
List特有的迭代器ListIterator允許雙向遍歷以及修改元素，而Collection的迭代器Iterator只能單向遍歷

List 提供增強的迭代器ListIterator，支持雙向遍歷和修改

public interface List<E> extends Collection<E> {ListIterator<E> listIterator();//返回列表迭代器（支持雙向遍歷和修改）ListIterator<E> listIterator(int index);//從指定位置開始的列表迭代器
}

返回一個 增強的迭代器ListIterator，該迭代器特有的方法

boolean hasPrevious()：是否有前驅元素
E previous()：返回前驅元素
void add(E e)：在當前位置插入元素
void set(E e)：替換最近訪問的元素

代碼示例，先看普通迭代器的

        List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C", "D"));Iterator<String> iterator = list.iterator();//while (iterator.hasNext()){String s = iterator.next();if(s.equals("B")){//普通迭代器 iterator沒有新增或者替換元素的方法，僅有刪除元素的操作方法iterator .remove(); // 刪除元素"B"//如果操作集合list的方法在B后插入 Xlist.add("X");  //報錯ConcurrentModificationException 快速失敗機制}}

快速失敗機制：允許遍歷集合時候進行操作集合內容，modCount變更導致拋出異常

雙向增強迭代器ListIterator

        List<String> list = new ArrayList<>();list.add("A");list.add("B");list.add("C");list.add("D");ListIterator<String> listIterator = list.listIterator();//此時list [A, B, C, D]//正向遍歷列表while (listIterator.hasNext()){String s = listIterator.next();if(s.equals("B")){listIterator.set("b");//將元素B 替換為blistIterator.add("X"); //在b后插入 ,這個時候的集合元素是 [A, b, X, C, D]}} // 此時集合 [A, b, X, C, D]//反向遍歷列表while (listIterator.hasPrevious()){ // 判斷前驅元素是否存在String s = listIterator.previous(); // 獲取前驅元素if(s.equals("D")){listIterator.set("d");listIterator.add("X");  // 在d前插入X ,集合元素是[A, B, C, X, d]}} // 最終[A, b, X, C, X, d]

需要注意的是: 使用列表迭代器（ListIterator），并且希望從列表的末尾開始反向遍歷，那么需要先通過正向遍歷將指針移動到列表的末尾。這是因為列表迭代器的默認行為是從列表的開頭開始遍歷，如果沒有正向迭代遍歷，上來就使用反向遍歷方式，不會報錯但什么也獲取不到，另外反向遍歷列表的方法使用和正向列表的方法使用上一致，只是方向不同

		List<String> list = new ArrayList<>();list.add("A");list.add("B");list.add("C");list.add("D");ListIterator<String> listIterator = list.listIterator();System.out.println(list); // [A, B, C, D]//反向遍歷列表while (listIterator.hasPrevious()){ // 判斷前驅元素是否存在String s = listIterator.previous(); // 獲取前驅元素if(s.equals("D")){listIterator.set("d");listIterator.add("X");  // 在d前插入X ,這個時候的集合元素是[A, B, C, X, d]}}System.out.println(list); // 還是[A, B, C, D]

抽象類 AbstractList

提供核心抽象方法必須由子類實現 和 默認通用方法實現邏輯 AbstractList介紹詳情

抽象類 AbstractSequentialList (簡化鏈表的順序訪問)

繼承自 AbstractList，用于簡化順序訪問數據存儲（如鏈表）的實現。與 AbstractList 相比，它更適合于鏈式結構，因為它通過重寫迭代器功能來實現隨機訪問操作（如 get(int index) 和 set(int index, E element)）

public abstract class AbstractSequentialList<E> extends AbstractList<E> {

繼承結構：

AbstractSequentialList 核心特點

1.順序訪問優化：
它要求子類必須實現 listIterator() 方法，所有的操作（如 get、set、add、remove）都基于這個迭代器完成
2.不支持隨機訪問
由于底層是順序訪問結構（如鏈表），所以隨機訪問效率低（需要遍歷）。因此，它通過迭代器來順序操作元素，避免直接使用索引。
3.方法實現：

• get(int index): 通過 listIterator(index) 定位到索引位置，然后獲取元素。
• set(int index, E element): 使用迭代器定位并替換元素。
• add(int index, E element): 使用迭代器在指定位置插入元素。
• remove(int index): 使用迭代器移除指定位置元素

自定義實現示例代碼講解其實現原理

本質是把迭代鏈接適合，每次的迭代遍歷累加計數 作為索引位置
比起數組結構可以直接獲取索引位置的值來看，雖然時間復雜度還是0，但是至少有個索引值了，能符合List集合架構的特性了

import java.util.*;public class SinglyLinkedList<E> extends AbstractSequentialList<E> {private Node<E> head;private int size = 0;private static class Node<E> {E data;Node<E> next;Node(E data) {this.data = data;}}@Overridepublic int size() {return size;}@Overridepublic ListIterator<E> listIterator(int index) {if (index < 0 || index > size)throw new IndexOutOfBoundsException("Index: " + index);return new SinglyListIterator(index);}private class SinglyListIterator implements ListIterator<E> {private Node<E> lastReturned;private Node<E> next;private int nextIndex;private Node<E> previous; // 用于刪除操作SinglyListIterator(int index) {next = head;previous = null;for (nextIndex = 0; nextIndex < index; nextIndex++) {previous = next;next = next.next;}}@Overridepublic boolean hasNext() {return nextIndex < size;}@Overridepublic E next() {if (!hasNext()) throw new NoSuchElementException();lastReturned = next;previous = next; // 記錄前一個節點用于刪除next = next.next;nextIndex++;return lastReturned.data;}@Overridepublic boolean hasPrevious() {// 單向鏈表不支持向前遍歷return false;}@Overridepublic E previous() {// 單向鏈表不支持throw new UnsupportedOperationException();}@Overridepublic int nextIndex() {return nextIndex;}@Overridepublic int previousIndex() {return nextIndex - 1;}@Overridepublic void remove() {if (lastReturned == null) throw new IllegalStateException();if (lastReturned == head) {head = head.next;} else {previous.next = lastReturned.next;}lastReturned = null;size--;nextIndex--;}@Overridepublic void set(E e) {if (lastReturned == null)throw new IllegalStateException();lastReturned.data = e;}@Overridepublic void add(E e) {Node<E> newNode = new Node<>(e);if (head == null) {head = newNode;} else if (previous == null) {newNode.next = head;head = newNode;} else {newNode.next = previous.next;previous.next = newNode;}size++;nextIndex++;previous = newNode;lastReturned = null;}}public static void main(String[] args) {SinglyLinkedList<String> list = new SinglyLinkedList<>();// 添加元素list.add("Apple");list.add("Banana");list.add("Cherry");System.out.println("初始列表: " + list);// 在索引1處插入list.add(1, "Blueberry");System.out.println("插入后: " + list);// 刪除索引2處的元素list.remove(2);System.out.println("刪除后: " + list);// 使用迭代器修改ListIterator<String> it = list.listIterator();it.next(); // Appleit.set("Apricot");System.out.println("修改后: " + list);// 使用迭代器添加it.next(); // Blueberryit.add("Blackberry");System.out.println("添加后: " + list);}
}

輸出結果:

初始列表: [Apple, Banana, Cherry]
插入后: [Apple, Blueberry, Banana, Cherry]
刪除后: [Apple, Blueberry, Cherry]
修改后: [Apricot, Blueberry, Cherry]
添加后: [Apricot, Blueberry, Blackberry, Cherry]

AbstractSequentialList 總結

注意事項
1.迭代器必須實現：
子類只需實現 listIterator() 和 size() 方法，其他方法（如 add(int index, E element)）由父類通過迭代器實現
2.性能考慮：
由于所有基于索引的操作都通過迭代器遍歷實現，所以 get(index) 的時間復雜度是 O(n)，不適合頻繁隨機訪問。
3.雙向迭代器：
如果底層數據結構支持（如雙向鏈表），應實現完整的 ListIterator（包括向前遍歷）。單向鏈表則無法高效實現 previous(),這點參考上面講解的List核心特性里面的雙向迭代器

使用場景
1.當你要實現一個基于鏈表或順序訪問的數據結構時，繼承 AbstractSequentialList 比繼承 AbstractList 更方便。
2.因為隨機訪問操作（如 get(index)）在鏈表中效率低，所以 AbstractSequentialList 已經幫你用迭代器實現了這些方法，你只需要實現迭代器即可

與AbstractList的對比

特性	AbstractSequentialList	AbstractList
訪問方式	順序訪問	隨機訪問
適合數據結構	鏈表、順序存儲	數組、支持隨機訪問的結構
核心實現方法	listIterator()	get(), set(), add(), remove()
隨機訪問性能	O(n)	O(1)（理想情況）
子類示例	LinkedList	ArrayList, Vector

AbstractSequentialList 通過迭代器實現了所有隨機訪問操作，使得鏈表類集合的實現更加簡單高效

List 實現類 ArrayList

ArrayList是List集合框架種最核心的實現類之一，也是最常用的集合類

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable

實現 List 接口：支持有序、可重復元素和索引訪問。
實現 RandomAccess 接口：標志支持 O(1) 時間復雜度的隨機訪問（如 get(index)）58。
實現 Cloneable、Serializable 接口：支持深拷貝和序列化

ArrayList 底層數據結構及其實現原理

底層是一個動態數組結構 = 初始一維數組(默認容量16 可自定義容量大小)+自動擴容，動態數組具體實現原理詳細介紹

ArrayList 核心特性

1.作為List集合最核心的實現類，支持有序、可重復元素和索引訪問的特性
2.基于動態數組的數據結構，訪問速度塊
3.非線程安全：多線程并發修改可能引發 ConcurrentModificationException
解決方案
a.使用 Collections.synchronizedList(new ArrayList<>()) 包裝

List<String> list = Collections.synchronizedList(new ArrayList<String>());
list.add("1");
list.add("2");
list.add("3");synchronized (list) {Iterator<String> i = list.iterator();// Must be in synchronized blockwhile (i.hasNext()) {System.out.println(i.next());}
}

b.改用線程安全的 CopyOnWriteArrayList（讀多寫少場景）

ArrayList 的常見操作方式

1.基礎操作

ArrayList<String> list = new ArrayList<>();
list.add("Apple");         // 尾部添加
list.add(1, "Banana");     // 指定位置插入
list.set(0, "Cherry");     // 替換元素
list.remove(1);            // 刪除索引1的元素
String item = list.get(0); // 獲取元素

2.遍歷方式

// 1. for循環（隨機訪問高效）
for (int i = 0; i < list.size(); i++) {System.out.println(list.get(i));
}// 2. 增強for循環
for (String s : list) {System.out.println(s);
}// 3. Iterator迭代器
Iterator<String> it = list.iterator();
while (it.hasNext()) {System.out.println(it.next());
}

3.存儲自定義對象

class Student {private String name;private int age;// 構造方法/getter/setter
}ArrayList<Student> students = new ArrayList<>();
students.add(new Student("Alice", 20));
students.get(0).getName(); // 訪問屬性

ArrayList 總結

常見操作方法時間復雜度總結

操作	方法	時間復雜度	說明
隨機訪問	get(int index)	O(1)	直接通過數組下標訪問
尾部插入	add(E e)	均攤 O(1)	可能觸發擴容
指定位置插入	add(int index, E e)	O(n)	需移動后續元素（System.arraycopy）
指定位置刪除	remove(int index)	O(n)	需移動后續元素
搜索元素	indexOf(Object o)	O(n)	遍歷數組匹配

適用場景與替代方案
1.推薦場景：
a.頻繁隨機訪問（如按索引查詢）
b.數據量可預測，或尾部插入為主

2.不推薦場景：
a.頻繁在中間位置插入/刪除（改用 LinkedList）
b.高并發寫操作（改用 CopyOnWriteArrayList 或同步包裝類）

ArrayList 的優缺點 總結

優點	缺點
? O(1) 隨機訪問效率高	? 中間插入/刪除效率低（O(n)）
? 內存連續，緩存友好	? 擴容有性能開銷（數據復制）
? 支持泛型與類型安全	? 非線程安全
? API 豐富，易用性強	? 存儲基本類型需裝箱（性能損耗）

合理利用 ArrayList 需結合業務需求：預分配容量、避免中間修改、多線程環境同步控制，方能最大化其動態數組的高效特性

List 實現類 CopyOnWriteArrayList(List中線程安全包裝類)

CopyOnWriteArrayList 是專門為List集合中提供的線程安全的，采用“寫時復制”技術保證線程安全，因為讀不涉及變更集合 也就不涉及什么安全不安全，只關系寫操作

public class CopyOnWriteArrayList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

CopyOnWriteArrayList 核心特性

1.線程安全，這個類的設計初衷
2.支持快速失敗機制：迭代過程更改集合拋出異常
3.迭代弱一性：數據時效性問題,執行操作的結果可能反應 也可能不反應，但是對于這種數據長度統計的集合是致命缺陷，比如 別的集合類型如隊列，add成功或不成功不反應 影響不大，但是這種需要統計索引的集合如果add成功不反應，那么size的值獲取到的不是最新的從而不準確

CopyOnWriteArrayList 線程安全的實現

寫時復制（Copy-On-Write）機制
1.讀操作：

• 直接訪問當前數組，無需加鎖
• 支持高并發讀取

2.寫操作（增、刪、改）：

• 加鎖（ReentrantLock）保證互斥
• 復制底層數組（完整拷貝）
• 在新數組上執行修改
• 將數組引用切換到新數組（volatile 寫保證可見性）

CopyOnWriteArrayList 數據結構及實現原理

1.底層數據結構

// 底層存儲數組（volatile 保證可見性）
private transient volatile Object[] array;
final Object[] getArray() {return array;
}
final void setArray(Object[] a) {array = a;
}

2.讀操作實現

// 無鎖訪問
public E get(int index) {return get(getArray(), index);
}private E get(Object[] a, int index) {return (E) a[index];
}

3.寫操作實現（以 add 為例）

public boolean add(E e) {final ReentrantLock lock = this.lock;lock.lock(); // 1. 加鎖try {Object[] elements = getArray();int len = elements.length;// 2. 創建新數組（長度+1）Object[] newElements = Arrays.copyOf(elements, len + 1);// 3. 在新數組上添加元素newElements[len] = e;// 4. 切換數組引用setArray(newElements);return true;} finally {lock.unlock(); // 5. 釋放鎖}
}

CopyOnWriteArrayList 總結

1.注意事項
a.避免頻繁修改操作，盡可能一起操作
CopyOnWriteArrayList在寫操作時會對整個數組進行復制，多次寫操作多次復制數組 不合算

// 反例：頻繁添加單個元素
for (int i = 0; i < 10000; i++) {cowList.add("item-" + i); // 觸發10000次數組復制！
}
// 正例：批量添加
cowList.addAll(allItems); // 只復制1次

b.慎用 size()
本質是:size() 返回的是調用時刻的數組長度快照,返回后數組可能立即被修改（新數組替換）,返回值與實際集合狀態可能不一致

// size()返回值可能立即過時 不保證后續操作時size仍有效
// 反例：基于size()的循環
for (int i = 0; i < list.size(); i++) {  // 每次循環都調用size()process(list.get(i));
}// 正例：使用快照迭代器
Iterator<String> it = list.iterator();
while (it.hasNext()) {process(it.next());
}

c.迭代器只讀:快速失敗機制

Iterator<String> it = cowList.iterator();
while (it.hasNext()) {it.remove(); // 拋出 UnsupportedOperationException
}這是因為迭代器基于創建時的數組快照：所有修改操作均不支持
public Iterator<E> iterator() {return new COWIterator<E>(getArray(), 0);
}static final class COWIterator<E> implements ListIterator<E> {// 快照數組（不會變化）private final Object[] snapshot;private int cursor;COWIterator(Object[] es, int initialCursor) {cursor = initialCursor;snapshot = es; // 固定為創建時的數組}public boolean hasNext() {return cursor < snapshot.length;}public E next() {if (!hasNext()) throw new NoSuchElementException();return (E) snapshot[cursor++];}// 所有修改操作均不支持public void remove() {throw new UnsupportedOperationException();}
}

2.性能對比

操作	ArrayList	Collections.synchronizedList	CopyOnWriteArrayList
并發讀	不安全	阻塞（鎖競爭）	??? 無鎖高性能
并發寫	不安全	阻塞（鎖競爭）	? 復制開銷大
迭代安全	不安全	需手動同步	??? 基于快照安全
內存占用	低	低	?? 寫時復制翻倍
寫后讀一致性	-	強一致性	?? 弱一致性

CopyOnWriteArrayList 核心 優勢

特性	說明
線程安全	寫操作通過鎖互斥，讀操作無鎖
讀高性能	讀操作完全無鎖，支持高并發讀
迭代安全	迭代器基于創建時的數組快照
弱一致性	讀操作可能看到過時數據

CopyOnWriteArrayList 局限性

限制	影響
內存消耗	寫操作需復制整個數組
數據實時性	讀操作可能獲取舊數據
寫性能低	大集合寫操作成本高
不支持修改迭代器	迭代器只讀（調用 remove 拋異常）

3.最佳實踐

CopyOnWriteArrayList 使用示例代碼

1.基礎操作

CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();// 并發添加元素
ExecutorService executor = Executors.newFixedThreadPool(5);
for (int i = 0; i < 10; i++) {final int index = i;executor.submit(() -> {list.add("Item-" + index);});
}// 安全迭代（基于快照）
Iterator<String> it = list.iterator();
while (it.hasNext()) {System.out.println(it.next()); // 迭代過程中可修改原列表
}

2.事件監聽器場景

class EventBus {private final CopyOnWriteArrayList<EventListener> listeners = new CopyOnWriteArrayList<>();// 添加監聽器（線程安全）public void register(EventListener listener) {listeners.add(listener);}// 觸發事件（無需鎖）public void fireEvent(Event event) {for (EventListener listener : listeners) {listener.onEvent(event);}}
}

3.原子操作

// 條件添加（不存在時才添加）
boolean added = list.addIfAbsent("UniqueItem");// 批量條件添加
List<String> newItems = Arrays.asList("A", "B", "C");
int addedCount = list.addAllAbsent(newItems);

List 實現類 LinkedList

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}

整個集合框架中最靈活的類之一 LinkedList詳情介紹

這里就總結一下關于List的部分
因為要同時滿足 列表，基本隊列，雙端隊列的數據操作要求，所以LinkedList的底層數據結構得是這三者中最復雜能同時滿足這三種功能需求的，所以只能是 雙向鏈表

如果作為List來看，雖然也有索引位置，但是鏈表的索引獲取是比較復雜的，需要從頭或者尾挨個指向的方式遍歷，而且一旦變更就需要重新遍歷獲取 時間復雜度是O(n)

雙向鏈表的最大特色是 刪除首尾 時間復雜度0(1),只需要斷開鏈接就可以了，但是如果指定位置的刪除時間復雜度就是O(n)+O(1)了，刪除元素之前得先找到這個元素啊

與 ArrayList 對比

特性	LinkedList	ArrayList
底層結構	雙向鏈表	動態數組
隨機訪問	慢 (O(n))	快 (O(1))
頭尾插入/刪除	快 (O(1))	頭慢 (O(n)) 尾快 (O(1))
中間插入/刪除	慢 (O(n))	慢 (O(n))
內存占用	較高 (每個節點額外存儲兩個指針)	較低
內存連續性	非連續	連續

List 總結

核心特征：有序 和 可重復，線程不安全
有序：完全按照插入順序，所以有了索引，基于索引又衍生出很多方法特性
可重復：不關心元素內容 所以可以為null

重要實現類對比

實現類	底層結構	線程安全	隨機訪問	插入/刪除	最佳適用場景
ArrayList	動態數組	?	?? 極快	末尾快/中間慢	讀多寫少，需要快速隨機訪問
LinkedList	雙向鏈表	?	?? 慢（O(n)）	?? 極快	頻繁插入刪除，實現隊列/棧
Vector	動態數組	? (同步方法)	快	慢	遺留代碼（已被 ArrayList 取代）
Stack	數組（繼承Vector）	?	快	末尾快	LIFO 棧結構（推薦用 Deque 替代）
CopyOnWriteArrayList	動態數組	? (寫時復制)	快	慢	讀多寫少的高并發場景