Stack class in java.util package

Question

Why stack class in java.util package was implemented using array? Why not using Linked List data structure?

package java.util;

public class Stack<E> extends Vector<E>
{
    private static final long serialVersionUID = 1224463164541339165L;

    protected Object[] elementData; // in Vector Class

    public E push(E paramE)
    {
       addElement(paramE);
       return paramE;
    }

    public synchronized void addElement(E paramE)
    {
      modCount += 1;
      ensureCapacityHelper(elementCount + 1);
      elementData[(elementCount++)] = paramE;
    }

score 5 · Answer 1 · answered Dec 10 '18 at 16:40

5

Stack was added in JDK1, LinkedList was added in JDK2, LinkedList wasn't exist when implemented Stack,
Stack is very old classes, now best practice use ArrayDeque instead of,
LinkedList is almost all cases is worse then ArrayList (by performance), see Oracle guide and this answer in SO

answered Dec 10 '18 at 16:40

Slava Vedenin

58,326
13
40
59

1

For a data structure that is being used *purely* as a stack (i.e. only push, pop and peek, not enumerating the entire container as if it were a list), linked lists may actually give better performance that array-based solutions. The reason is that all the required operations (push, pop and peek) are O(1), whereas with an array solution, pop and peek would be O(1), but push is O(n), as you would occasionally need to reallocate the entire array. – Nick Mertin Dec 10 '18 at 16:57
In one of conference, I asked Oracle engineer, who worked with Java perfomance, "when do you prefer to use LinkedList instead of ArrayList?". "Never in real life" - he answered, - "I can imagine synthetic cases, when LinkedList better ArrayList, but in real life it's almost impossible". Reason it's absolutely different O(1) and O(n), ArrayList use fast System memory copy and processor cache, but Linked List almost iterate to next element after added, and very very slow operations without processor cache. – Slava Vedenin Dec 10 '18 at 17:16
Plus, LinkedList need 6 times more memory. – Slava Vedenin Dec 10 '18 at 17:16
That's fair. I come from the C++ world so I'm not really used to the extra inefficiencies that come with VMs. – Nick Mertin Dec 11 '18 at 16:04
Eclipse Collections also has an array based Stack implementation, that doesn't extend Vector - https://www.eclipse.org/collections/javadoc/9.2.0/org/eclipse/collections/impl/stack/mutable/ArrayStack.html – Donald Raab Jan 06 '19 at 02:10

Stack class in java.util package

1 Answers1