eag*_*sky 1 java arraylist arraydeque
文件说:
Deque接口的可调整大小的数组实现.阵列deques没有容量限制; 他们根据需要增长以支持使用
但是,我仍然想了解ArrayDeque的确切结构,调整大小的工作原理.如果有人可以提供可靠的来源,我可以找到答案,这将是很好的.根据我发现的一些谷歌搜索结果,它可能是一个圆形阵列.这是真的吗？什么是增长政策？它与ArrayList类似吗？如果是,ArrayDeque在操作中是否具有与ArrayList类似的性能,例如在末尾添加或删除元素？
谢谢.
JDK实现甚至JDK版本之间的增长策略ArrayList并ArrayDeque没有记录,可能会有所不同.例如,在Open JDK 6中它是(n*3/2+1),但在Open JDK 8中它是(n*3/2).同样在JDK 6中ArrayList,默认构造函数最初使用10个元素数组创建,而在JDK 8中,它仅在添加至少一个元素时才分配数组.
该ArrayDeque实施更为往往比改变ArrayList.它总是在内部使用的乘方的二大小的数组起始16默认和加倍它时必要,这样内存占用可以是用于不同ArrayList和ArrayDeque(对于ArrayDeque你将有平均较少的重新分配,但是更多的浪费存储器).
除非需要重新分配ArrayList,ArrayDeque否则对尾部的加法大致相同.重新分配事件可能发生在不同的点.例如,默认情况下,ArrayList在添加元素#11时将首先重新分配,但是因为ArrayDeque它将在元素#16上发生.
其优点ArrayDeque是能够以尽可能快的速度向尾部添加/移除元素.相反,ArrayList会做的O(n)时间,因为它必须将所有已经存在的元素.因此,ArrayDeque当您需要添加/删除头部和尾部时使用.如果您只需要修改尾部,通常ArrayList是首选.