Java集合框架深入解析：ArrayList & LinkedList

一、 ArrayList 深度解析

核心定义

ArrayList 是基于动态数组实现的有序集合，核心特点：

• 数组是 “定长” 的，但 ArrayList 通过「扩容机制」实现 “动态”；
• JDK8 中无参构造的 ArrayList，初始化时底层数组是空数组（DEFAULTCAPACITY_EMPTY_ELEMENTDATA），首次添加元素时才会扩容为 10；
• 数组的优势：随机访问快（通过索引直接定位，时间复杂度 O (1)）；
• 数组的劣势：增删慢（需要移动元素）、扩容有成本（复制数组）。

1. 底层数组实现机制

1.1 数据结构核心

// ArrayList 核心字段,他和Linkedlist都继承了List<E>接口。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    
    // 实际存储数据的数组
    transient Object[] elementData;  // 关键：非私有，包内可见
    
    // 当前元素数量
    private int size;
    
    // 空数组（优化内存）
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
}

1.2 数组特性深入

内存连续性优势：

// 内存连续性优势
public class MemoryLayoutDemo {
    public static void main(String[] args) {
        // ArrayList：内存连续
        // 内存地址：0x1000 [元素1], 0x1004 [元素2], 0x1008 [元素3]
        // CPU缓存一次加载连续内存块（通常是64字节）
        
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            list.add(i);
        }
        
        // 访问时：CPU预取后续元素到缓存
        // 第一次访问 index=0 时，可能把 0-15 都加载到缓存
        // 后续访问 index=1~15 时命中缓存，速度极快
        
        // 对比 LinkedList：内存分散，缓存不友好
    }
}

2. 扩容机制深度剖析

2.1 扩容流程详解

// 完整的扩容过程
private void grow(int minCapacity) {
    // 1. 记录旧容量
    int oldCapacity = elementData.length;
    
    // 2. 计算新容量（核心：1.5倍）
    int newCapacity = oldCapacity + (oldCapacity >> 1);  // 位运算：右移1位=除以2
    
    // 3. 特殊情况处理
    if (newCapacity - minCapacity < 0)  // 如果1.5倍还不够
        newCapacity = minCapacity;       // 直接使用所需容量
    
    // 4. 处理最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    
    // 5. 数组复制（真正的扩容操作）
    elementData = Arrays.copyOf(elementData, newCapacity);
}

扩容触发条件：当添加元素时，数组的实际元素个数（size）等于数组容量（elementData.length），触发扩容。

oldCapacity >> 1 相当于 “位级写法”的 oldCapacity / 2（效率更高），但有三点要注意：

1. 只向下取整（舍去小数部分），不会四舍五入。
2. 运算对象必须是 整型（byte/short/int/long）。
3. 负数也成立，-7 >> 1 得到 -4，结果仍向负无穷取整。

所以看到

int newCapacity = oldCapacity + (oldCapacity >> 1);

就是

新容量 = 原容量 + 原容量 / 2   ≈ 1.5 倍

这是 ArrayList 扩容时“平滑 1.5 倍”的写法，比直接 / 2 快一点点，习惯上炫技 ,哈哈。

2.2 扩容过程可视化

初始：容量=10，size=0
添加过程：
1. 添加第1个元素：容量10，size=1
2. 添加第11个元素时触发扩容：
   oldCapacity = 10
   newCapacity = 10 + (10 >> 1) = 10 + 5 = 15
   → 扩容到15，复制原数组
   
3. 添加第16个元素时再次扩容：
   oldCapacity = 15
   newCapacity = 15 + (15 >> 1) = 15 + 7 = 22
   → 扩容到22，复制原数组
   
容量增长序列：10 → 15 → 22 → 33 → 49 → 73 → 109 → ...

2.3 扩容性能影响

