1

I'm trying to understand this:

In java, Stack extends Vector. That's OK. It's a synchronized implementation. However, synchronization isn't always needed, in such cases, it's advised to use ArrayDeque.

But If Stack would have been built using composite pattern with LinkedList, wouldn't it have been better? LinkedList provides better performance for inserting and deleting. Additionally, arrays are fixed in size, anytime you need to increase the size of the list, you also need to reallocate a new array and copy the contents over. Finally, with LinkedList an implementation for Stack may be easier and more performant than array.

public class ListStack implements Stack {

private final List _list = new LinkedList();

public void push(Object value) {
    _list.add(value);
}

public Object pop() throws EmptyStackException {
    if(isEmpty()) {
        throw new EmptyStackException();
    }
    return _list.delete(_list.size() - 1);
}

public Object peek() throws EmptyStackException {
    Object result = pop();
    push(result);
    return result;
}


public void clear() {
     _list.clear();
}

public int size() {
    return _list.size();
}

public boolean isEmpty() {
    return _list.isEmpty();
}

public void enqueue(Object value) {
      push(value);
}

public Object dequeue() throws EmptyQueueException {
    try {
        return pop();
    }catch (EmptyStackException ex) {
        throw new EmptyStackException();
    }
}

}

Curiosa Globunznik
  • 3,129
  • 1
  • 16
  • 24
fgul
  • 5,763
  • 2
  • 46
  • 32
  • There's no need for such a wrapper, as `LinkedList` implements [`Deque`](https://docs.oracle.com/javase/8/docs/api/), just as `ArrayDeque`. Thus, usage is not bound to either class. – Izruo Oct 13 '19 at 13:36
  • 1
    performant ... depends on the use case, linked list is faster for insert/delete, but slower for get, here's a [small study](https://dzone.com/articles/arraylist-vs-linkedlist-vs). – Curiosa Globunznik Oct 13 '19 at 13:36
  • 1
    See also https://stackoverflow.com/questions/58311008/java-adding-time-linkedlist-vs-arraylist/58311267#58311267 – Jim Mischel Oct 13 '19 at 22:49

1 Answers1

2

This:

LinkedList provides better performance for inserting and deleting.

And this:

Finally, with LinkedList an implementation for Stack may be easier and more performant than array

are incorrect.

They're still incorrect even when you consider this:

Additionally, arrays are fixed in size, anytime you need to increase the size of the list, you also need to reallocate a new array and copy the contents over.

Stack is based on Vector, because it's more efficient than a linked list in terms of both speed and memory consumption.

Lets say you push 1 million items onto the end of the list/top of the stack.

How many memory allocations are performed all together? Vector: ~20. LinkedList: ~1000000

How many bytes are modified (pretty much proportional to remaining time taken)? Vector: ~10MB. LinkedList: ~24MB

Total memory consumption? Vector: ~4MB, LinkedList: ~16MB

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87
  • Note for pedants: memory numbers assume a 64-bit VM with compressed oops (https://docs.oracle.com/javase/7/docs/technotes/guides/vm/performance-enhancements-7.html#compressedOop) or a 32-bit VM – Matt Timmermans Oct 13 '19 at 15:11
  • Note for pedants: The memory consumption is of course the list's overhead. If each item requires 1 KB by itself, the total memory consumption is 1 GB (items) + 4~16 MB (list structure). Also note that a re-allocation on a large array-based list is more likely to exceed the JVM's heap space than a new allocation on a linked-based list. – Izruo Oct 14 '19 at 00:18