ArrayDeque vs ArrayList实现堆栈

Question

文档ArrayDeque说:

当用作堆栈时,此类可能比Stack快,并且当用作队列时比LinkedList更快.

没有提到使用ArrayDeque堆栈和使用堆栈之间的区别ArrayList.您可以使用ArrayList如下堆栈作为堆栈.

list.add(object);                      // push
object = list.remove(list.size() - 1); // pop

我发现当我只用ArrayList这种方式时,它的性能比它差ArrayDeque.这种差异的原因是什么？当然,它不仅仅是电话size()？在内部,都ArrayList和ArrayDeque使用的是实现Object[]由更大的阵列需要时更换,所以可靠地性能应该是大约相同的？

Answer 1

两种实现之间的主要区别在于调整大小策略

• ArrayList调整大小到新的大小oldCapacity + (oldCapacity >> 1),导致增加~50%.默认容量为10,在调整大小为15,22,33,49,73,109,163,244,366后产生容量...

• ArrayDeque总是调整为2的幂.在调整大小时,容量加倍.从默认值16开始,调整大小后的结果容量为32,64,128,256,...

因此,ArrayDeque可以通过更少的调整大小操作来实现更高的容量,由于阵列复制,这些代价很高.即在默认大小的ArrayList中存储256,它需要9次调整大小调用,而ArrayDeque只需要4次.数组复制可能很快,但也可能需要GC为新数据集释放一些空间,除了内存复制成本(由于它与2的幂对齐,ArrayDeque也可能表现更好).

两个数据结构都具有O(1)的最佳情况复杂度,用于推送和弹出直接访问head&tail(ArrayDequeue)分别添加和删除(Last) size(ArrayList)