public class ExpansionCostDemo {
    public static void main(String[] args) {
        // 测试扩容开销
        int testSize = 10000000;
        
        // 情况1：不指定容量（频繁扩容）
        long start1 = System.nanoTime();
        List<Integer> list1 = new ArrayList<>();
        for (int i = 0; i < testSize; i++) {
            list1.add(i);
        }
        long end1 = System.nanoTime();
        
        // 情况2：指定容量（避免扩容）
        long start2 = System.nanoTime();
        List<Integer> list2 = new ArrayList<>(testSize);
        for (int i = 0; i < testSize; i++) {
            list2.add(i);
        }
        long end2 = System.nanoTime();
        
        System.out.printf("未预分配：%.2f ms\n", (end1 - start1) / 1_000_000.0);
        System.out.printf("预分配：%.2f ms\n", (end2 - start2) / 1_000_000.0);
        
        // 结果可能相差数倍！因为数组复制开销很大
    }
}

3. Fail-Fast 机制深度解析

核心定义

fail-fast 是 Java 集合（如 ArrayList、LinkedList、HashMap 等）的错误检测机制，是迭代器的错误检测机制，不是集合的 “功能”，目的是避免数据不一致，且不保证 100% 触发（仅作快速失败提示）。

迭代器遍历 ArrayList 时，若检测到集合被「并发修改」（比如遍历中 add/remove），立即抛出 ConcurrentModificationException，这是一种 “快速失败” 的检测机制，而非线程安全机制。

3.1 机制原理

• ArrayList 有个成员变量 modCount：记录集合被修改的次数（调用集合的add/remove等方法 都会让modCount++）；
• 迭代器创建时，会记录当前的modCount到expectedModCount；
• 遍历过程中，每次next()都会检查 modCount == expectedModCount，不相等则抛异常。

// modCount 机制
public class FailFastDemo {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        
        // 创建迭代器时记录 expectedModCount = modCount
        Iterator<String> iterator = list.iterator();
        
        // 迭代过程中修改列表
        while (iterator.hasNext()) {
            String item = iterator.next();
            System.out.println(item);
            
            if (item.equals("B")) {
                // 这里修改列表，modCount++
                list.remove(item);  // 触发 modCount++（因为这里用的是列表的remove函数，不是迭代器的，此时迭代器会认为外部有人恶意篡改数据，导致脏读。如果用迭代器里的remove函数就不会报错。）
                // iterator.next() 会检查：
                // if (modCount != expectedModCount)
                //     throw new ConcurrentModificationException();
            }
        }
    }
}

• modCount = 列表被结构改动的总次数（ArrayList 的“版本号”）
• expectedModCount = 迭代器诞生那一刻拍下来的快照（迭代器眼里的“当前版本号”）

3.2 源码实现细节

// ArrayList.Itr 迭代器实现
private class Itr implements Iterator<E> {
    int cursor;       // 下一个返回元素的索引
    int lastRet = -1; // 上一个返回元素的索引
    int expectedModCount = modCount;  // 关键！记录创建时的modCount（相当于拍照，为了比较列表是否被动过。）
    
    public boolean hasNext() {
        return cursor != size;
    }
    
    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();  // 每次next都检查
        // ... 其他逻辑
    }
    
    public void remove() {
        // 迭代器自己的remove会同步modCount
        checkForComodification();
        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;  // 更新expectedModCount
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

3.3 Fail-Fast 应用场景

public class ConcurrentModificationCase {
    // 场景1：单线程错误用法
    public void wrongSingleThread() {
        //在初始化ArrayList的时候就存入数组{"A","B","C","D"}
        List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C","D"));
        for (String s : list) {  // 内部使用迭代器
            if (s.equals("B")) {
                list.remove(s);  //会报错,用的是ArrayList自己的remove方法，抛出ConcurrentModificationException
            }
        }
    }
    
    // 场景2：多线程并发修改
    public void multiThreadIssue() {
        List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
        
        Thread t1 = new Thread(() -> {
            Iterator<String> it = list.iterator();
            while (it.hasNext()) {
                System.out.println(it.next());
                try { Thread.sleep(100); } catch (InterruptedException e) {}
            }
        });
        
        Thread t2 = new Thread(() -> {
            try { Thread.sleep(50); } catch (InterruptedException e) {}
            list.add("D");  // 在迭代过程中修改，抛出ConcurrentModificationException
        });
        
        t1.start();
        t2.start();
    }
    
    // 正确做法
    public void correctApproach() {
        List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
        
        // 方法1：使用迭代器的remove方法
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String item = iterator.next();
            if (item.equals("B")) {
                iterator.remove();  // 正确！会更新expectedModCount
            }
        }
        
        // 方法2：使用CopyOnWriteArrayList（并发安全）
        // List<String> safeList = new CopyOnWriteArrayList<>(list);
        
        // 方法3：使用并发集合
        // List<String> concurrentList = Collections.synchronizedList(list);
    }
}

