How is ArrayDeque faster than stack?

Question

According to javadoc,

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

I don't understand how can ArrayDeque be faster than stack. Suppose stack is implemented using linkedlist as follows:

Push: Insert new element at the head, teamp->next = head; head = temp 
(where temp is the element to be inserted)
Pop: Remove the element from head, and make head = head->next

For large number of elements, there will be a overhead for ArrayDeque to resize which won't be a case in Stack implemented using LinkedList. So how exactly is ArrayDeque faster than stack?

Answer 1

ArrayDeque is part of the Java Collections Framework and is not written to be inherently thread safe.

Stack, together with Vector and Hashtable came with Java 1.0 and were implemented with thread safe operations (because it seemed like a good idea at the time). Acquiring and releasing thread locks is relatively expensive time wise, hence those data structures will be much slower than their compatriots in the JCF.

Answer 2

Because most operations don't require the array to resize, particularly once the queue has reached a stable size and isn't growing any more.

Every time you add an item Stack has to allocate new objects update the links, etc.

ArrayDeque just needs to put an object in the array and update an index.

Answer 3

The keyword is "likely". If resizing does occur, then it can be slower, but a stack isn't likely to grow that much.

Answer 4

In my experience, linked lists are more efficient than array lists in one case only - where you frequently want to add or remove multiple elements from random points within the list in a single pass through it. In every other case, an array list is usually better - faster lookup, random access, less memory. If ArrayDeque is based on an array - it is likely to not need to allocate additional node objects for each item stored within it.

Since a stack usually has items added / removed to the end of the list, an array based solution is likely to be more efficient

Answer 5

As long as the main operation you do is not a 'contains' search or a 'bulk insert' etc, an array will work faster compared to other data structures. The 'faster' part is always depending on the usage. On average, ie if you take mean times, ArrayDeque wil be faster than a Stack.

Answer 6

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). ArrayDeque has better locality of reference as well.