Stack与LinkedList增删操作时间复杂度对比及LeetCode耗时差异疑问

虽然Stack的push()、pop()、peek()和LinkedList的add()、removeLast()时间复杂度都是O(1)，但实际性能差异的核心原因在于两者的线程安全设计：

• Stack继承自Vector，所有方法带synchronized锁：Vector为保证线程安全，给每个公共方法都添加了synchronized关键字。哪怕是单线程场景，每次调用这些方法都要执行锁的获取与释放操作，这会带来额外开销——包括锁检查、无竞争场景下的锁操作成本，在大量重复调用的测试用例中，累计的开销会被放大，直接导致耗时剧增。

• LinkedList的核心操作无锁开销：LinkedList本身并非线程安全实现，add()、removeLast()这类方法没有同步锁逻辑，调用时直接操作节点指针，无需处理同步相关的额外步骤，单线程下的执行效率远高于带锁的Stack。

此外，Stack底层基于数组实现，扩容时会有数组拷贝开销，但这种情况仅在容量不足时触发，不是造成你看到的2888ms vs 188ms量级差异的主要原因，核心还是synchronized锁的额外消耗。

内容的提问来源于stack exchange，提问作者Vipin