java - 在 Java 中使用基于 Vector 的 Stack 实现而不是链表的动机是什么？

Question

Vector在 Java 中使用基于 a 的实现Stack而不是链表实现的动机是什么？我意识到 aVector是同步的并且具有继承优势（和开销），但我觉得这些数据结构不仅通常在文本中作为基于链表的结构教授，而且 LL 避免了随着底层数组的填充而代价高昂的调整大小。

我确实明白Vectors，使用摊销分析，即使调整大小也是 O(1) 。因此，也许考虑到这一点并没有太大的区别，但是我仍然很想了解其中的原理。

Answer 1

链表有以下缺点：

• 每个元素的存储开销
• 必须遵循从元素到元素的指针/引用的计算复杂性
• 缓存位置错误

当然，这些只是链表的一般缺点；我不知道他们是否影响了基于什么的Queue决定Stack。

Answer 2

向量将其数据存储在连续内存中。这有利于缓存。

链表在内存中会变得非常碎片化。