Stack implementation java - LinkedList vs Vector [closed]

Question

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.

Answer 1

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.

Answer 2

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¹.

---

^{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.}