场景一中注释“内部使用迭代器”指的是：
编译器把那句看似简单的

for (String s : list) { … }

偷偷翻译成了带有 Iterator 对象的经典三件套：

for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
    String s = it.next();
    …
}

你写的“增强 for 循环”只是语法糖，字节码里跑的就是迭代器。
因此：

1. 遍历过程中 list.remove(s) 会修改 modCount，而迭代器每次 next() 都会检查 modCount != expectedModCount，不一致就抛 ConcurrentModificationException。
2. 想安全删除，必须用迭代器自己的删除方法

场景二中线程的操作：

线程一先打印出第一个遍历到的元素，然后休眠50毫秒，，此时线程二几乎也同时休眠了50毫秒。然后线程二会进行增加元素的操作，但此时线程一开始next()，如果此时线程一比线程二稍快，也就是线程二增加元素操作慢了一拍的话，线程一next()时候expectedModCount 仍然等于 modCount，此时不会报错，但是等到下一次next()的时候仍然会抛出异常。

所以，经过上面的分析，总结一句：异常是否抛出取决于“迭代器是否还会再检查一次”

4. ArrayList 面试高频问答

问题	标准答案（简洁版）
ArrayList 底层结构？	JDK8 基于动态数组，无参构造初始为空数组，首次 add 扩容到 10。
ArrayList 扩容倍数？	1.5 倍（oldCapacity + oldCapacity >> 1）。
ArrayList 为什么查询快、增删慢？	查询：索引直接定位（O (1)）；增删：需移动元素（O (n)）。
如何优化 ArrayList 性能？	创建时指定初始容量，减少扩容次数；避免遍历中修改集合。
fail-fast 是什么？怎么解决？	遍历中检测集合并发修改抛异常；解决：迭代器 remove ()、CopyOnWriteArrayList。

二、 LinkedList 深度解析

1. 双向链表结构详解

LinkedList 是基于双向链表实现的有序集合，核心结构：

1.1 节点结构深入

• 每个节点是一个Node对象，包含 3 个属性：

// Node 类的完整理解
private static class Node<E> {
    E item;          // 实际存储的数据
    Node<E> next;    // 后继指针：指向下一个节点
    Node<E> prev;    // 前驱指针：指向前一个节点
    
    // 构造函数：创建时建立双向链接
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;   // 把自己的数据域赋成传进来的元素
    this.next = next;      // 把自己的后继指向参数 next
    this.prev = prev;      // 把自己的前驱指向参数 prev

    // 下面两行是反向链接：让相邻的节点也认识自己
    if (prev != null) prev.next = this;  // 前驱的后继 = 我自己
    if (next != null) next.prev = this;  // 后继的前驱 = 我自己
    }
}

• LinkedList 还维护了两个哨兵节点：first（头节点）、last（尾节点），无需遍历就能快速定位头尾；
• 无固定容量，添加元素只需新建节点、修改指针，无需扩容。

1.2 链表结构可视化

public class LinkedListStructure {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        
        // 添加元素的过程
        list.add("A");  // 创建节点1：[null ← A → null]
        list.add("B");  // 创建节点2：[A ← B → null]，并更新A.next=B
        list.add("C");  // 创建节点3：[B ← C → null]，并更新B.next=C
        
        // 最终结构：
        // first → [null ← A → B] ↔ [A ← B → C] ↔ [B ← C → null] ← last
        //         (节点1)           (节点2)           (节点3)
        
        // 双向遍历能力：
        // 正向：A → B → C
        // 反向：C → B → A
    }
}

2. 核心操作原理

2.1 头部插入分析

