24

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?

Gaurav
  • 1,005
  • 3
  • 14
  • 33

6 Answers6

34

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.

Steve C
  • 18,876
  • 5
  • 34
  • 37
9

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.

Tim B
  • 40,716
  • 16
  • 83
  • 128
  • 5
    Is this correct? Considering that the Java stack is actually not implemented using any linked structure, and just assumed by the OP. – ptntialunrlsd May 26 '17 at 06:00
3

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

tofarr
  • 7,682
  • 5
  • 22
  • 30
  • 1
    Actually I'd argue the random point within the list criteria is still not specific enough. Unless you are already iterating over the list anyway then `ArrayList` may well still be faster as shuffling the elements after the modified one up is not much slower than the list scan required just to find the element in a `LinkedList`. Basically modifying the list as you search it or lots of operations at the head of the list is where `LinkedList` has an advantage. – Tim B May 28 '14 at 10:06
  • @Tim B - I have updated my answer to reflect this - you are correct. – tofarr May 28 '14 at 10:11
2

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.

Ayush
  • 1,510
  • 11
  • 27
Kamal
  • 309
  • 2
  • 5
1

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

Kayaman
  • 72,141
  • 5
  • 83
  • 121
0

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.

Girish
  • 93
  • 8