[ACCEPTED]-How is ArrayDeque faster than stack?-arraydeque

Accepted answer
Score: 31

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

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

Score: 8

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

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

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

Score: 2

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

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

Score: 1

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

Score: 1

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

Score: 0

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

More Related questions