堆栈实现 java - LinkedList vs Vector

Question

我想知道为什么 Stack 是使用 Vector 而不是 LinkedList 实现的。据我所知，LinkedList 为元素的删除和插入提供了更高效的结构。那么，为什么堆栈是使用向量而不是 LinkedList 来实现的。Java 使用 LinkedList 实现了 Queue 接口，既然在堆栈和队列中，插入和删除是主要功能，为什么 Stack 不使用链表。

Answer 1

Stack并且Vector都是旧类。

如果您阅读 的 Javadoc Stack，您会看到它建议使用Deque：

Deque 接口及其实现提供了一组更完整和一致的 LIFO 堆栈操作，应优先使用此类。

并且LinkedList确实实现了Deque接口。

Answer 2

据我所知，LinkedList为元素的删除和插入提供了更有效的结构。

这实际上不是真的……在堆栈操作的上下文中。（或一般情况下）。

AVector是数组列表的一种形式。它的工作原理是分配一个数组来保存多个元素，并使用数组索引来访问和更新列表。在 中的随机位置插入和删除Vector是昂贵的，因为它需要复制多个元素引用。

但是，这不是 a 所Stack要求的。它实际上需要插入和删除专门在的结尾Vector，那就是便宜。在大多数情况下，插入和删除仅涉及将元素分配到数组单元并调整Vector对象的length字段。如果阵列中没有足够的空间，它只会变得昂贵。然后必须通过创建一个新数组并复制元素来“增长”数组。但是当数组列表以指数方式增长数组时（例如通过将其大小加倍），数学表明摊销 成本O(1)在数组列表的生命周期内。

相比之下，每次向 a 中插入元素时LinkedList，都需要分配一个新的内部“节点”对象来保存该元素。平均而言，这比Vector插入更昂贵，尤其是当您考虑到“节点”对象的生命周期内产生的 GC 成本时。

假设我们使用 64 位引用，结果还证明 aLinkedList每个元素使用的内存是 a 的 4 倍Vector。

简而言之，对于堆栈数据结构， aVector比 a 更有效并且使用更少的空间LinkedList。做出了正确的设计选择¹。

^{1 - 正如你所期望的。我们可以假设在过去大约 25 年里设计和维护 Java 的工程师知道他们在做什么。或者，自代码编写以来看过该代码的数以万计的其他人也会注意到（假设！）如此严重的错误并记录了错误报告。}