push() and a
pop() method. I have two options for the underlying data structure I can use: Linked Lists or Arrays.
Using a Linked List I will have O(1) average and worst time complexities.
Using an Array I will have O(1) average and O(n) worst time complexities, since
Array.pop() have O(1) amortized time complexities.
While the Array implementation will occasionally encounter an O(n) operation, it will likely be much faster than the Linked List implementation for every other operation as Arrays are far more optimized than Linked Lists.
Is there any other argument to using a Linked List-based implementation of a Stack other than what I have covered?
I can see why Linked Lists are better for Queues (since
Array.unshift() are O(n) operations), but not for Stacks.