關於Java中

Question

的文件執行ArrayDeque的說：

大小可變數組實現雙端隊列接口。 Array deques 沒有容量限制;他們根據需要增長以支持使用

但是我仍然想了解ArrayDeque的結構究竟是什麼，調整大小如何工作。如果有人能夠提供可靠的信息來源，我可以找到答案，這也是非常好的。根據我發現的一些Google結果，它可能被實現爲圓形陣列。這是真的嗎？什麼是增長政策？它與ArrayList相似嗎？如果是這樣，ArrayDeque在類似於ArrayList的操作中是否像在末尾添加或刪除元素一樣操作？

謝謝。

Answer 1

ArrayList和ArrayDeque的增長策略沒有記錄，並且可能因JDK實現甚至JDK版本而異。例如，在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來說，尾部的添加幾乎同樣快，除非需要重新分配。重新分配事件可能發生在不同的點。例如，默認情況下，在添加元素＃11時將首先爲ArrayList重新分配，但對於ArrayDeque，將在元素＃16上發生。

ArrayDeque的優勢是能夠將元素添加到頭部的速度與尾部一樣快。相反，ArrayList將在O(n)時間內完成，因爲它必須移動所有現有元素。因此，在需要添加/刪除頭部和尾部時，請使用ArrayDeque。如果您只需要修改尾部，通常首選ArrayList。