Java 中 ArrayList 与 LinkedList 的详细比较

ArrayList 详细介绍

内部实现

ArrayList 是基于动态数组的数据结构。它允许随机访问元素，并且在内存中是连续存储的。当 ArrayList 的容量不足时，它会创建一个更大的数组，并将现有元素复制到新数组中，这可能会导致性能开销。内部使用的是 Object[] 数组来存储元素。

性能特点

• 随机访问：O(1)，因为可以直接通过索引访问。
• 插入和删除（末尾）：平均情况下 O(1)；最坏情况下 O(n)，如果需要扩容的话。
• 插入和删除（中间或开头）：O(n)，因为需要移动元素以保持数组的连续性。

使用场景

• 当你需要频繁地进行随机访问或者在列表末尾添加/移除元素时，ArrayList 是一个很好的选择。
• 如果你预计列表的大小不会频繁变化，那么 ArrayList 也可以是一个合适的选择，因为它提供了较快的读取速度。

import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        // 创建一个ArrayList实例，默认初始容量为10
        ArrayList<String> list = new ArrayList<>();
        
        // 添加元素到ArrayList
        // add() 方法在列表末尾添加元素，时间复杂度为 O(1)
        list.add("Apple");
        list.add("Banana");
        list.add("Orange");
        
        // 打印列表，toString() 方法返回列表内容的字符串表示
        System.out.println("Initial List: " + list);
        
        // 随机访问元素，get() 方法根据索引获取元素，时间复杂度为 O(1)
        String element = list.get(1); // 获取索引为1的元素
        System.out.println("Element at index 1: " + element);
        
        // 在末尾添加元素，add() 方法在列表末尾添加元素，时间复杂度为 O(1)
        list.add("Grapes");
        System.out.println("After adding Grapes: " + list);
        
        // 删除元素，remove() 方法根据索引删除元素，时间复杂度为 O(n)
        list.remove(2); // 删除索引为2的元素
        System.out.println("After removing index 2: " + list);
        
        // 设置元素值，set() 方法替换指定位置的元素，时间复杂度为 O(1)
        list.set(1, "Mango"); // 将索引为1的元素设置为 "Mango"
        System.out.println("After setting index 1 to Mango: " + list);
        
        // 检查是否包含某个元素，contains() 方法遍历列表查找元素，时间复杂度为 O(n)
        boolean containsApple = list.contains("Apple");
        System.out.println("Contains Apple: " + containsApple);
        
        // 获取列表大小，size() 方法返回列表中元素的数量，时间复杂度为 O(1)
        int size = list.size();
        System.out.println("List size: " + size);
    }
}

LinkedList 详细介绍

内部实现

LinkedList 是基于双向链表的数据结构。每个节点不仅包含元素本身，还包含指向前后节点的引用。这种结构使得在链表两端进行插入和删除操作非常高效。内部使用了 Node<E> 类来表示链表中的节点。

性能特点

• 随机访问：O(n)，因为必须遍历链表到达指定位置。
• 插入和删除（两端）：O(1)，不需要移动其他元素。
• 插入和删除（中间）：O(n)，首先需要找到目标位置。

使用场景

• 当你需要频繁地在列表的任意位置进行插入或删除操作时，LinkedList 提供了更好的性能。
• 如果你需要一个队列或双端队列的数据结构，LinkedList 实现了 Deque 接口，可以高效地支持这些数据结构所需的头部和尾部操作。

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // 创建一个LinkedList实例
        LinkedList<String> list = new LinkedList<>();
        
        // 添加元素到LinkedList
        // add() 方法在列表末尾添加元素，时间复杂度为 O(1)
        list.add("Apple");
        list.add("Banana");
        list.add("Orange");
        
        // 打印列表，toString() 方法返回列表内容的字符串表示
        System.out.println("Initial List: " + list);
        
        // 使用迭代器遍历元素，iterator() 方法返回一个用于遍历列表的迭代器
        for (String fruit : list) {
            System.out.println(fruit);
        }
        
        // 在头部插入元素，addFirst() 方法在列表头部添加元素，时间复杂度为 O(1)
        list.addFirst("Strawberry");
        System.out.println("After adding to head: " + list);
        
        // 在尾部添加元素，addLast() 方法在列表尾部添加元素，时间复杂度为 O(1)
        list.addLast("Grapes");
        System.out.println("After adding to tail: " + list);
        
        // 删除第一个和最后一个元素，removeFirst() 和 removeLast() 方法分别删除头尾元素，时间复杂度为 O(1)
        list.removeFirst();
        list.removeLast();
        System.out.println("After removing first and last: " + list);
        
        // 获取第一个和最后一个元素，getFirst() 和 getLast() 方法分别获取头尾元素，时间复杂度为 O(1)
        String first = list.getFirst();
        String last = list.getLast();
        System.out.println("First Element: " + first);
        System.out.println("Last Element: " + last);
        
        // 插入元素到指定位置，add(int index, E element) 方法在指定位置插入元素，时间复杂度为 O(n)
        list.add(1, "Peach");
        System.out.println("After inserting Peach at index 1: " + list);
        
        // 删除指定位置的元素，remove(int index) 方法删除指定位置的元素，时间复杂度为 O(n)
        list.remove(1);
        System.out.println("After removing element at index 1: " + list);
    }
}

线程安全性与同步

默认情况下，ArrayList 和 LinkedList 都不是线程安全的。如果在多线程环境中使用它们，你需要确保适当的同步。可以使用 Collections.synchronizedList() 方法来包装列表，以获得线程安全的版本。但是需要注意，即使列表被同步了，迭代器仍然不是线程安全的。

import java.util.Collections;
import java.util.List;
import java.util.ArrayList;

public class SynchronizedListExample {
    public static void main(String[] args) {
        // 创建一个ArrayList实例，并用 Collections.synchronizedList 包装以获得线程安全的版本
        List<String> syncList = Collections.synchronizedList(new ArrayList<>());
        // 或者对于 LinkedList
        // List<String> syncList = Collections.synchronizedList(new LinkedList<>());

        // 对于同步列表的操作...
        synchronized (syncList) {
            syncList.add("Thread-safe Element");
        }
        
        // 注意：即使列表是线程安全的，迭代器也不是线程安全的。
        // 必须在外层加锁来保证迭代期间的安全性。
        synchronized (syncList) {
            for (String item : syncList) {
                // 迭代操作...
            }
        }
    }
}

迭代器失效

当在迭代过程中修改了 ArrayList 或 LinkedList，除了通过迭代器自身的 remove 或 add 方法外，都会抛出 ConcurrentModificationException。这是为了防止并发修改带来的不一致性问题。

import java.util.Iterator;
import java.util.ArrayList;

public class IteratorExample {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("Apple");
        list.add("Banana");

        // 获取迭代器
        Iterator<String> it = list.iterator();
        while (it.hasNext()) {
            String fruit = it.next();
            if ("Banana".equals(fruit)) {
                // 正确的方式：通过迭代器移除元素，避免 ConcurrentModificationException
                it.remove();
            }
            // 错误的方式：直接通过list.remove()会导致ConcurrentModificationException
            // list.remove(fruit);
        }

        // 打印最终列表
        System.out.println("Final List after iteration removal: " + list);
    }
}