Why Stack is implemented using array not using linkedlist ?
If you use add to front and remove from front in the linkedlist than it can be efficient way of of implementing stack, instead of working about increasing the size of the array when it’s 75% or some threshold full.
Advertisement
Answer
If you use add to front and remove from front in the linkedlist than it can be efficient way of of implementing stack, instead of working about increasing the size of the array when its 75% or some threshold full.
The trade-offs are more complicated than that.
-
A stack that is implement using a linked list would need 3 or 4 times as much space per stack entry as an array-based implementation:
- In an array-based implementation, a stack element just requires one reference-sized array cell.
- In a linked-list based implementation, each stack element consists of a “node” object containing 2 references (or 3 if doubly-linked). Then you have to add the overhead of the node’s object header and possible heap node padding.
You may waste some space due to resizing, but on average the math says that the wastage is much less than the “node” overheads. If you are not prepared to take my word for this, do the math yourself for various combinations of platform assumptions; e.g. reference size, object header size, heap node size granularity, array resize strategy, etc.
-
An array-based stack has predictable locality, whereas the objects that represent a linked list’s entries could be scattered throughout the heap.
-
If you expand an array-based data structure by a fixed percentage when it gets full, AND the stack has a long life, THEN the cost of the expansion is amortized, and becomes irrelevant.
On the flip-side a linked-list based implementation does have the advantage that space gets released (i.e. becomes eligible for GCing) when the stack empties.
In short, different implementation approaches will be better depending on how the stack is going to be used. But the Stack implementors had to pick just one.
The other point is that Stack is a really old class that existed in Java 1.0 … before the collections framework was introduced. The API and aspects of the implementation are constrained by the need for backwards compatibility.
If you want better APIs and better (or different) performance characteristics, look at the classes that implement the Dequeue interface.