java - 为什么 java.util.Stack 不使用 LinkedList 的复合模式，而是使用 Vektor？

Question

我试图理解这一点:

在java中，Stack扩展了Vector。没关系。这是一个同步实现。但是，并不总是需要同步，在这种情况下，建议使用 ArrayDeque。

但是如果 Stack 是使用 LinkedList 的复合模式构建的，不是会更好吗？ LinkedList 为插入和删除提供了更好的性能。此外，数组的大小是固定的，每当您需要增加列表的大小时，您还需要重新分配一个新数组并将内容复制过来。 最后，使用 LinkedList，Stack 的实现可能比数组更简单、性能更高。

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();
    }
}

}

Answer 1

这个:

LinkedList provides better performance for inserting and deleting.

还有这个:

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

不正确。

即使您考虑到这一点，它们仍然是不正确的:

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 基于 Vector，因为它在速度和内存消耗方面都比链表更高效。

假设您将 100 万个项目推送到列表末尾/堆栈顶部。

总共执行了多少内存分配？ vector :~20。链接列表:~1000000

修改了多少字节(与所用的剩余时间几乎成正比)？ vector :~10MB。链接列表:~24MB

总内存消耗？ vector :~4MB，链接列表:~16MB