// linkFirst 方法深度解析
private void linkFirst(E e) {
    final Node<E> f = first;  // 1. 保存原头节点
    
    // 2. 创建新节点：prev=null, element=e, next=f（指向原头节点）
    final Node<E> newNode = new Node<>(null, e, f);
    
    first = newNode;  // 3. 更新first指针
    
    if (f == null)    // 4. 原链表为空
        last = newNode;  // 新节点也是尾节点
    else
        f.prev = newNode;  // 5. 原头节点的prev指向新节点
        
    size++;
    modCount++;
}

// 时间复杂度：O(1) 常数时间
// 无论链表多长，操作步骤固定

2.2 中间插入分析

// 在指定位置插入
public void add(int index, E element) {
    checkPositionIndex(index);//检查传入的参数index是否在数组索引范围内
    
    if (index == size)  // 尾部插入
        linkLast(element);
    else
        linkBefore(element, node(index));  // 关键：先找到节点
}

// node(index)：查找节点（耗时操作）
Node<E> node(int index) {
    // 优化：根据位置决定从前还是从后遍历
    if (index < (size >> 1)) {  // 前半部分
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;  // 顺序遍历
        return x;
    } else {  // 后半部分
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;  // 逆序遍历
        return x;
    }
}

// 时间复杂度：
// 查找节点：O(n/2) = O(n) 线性时间
// 插入操作：O(1) 常数时间
// 总复杂度：O(n)

还有尾部插入，指定的节点前插入…这些我都不一一讲述，有兴趣的小伙伴可以去读源码，读源码是一个很方便快捷的方式，对我们提升自身能力有很大帮助！

其实原理很简单，只要你能理解链表的结构，同时关照到每个方面，源码你也能手搓出来！嘻嘻。

3. 适用场景深度分析

场景1：频繁的头部操作

public class StackImplementation {
    // LinkedList 实现栈（后进先出）
    public class Stack<E> {
        private LinkedList<E> list = new LinkedList<>();
        
        public void push(E item) {
            list.addFirst(item);  // O(1)
        }
        
        public E pop() {
            return list.removeFirst();  // O(1)
        }
        
        public E peek() {
            return list.getFirst();  // O(1)
        }
    }
    
    // 对比 ArrayList 实现栈
    public class ArrayListStack<E> {
        private ArrayList<E> list = new ArrayList<>();
        
        public void push(E item) {
            list.add(0, item);  // O(n)！需要移动所有元素
        }
        
        public E pop() {
            return list.remove(0);  // O(n)！
        }
    }
}

场景2：实现队列和双端队列

public class QueueDequeDemo {
    public static void main(String[] args) {
        // LinkedList 实现了 Deque 接口
        Deque<String> deque = new LinkedList<>();
        
        // 作为队列使用（FIFO）
        deque.offer("A");  // 入队
        deque.offer("B");
        System.out.println(deque.poll());  // 出队：A
        
        // 作为双端队列使用
        deque.offerFirst("C");  // 头部入队
        deque.offerLast("D");   // 尾部入队
        System.out.println(deque.pollFirst());  // C
        System.out.println(deque.pollLast());   // D
        
        // 作为栈使用
        deque.push("E");    // 压栈
        deque.push("F");
        System.out.println(deque.pop());  // 弹栈：F
    }
}

场景3：LRU缓存实现

public class LRUCache<K, V> {
    private final int capacity;
    private final Map<K, Node> cache;
    private final LinkedList<Node> list;
    
    class Node {
        K key;
        V value;
    }
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.list = new LinkedList<>();
    }
    
    public V get(K key) {
        if (!cache.containsKey(key)) return null;
        
        Node node = cache.get(key);
        // 移动到头部（最近使用）
        list.remove(node);      // O(1) 知道节点位置
        list.addFirst(node);    // O(1)
        
        return node.value;
    }
    
    public void put(K key, V value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;
            list.remove(node);
            list.addFirst(node);
        } else {
            if (cache.size() >= capacity) {
                Node last = list.removeLast();  // 移除最久未使用
                cache.remove(last.key);
            }
            Node newNode = new Node();
            newNode.key = key;
            newNode.value = value;
            list.addFirst(newNode);
            cache.put(key, newNode);
        }
    }
}

场景4：大数据集的中间位置频繁修改

public class TextEditor {
    // 模拟文本编辑器：光标位置频繁插入删除
    private LinkedList<Character> text = new LinkedList<>();
    private ListIterator<Character> cursor;
    
