Menu
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?
332
Time complexity for ArrayDeque for accessing a element is O(1) and that for LinkList is is O(N) to access last element. ArrayDeque is not thread safe so manually synchronization is necessary so that you can access it through multiple threads and so they they are faster.
The ArrayDeque class implements the Deque interface In fact, the Java API documentation even states that the ArrayDeque class will often times be faster than a Queue or a Stack. This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.
If you want to search or access a specific element, arrays are faster, but if you want to insert or delete an element, a linked list is faster.
An ArrayDeque (also known as an “Array Double Ended Queue”, pronounced as “ArrayDeck”) is a special kind of a growable array that allows us to add or remove an element from both sides. An ArrayDeque implementation can be used as a Stack (Last-In-First-Out) or a Queue(First-In-First-Out).
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.
83
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.
24
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
