Stack implementation java – LinkedList vs Vector

huangapple go评论69阅读模式
英文:

Stack implementation java - LinkedList vs Vector

问题

我想知道为什么使用向量(Vector)而不是链表(LinkedList)来实现栈(Stack)。据我所知,链表提供了更有效的结构用于元素的删除和插入。那么,为什么栈要使用向量而不是链表呢?Java使用链表来实现队列(Queue)接口,并且由于在栈和队列中,插入和删除是主要功能,为什么对于栈不使用链表呢?

英文:

I wanted to know why Stack is implemented using Vector and not with LinkedList. As far as I know, LinkedList provides more efficient structure for deletion and insertion of elements. So, why stack is implemented using vector and not LinkedList. Java implements Queue interface with LinkedList and since in both stack and queue, insertion and deletion is the primary function, why not linkedlist for Stack.

答案1

得分: 5

StackVector都是旧的类。

如果您阅读Stack的Javadoc,您会看到它建议使用Deque代替:

>更完整一致的LIFO堆栈操作集由Deque接口及其实现提供,应优先使用该接口而不是此类。

LinkedList确实实现了Deque接口。

英文:

Stack and Vector are both old classes.

If you read the Javadoc of Stack, you'll see that it suggests using Deque instead:

>A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

And LinkedList does implement the Deque interface.

答案2

得分: 5

据我所知,LinkedList 提供了更高效的结构,用于删除和插入元素。

但事实并非如此,在栈操作的上下文中(或一般情况下)。

Vector 是一种数组列表形式。它通过分配一个数组来存储多个元素,并使用数组索引来访问和更新列表。在Vector中的任意位置进行插入和删除操作是昂贵的,因为涉及复制多个元素引用。

然而,这不是Stack所需要的。它实际上要求仅在Vector的末尾进行插入和删除操作,这是廉价的。在大多数情况下,插入和删除只涉及将元素赋值到数组单元中并调整Vector对象的length字段。只有在数组中没有足够空间时,才会变得昂贵。然后,必须通过创建新数组并复制元素来“增长”数组。但是,当数组列表呈指数增长(例如将其大小加倍)时,数学表明在数组列表的生命周期内,摊销成本为O(1)

相比之下,每次将元素插入LinkedList时,都涉及分配一个新的内部“节点”对象来容纳元素。平均而言,这比Vector的插入成本更高,特别是考虑到内存中的“节点”对象在其生命周期内产生的垃圾收集成本。

而且事实证明,相对于使用64位引用,LinkedList每个元素使用的内存多达Vector的4倍。

简而言之,对于栈数据结构,相较于LinkedListVector更高效且使用的空间更少。正确的设计选择已经被做出<sup>1</sup>。


<sup>1 - 正如您所期望的那样。我们可以假设在过去的大约25年里设计和维护Java的工程师知道他们在做什么。或者那些自代码编写以来已经查看过该代码的数以万计的其他人也会注意到如此重大的(假设的!)错误并提交错误报告。</sup>

英文:

> As far as I know, LinkedList provides more efficient structure for deletion and insertion of elements.

That is not actually true ... in the context of stack operations. (Or in general).

A Vector is a form of array list. It works by allocating an array to hold a number of elements, and using array indexing to access and update the list. Insertion and deletion at a random position in the Vector is expensive because it entails copying multiple element references.

However, that not what a Stack requires. It actually requires insertion and deletion exclusively at the end of the Vector, and that is cheap. In most cases, insertion and deletion simply involves assigning an element into an array cell and adjusting the Vector object's length field. It only gets expensive if there is not enough space in the array. Then the array has to be "grown" by creating a new one and copying the elements. But when an array list grows the array exponentially (e.g. by doubling its size), the math says that the amortized cost is O(1) over the lifetime of the array list.

By contrast, every time you insert an element into a LinkedList, it involves allocating a new internal "node" object to hold the element. That is more expensive on average than a Vector insertion, especially when you take into account the GC costs incurred over the lifetime of the "node" object.

It also turns out a LinkedList uses up to 4 times as much memory per element as a Vector does, assuming we are using 64 bit references.

In short, a Vector is more efficient and uses less space than a LinkedList for a stack data structure. The correct design choice was made<sup>1</sup>.


<sup>1 - As you would expect. We can assume that the engineers who designed and maintained Java over the last ~25 years knew what they were doing. Or that the tens of thousands of other people who have looked at that code since it was written would also have noticed a (hypothetical!) mistake of that magnitude and logged a bug report.</sup>

huangapple
  • 本文由 发表于 2020年7月26日 16:01:04
  • 转载请务必保留本文链接:https://go.coder-hub.com/63097585.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定