2
$\begingroup$

Let's say I want to make a Stack class in JavaScript. The class will have a 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.push() and 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.shift() and Array.unshift() are O(n) operations), but not for Stacks.

Thanks!

Improve this question
$\endgroup$
2
  • $\begingroup$ To my knowledge, an array would almost always run much faster (and even for Queues or double-ended queues, you can implement it using an array in a clever & fast way). So I don't think there is any other argument you haven't covered here. $\endgroup$
    – nir shahar
    Commented Mar 1, 2022 at 20:02
  • $\begingroup$ "every other operation as Arrays are far more optimized than Linked Lists": what do you mean ? If you allude to the fact that arrays support random access, this is irrelevant as a queue ADT only needs to support push and pop. I disagree with your "far more" and your "optimized". Can you explain ? $\endgroup$
    – user16034
    Commented Apr 1, 2022 at 10:18

1 Answer 1

Reset to default
-1
$\begingroup$

If you are only considering the implementations, then yes what you have mentioned is correct. However when you consider the use cases, then you might want to think further. For example if your use case has very less push/pop operations then arrays are well suited else you can use linked list. If your use case requires frequent reading and using of indexes then array is the one to go. These might not seem the operations of a stack but sometimes you may need to implement such a data structure which could behave like a stack while providing other operations too.

What you are comparing is actually a data structure vs a concept. A linked list can be implemented using an array too and you can have the best of both. Then you can extend the idea to implement a stack.

This is just some food for thought since you asked for some insights. You can try out different implementations to see what works out best.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ A stack does not support insert nor delete. $\endgroup$
    – user16034
    Commented Apr 1, 2022 at 10:21
  • $\begingroup$ I never said it did, since op was comparing the implementations based on arrays and linked lists, I used the terms insert and delete as stack operations on both are essentially insert and delete. $\endgroup$
    – Rinkesh P
    Commented Apr 2, 2022 at 6:49
  • $\begingroup$ No, the operations are push and pop, a tiny subset of insert and delete. $\endgroup$
    – user16034
    Commented Apr 2, 2022 at 8:26
  • $\begingroup$ I agree. Its a case of misinterpretation, but since push/pop is a subset of insert and delete i dont see why using insert and delete is outright wrong. I have edited my answer accordingly $\endgroup$
    – Rinkesh P
    Commented Apr 2, 2022 at 8:53
  • $\begingroup$ Don't you understand that complexities are quite different. $\endgroup$
    – user16034
    Commented Apr 2, 2022 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.