Java 中 ArrayDeque 与 LinkedList 作为栈使用的性能对比

在 Java 中实现栈结构时，优先推荐使用 ArrayDeque，而不是 LinkedList 或传统的 Stack 类。

先说结论：ArrayDeque 是官方推荐的栈实现方案，通常在内存占用和访问速度上优于 LinkedList。

适合：单线程环境下的栈操作场景，如表达式求值、深度优先搜索。
重点看：底层数据结构差异，数组连续内存带来的缓存友好性。
别忽略：ArrayDeque 不允许存放 null 元素，且不是线程安全的。

代码迁移示例

如果你正在使用 LinkedList 模拟栈，可以参考以下替换方式。ArrayDeque 同样实现了 Deque 接口，支持 push/pop/peek 方法。

Java 中 ArrayDeque 与 LinkedList 作为栈使用的性能对比

// 原代码 (LinkedList 作为栈)
LinkedList<String> stack = new LinkedList<>();
stack.push("A");
String top = stack.pop();

// 建议替换为 (ArrayDeque)
ArrayDeque<String> stack = new ArrayDeque<>();
stack.push("A");
String top = stack.pop();

性能差异与基准测试

ArrayDeque 性能优于 LinkedList 的主要原因有两点：一是 LinkedList 每个节点都需要额外的对象头开销和前后指针引用，内存占用更高；二是 ArrayDeque 基于数组，内存连续，对 CPU 缓存更友好，遍历和访问效率更高。

以下是使用 JMH 进行基准测试的代码示例，可用于验证具体环境下的性能差异：

@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.SECONDS)
@State(Scope.Thread)
public class StackBenchmark {
    private Deque<String> arrayDeque;
    private Deque<String> linkedList;

    @Setup
    public void setup() {
        arrayDeque = new ArrayDeque<>();
        linkedList = new LinkedList<>();
    }

    @Benchmark
    public void testArrayDeque() {
        arrayDeque.push("data");
        arrayDeque.pop();
    }

    @Benchmark
    public void testLinkedList() {
        linkedList.push("data");
        linkedList.pop();
    }
}

在高频入栈出栈场景下，ArrayDeque 通常表现出更低的延迟和更高的吞吐量。

多线程安全实践

ArrayDeque 不是线程安全的。如果涉及多线程共享栈，需要外部同步。

方案一：使用 Collections 包装

Deque<String> stack = Collections.synchronizedDeque(new ArrayDeque<>());

方案二：显式锁控制（推荐用于复合操作）

private final Deque<String> stack = new ArrayDeque<>();
private final Lock lock = new ReentrantLock();

public void safePush(String item) {
    lock.lock();
    try {
        stack.push(item);
    } finally {
        lock.unlock();
    }
}

验证与常见坑

null 元素限制：LinkedList 允许 null，ArrayDeque 不允许，插入 null 会抛出 NullPointerException。
线程安全误解：多线程 push/pop 需要外部锁保护，不可直接共享实例。
容量扩展：ArrayDeque 扩容时会复制数组，初始化时指定合适容量可减少扩容抖动。
单元测试：替换后运行现有单元测试，确保功能行为未改变。

参考来源

1. Oracle Java Documentation - Class ArrayDeque
URL: https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/ArrayDeque.html