    public TextEditor() {
        cursor = text.listIterator();
    }
    
    // 插入字符
    public void insertChar(char c) {
        cursor.add(c);  // O(1) 在迭代器位置插入
    }
    
    // 删除字符
    public void deleteChar() {
        if (cursor.hasPrevious()) {
            cursor.previous();
            cursor.remove();  // O(1) 删除当前字符
        }
    }
    
    // 移动光标
    public void moveCursorForward() {
        if (cursor.hasNext()) cursor.next();  // O(1)
    }
    
    public void moveCursorBackward() {
        if (cursor.hasPrevious()) cursor.previous();  // O(1)
    }
}

4. LinkedList 面试高频问答

问题	标准答案
LinkedList 底层结构？	双向链表，每个节点包含 prev/next/item，维护头尾节点，无需扩容。
LinkedList 和 ArrayList 的区别？	1. 结构：数组 vs 双向链表；2. 访问：ArrayList 快（O (1)），LinkedList 慢（O (n)）；3. 增删：LinkedList 头尾增删快（O (1)），中间增删仍慢。
LinkedList 可以做队列 / 栈吗？	可以：队列（addFirst/removeLast）、栈（push/pop，底层是 addFirst/removeFirst）。
LinkedList 为什么不适合随机访问？	无索引，需从头 / 尾遍历到目标位置，时间复杂度 O (n)。

5. 性能对比实战

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * ArrayList vs LinkedList 性能对比
 * 测试维度：头部插入、尾部插入、随机访问、内存占用
 * 结论记忆：
 *   1. 头插：LinkedList 完胜（O(1) vs O(n)）
 *   2. 尾插：两者 O(1) 接近，ArrayList 略快（连续内存 + 扩容公式 1.5 倍）
 *   3. 随机读：ArrayList 碾压（O(1) vs O(n)）
 *   4. 内存：LinkedList 额外 50% ~ 100%（每个 Node 多两个引用域）
 */
public class PerformanceComparison {

    // 测试规模：10 万元素（可自行调大/调小）
    private static final int SIZE = 100_000;

    public static void main(String[] args) {
        System.out.println("=== 头部插入性能测试 ===");
        testAddFirst(SIZE);

        System.out.println("\n=== 尾部插入性能测试 ===");
        testAddLast(SIZE);

        System.out.println("\n=== 随机访问性能测试 ===");
        testRandomAccess(SIZE);

        System.out.println("\n=== 内存占用测试 ===");
        testMemoryUsage(SIZE);
    }

    /* ---------- 1. 头部插入 ---------- */
    private static void testAddFirst(int size) {
        // LinkedList：linkFirst 操作，纯指针调整，O(1)
        LinkedList<Integer> linkedList = new LinkedList<>();
        long start = System.nanoTime();
        for (int i = 0; i < size; i++) {
            linkedList.addFirst(i);
        }
        long linkedTime = System.nanoTime() - start;

        // ArrayList：每次 add(0, i) 都要整体右移，O(n)
        ArrayList<Integer> arrayList = new ArrayList<>();
        start = System.nanoTime();
        for (int i = 0; i < size; i++) {
            arrayList.add(0, i);   // 灾难性性能
        }
        long arrayTime = System.nanoTime() - start;

        printReport("LinkedList", linkedTime, "ArrayList", arrayTime);
    }

    /* ---------- 2. 尾部插入 ---------- */
    private static void testAddLast(int size) {
        // LinkedList：linkLast 操作，O(1)
        LinkedList<Integer> linkedList = new LinkedList<>();
        long start = System.nanoTime();
        for (int i = 0; i < size; i++) {
            linkedList.addLast(i);
        }
        long linkedTime = System.nanoTime() - start;

        // ArrayList：默认 append，平均 O(1)（偶尔扩容）
        ArrayList<Integer> arrayList = new ArrayList<>();
        start = System.nanoTime();
        for (int i = 0; i < size; i++) {
            arrayList.add(i);   // 等价 addLast
        }
        long arrayTime = System.nanoTime() - start;

        printReport("LinkedList", linkedTime, "ArrayList", arrayTime);
    }

