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	动态数组	✅ (写时复制)	快	慢	读多写少的高并发场景