ArrayDeque vs ArrayList to implement a stack
The main difference between both implementation is the resize strategy
ArrayList
is resized to a new size ofoldCapacity + (oldCapacity >> 1)
, resulting in an increse of ~50%. The default capacity is 10, resulting in a capacities after resize of 15, 22, 33, 49, 73, 109, 163, 244, 366...ArrayDeque
is always resized to a power of 2. On resize, the capacity is doubled. Starting with the default of 16, the resuling capacities after resize are 32, 64, 128, 256,...
So the ArrayDeque reaches higher capacities with much less resize operation, which are costly because of array copy. I.e. to store 256 in default-sized ArrayList, it requires 9 resize calls, while the ArrayDeque only need 4. Array copy may be fast, but may also require a GC to free some space for the new data sets, in addition to the memory copy costs (where the ArrayDeque might also perform better due to it's alignment to power-of-2).
Both datastructures have best-case complexity of O(1) for push and pop through direct access on either head
& tail
(ArrayDequeue) respectively add and remove(Last) size
(ArrayList)
Paul Boddington
Updated on July 13, 2022Comments
-
Paul Boddington almost 2 years
The documentation for
ArrayDeque
says:This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.
There is no mention of the difference between using an
ArrayDeque
as a stack and using anArrayList
. You can use anArrayList
as a stack as follows.list.add(object); // push object = list.remove(list.size() - 1); // pop
I found that when I used an
ArrayList
in this way only, its performance is worse thanArrayDeque
. What accounts for this difference? Surely, it can't just be the calls tosize()
? Internally, bothArrayList
andArrayDeque
are implemented using anObject[]
that is replaced by a larger array when required, so surely the performance should be about the same?