I have some doubt regarding this behavior.I assume performance of ArrayList would be same as ArrayDeque while implementing stack as ArrayDeque will use its addLast() method for insertion and removeLast() for deletion.Both will be equally efficient in this case.Please correct me if I am wrong somewhere.
1
-
Why don't you test that behavior?Vince– Vince2015-05-01 16:23:15 +00:00Commented May 1, 2015 at 16:23
Add a comment
|
2 Answers
When used as stack, ArrayDeque and ArrayList's performance should be almost the same. Both "push" would be amortized O(1), though their initial capacity might have a slightly affect on the performance.
The default capacity for ArrayList is 10, while the initial capacity of ArrayDeque is 16. Their internal growth policies cause small performance difference which might not be noticable in practice. You can refer to this post for more information.
After all, their "push" operation is amortized O(1).
** This post mentions ArrayDeque's javadoc suggests that it may be slightly faster, but I haven't found the source.
Comments
They are both amorized O(1) with stack operation. The main difference is:
- ArrayDeque is resized by factor 2, while ArrayList is 1.5
- The initial capacity of ArrayDeque is 16, while ArrayList is 10
So when using them to to store 1024 elements, ArrayDeque calls 6 resize methods, while the ArrayList only calls 12 methods, nealy 2 times of the ArrayDeque.
