Search code examples
javastackarraydeque

How is ArrayDeque faster than stack?

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?

Solution

  • 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.