    /* ---------- 3. 随机访问 ---------- */
    private static void testRandomAccess(int size) {
        // 预填充数据，避免插入耗时干扰
        LinkedList<Integer> linkedList = new LinkedList<>();
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            linkedList.add(i);
            arrayList.add(i);
        }

        // 生成同一批随机下标，保证公平
        int[] indices = new int[size];
        java.util.Random r = new java.util.Random(0);
        for (int i = 0; i < size; i++) indices[i] = r.nextInt(size);

        // LinkedList：每次 get 都要从最近端遍历，平均 O(n)
        long start = System.nanoTime();
        long sum = 0; // 防止 JIT 把循环优化掉
        for (int idx : indices) sum += linkedList.get(idx);
        long linkedTime = System.nanoTime() - start;

        // ArrayList：物理下标，直接内存偏移，O(1)
        start = System.nanoTime();
        sum = 0;
        for (int idx : indices) sum += arrayList.get(idx);
        long arrayTime = System.nanoTime() - start;

        printReport("LinkedList", linkedTime, "ArrayList", arrayTime);
    }

    /* ---------- 4. 内存占用估算 ---------- */
    private static void testMemoryUsage(int size) {
        Runtime rt = Runtime.getRuntime();
        rt.gc(); // 建议 GC，减少干扰
        long before = rt.totalMemory() - rt.freeMemory();

        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < size; i++) linkedList.add(i);

        rt.gc();
        long after = rt.totalMemory() - rt.freeMemory();
        double linkedMB = (after - before) / 1024.0 / 1024.0;

        // ArrayList 测试
        rt.gc();
        before = rt.totalMemory() - rt.freeMemory();

        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < size; i++) arrayList.add(i);

        rt.gc();
        after = rt.totalMemory() - rt.freeMemory();
        double arrayMB = (after - before) / 1024.0 / 1024.0;

        System.out.printf("LinkedList 占用: %.2f MB\n", linkedMB);
        System.out.printf("ArrayList  占用: %.2f MB\n", arrayMB);
        System.out.printf("LinkedList 多用了 %.1f%% 内存\n", (linkedMB - arrayMB) / arrayMB * 100);
    }

    /* ---------- 工具：统一打印格式 ---------- */
    private static void printReport(String fastName, long fastTime, String slowName, long slowTime) {
        System.out.printf("%s: %.2f ms\n", fastName, fastTime / 1_000_000.0);
        System.out.printf("%s: %.2f ms\n", slowName, slowTime / 1_000_000.0);
        System.out.printf("%s 是 %s 的 %.2f 倍快\n",
                fastName, slowName, (double) slowTime / fastTime);
    }
}

三、选择决策树

需要频繁随机访问吗？
├── 是 → 选择 ArrayList
└── 否 → 需要频繁在头部插入/删除吗？
    ├── 是 → 选择 LinkedList
    └── 否 → 数据量小吗？
        ├── 是 → 两者都可，ArrayList 通常更好
        └── 否 → 需要实现队列/双端队列吗？
            ├── 是 → 选择 LinkedList（实现 Deque）
            └── 否 → 内存敏感吗？
                ├── 是 → 选择 ArrayList
                └── 否 → 根据具体操作模式选择

四、总结要点

ArrayList 关键点

1. 数组实现：内存连续，缓存友好
2. 1.5倍扩容：复制数组开销大，应预估容量
3. Fail-Fast：快速失败机制，防止并发修改异常
4. 读快写慢：随机访问O(1)，插入删除O(n)
5. 内存效率：只存储数据，无额外指针开销

LinkedList 关键点

1. 双向链表：内存分散，每个节点有前后指针
2. 操作灵活：头部操作O(1)，支持双向遍历
3. 适用场景：队列/栈实现、LRU缓存、频繁头部操作
4. 内存开销：每个节点多16-24字节额外开销
5. 迭代器优势：支持在迭代中高效修改

实际应用建议

• 80% 场景用 ArrayList：大多数应用是读多写少
• 特殊场景用 LinkedList：明确需要队列/栈特性
• 性能关键时实测：用真实数据测试，理论可能不符合实际
• 考虑并发场景：两者都不是线程安全的，需要同步