Java基础 集合框架 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);//返回元素第一次出现的索引，不存在则返回 -1
	int 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后插入 X
             list.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 替换为b
                listIterator.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;
        }
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public 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;
            }
        }

        @Override
        public boolean hasNext() {
            return nextIndex < size;
        }

        @Override
        public E next() {
            if (!hasNext()) throw new NoSuchElementException();
            
            lastReturned = next;
            previous = next; // 记录前一个节点用于删除
            next = next.next;
            nextIndex++;
            return lastReturned.data;
        }

        @Override
        public boolean hasPrevious() {
            // 单向链表不支持向前遍历
            return false;
        }

        @Override
        public E previous() {
            // 单向链表不支持
            throw new UnsupportedOperationException();
        }

        @Override
        public int nextIndex() {
            return nextIndex;
        }

        @Override
        public int previousIndex() {
            return nextIndex - 1;
        }

        @Override
        public void remove() {
            if (lastReturned == null) 
                throw new IllegalStateException();
            
            if (lastReturned == head) {
                head = head.next;
            } else {
                previous.next = lastReturned.next;
            }
            
            lastReturned = null;
            size--;
            nextIndex--;
        }

        @Override
        public void set(E e) {
            if (lastReturned == null)
                throw new IllegalStateException();
            lastReturned.data = e;
        }

        @Override
        public 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(); // Apple
        it.set("Apricot");
        System.out.println("修改后: " + list);
        
        // 使用迭代器添加
        it.next(); // Blueberry
        it.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 通过迭代器实现了所有随机访问操作，使得链表类集合的实现更加简单高效

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 block
    while (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 总结

常见操作方法时间复杂度总结

适用场景与替代方案
1.推荐场景：
a.频繁随机访问（如按索引查询）
b.数据量可预测，或尾部插入为主

2.不推荐场景：
a.频繁在中间位置插入/删除（改用 LinkedList）
b.高并发写操作（改用 CopyOnWriteArrayList 或同步包装类）

ArrayList 的优缺点 总结

合理利用 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.性能对比

CopyOnWriteArrayList 核心 优势

CopyOnWriteArrayList 局限性

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 对比

List 总结

核心特征：有序 和 可重复，线程不安全
有序：完全按照插入顺序，所以有了索引，基于索引又衍生出很多方法特性
可重复：不关心元素内容 所以可以为null

重要实现类对比