Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

ArrayDeque vs ArrayList to implement a stack

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 an ArrayList. You can use an ArrayList 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 than ArrayDeque. What accounts for this difference? Surely, it can't just be the calls to size()? Internally, both ArrayList and ArrayDeque are implemented using an Object[] that is replaced by a larger array when required, so surely the performance should be about the same?

like image 348
Paul Boddington Avatar asked Apr 11 '15 21:04

Paul Boddington


People also ask

Why is ArrayDeque stack faster than ArrayList?

There are multiple reasons to use ArrayDeque instead of Stack as ArrayDeque is a Doubly ended Queue implemented as an Array. So, it can grow relatively faster. If you do not plan to use syncronized stack, then ArrayDeque is probably better than Stack which is Thread safe(and hence slow).

Is ArrayDeque faster than stack?

ArrayDeque class is likely to be faster than Stack when used as a stack. ArrayDeque class is likely to be faster than LinkedList when used as a queue.

What is the difference between ArrayDeque and ArrayList?

When to use ArrayList and when to use ArrayDeque? ArrayDeque has the ability to add or remove the elements from both ends (head or tail), on the other hand removing last element from ArrayList takes O(n) time as it traverses the whole list to reach the end.

Can you implement a stack with an ArrayList?

For beginners, using ArrayListA stack is one of the most simplest data structure to understand. If you had data structures in your academia, you already know what it means. It's a simple Last In First Out (LIFO) queue. What that means is the last element to enter the stack will be first element to go out of the stack.


1 Answers

The main difference between both implementation is the resize strategy

  • ArrayList is resized to a new size of oldCapacity + (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)

like image 72
Gerald Mücke Avatar answered Sep 22 '22 07:09

Gerald Mücke