在 Java 集合框架中，ArrayList 和 LinkedList 是两个常用的 List 实现类。虽然它们都实现了 List 接口，但在底层数据结构、性能和使用场景上有着显著的区别。本文将详细探讨它们的设计、实现和应用场景，并结合源码进行解析。

1. 是否保证线程安全

• ArrayList 和 LinkedList 都是不同步的，即不保证线程安全。如果需要线程安全的列表，可以使用 Collections.synchronizedList 方法来包装它们，或者使用 CopyOnWriteArrayList。

2. 底层数据结构

• ArrayList 底层使用的是 Object 数组。
• LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环）。

ArrayList 源码解析

java

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    transient Object[] elementData; // non-private to simplify nested class access
    private int size;
    
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

在 ArrayList 中，元素存储在一个 Object 数组中。当添加元素超过当前数组容量时，会自动扩容，新的容量是旧容量的 1.5 倍。

LinkedList 源码解析

java

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;
    
    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;
            this.prev = prev;
        }
    }
    
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
}

在 LinkedList 中，元素存储在一个个 Node 对象中，每个 Node 对象包含一个元素及其前后指针。

3. 插入和删除是否受元素位置的影响

• ArrayList 插入和删除元素的时间复杂度受元素位置的影响。比如在末尾插入元素时间复杂度为 O(1)，在中间插入或删除元素的时间复杂度为 O(n)。
• LinkedList 在头尾插入或删除元素不受位置影响，时间复杂度为 O(1)；在中间插入或删除元素的时间复杂度为 O(n)。

4. 是否支持快速随机访问

• ArrayList 支持快速随机访问，因为它实现了 RandomAccess 接口，可以通过索引直接访问元素，时间复杂度为 O(1)。
• LinkedList 不支持快速随机访问，需要从头或尾遍历，时间复杂度为 O(n)。

5. 内存空间占用

• ArrayList 的空间浪费主要体现在预留的容量空间。
• LinkedList 的空间花费主要体现在每个节点需要额外的空间存储前后指针。

实际应用场景

• ArrayList 适用于需要频繁随机访问元素的场景，如读取操作较多的情况。
• LinkedList 适用于需要频繁插入、删除元素的场景，特别是在头尾插入或删除时性能较优。

性能对比

以下是一个插入操作性能对比的例子：

java

public class ListPerformanceTest {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();
        
        // 初始化数据
        for (int i = 0; i < 100000; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }
        
        // 测试 ArrayList 插入性能
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            arrayList.add(50000, i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("ArrayList 插入时间: " + (endTime - startTime) + " ms");
        
        // 测试 LinkedList 插入性能
        startTime = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            linkedList.add(50000, i);
        }
        endTime = System.currentTimeMillis();
        System.out.println("LinkedList 插入时间: " + (endTime - startTime) + " ms");
    }
}

运行上述代码可以看到，在中间位置插入元素时，LinkedList 的性能远逊于 ArrayList。

结论

在大多数场景下，ArrayList 都优于 LinkedList。除非有明确的要求需要使用链表结构，否则推荐使用 ArrayList。这不仅是因为 ArrayList 提供了更好的性能，还因为其内存占用更为高效。

?