英文:
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
Stack
和Vector
都是旧的类。
如果您阅读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倍。
简而言之,对于栈数据结构,相较于LinkedList
,Vector
更高效且使用的空间更少。正确的设计选择已经被做出<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>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论