Search code examples
arraysalgorithmdata-structuresstackqueue

What is the advantage of arrays over linked-lists when implementing stacks and queues


Why might we want to use an array to implement a stack and a queue, when it could be done with linked-list? I just learned to implement stacks and queues using linked list so naturally using arrays doesn't make sense to me as of now, more specifically we could benefit O(1) push and pop just manipulating the head pointer, and without having to worry about the size of an array, unless it get's too big.


Solution

  • If you're implementing a pure stack (where you only ever access the first item), or a pure queue (where you only access the first or last), then you have O(1) access regardless of whether you've implemented it as an array or a linked list

    As you mentioned, using an array has the disadvantage of having to resize when the data structure grows beyond what you've already allocated. However, you can reduce the frequency of resizing by always doubling the size. If you initially allocate enough space to handle your typical stack size, then resizing is infrequent, and in most cases one resize operation will be sufficient. And if you're worried about having too much memory allocated, you can always add some logic that will reduce the size if the amount of memory allocated far exceeds the number of items in the data structure.

    Linked lists have definite benefits, but each addition to the linked list requires an allocation (and removal, a deallocation), which takes some time and also can lead to heap fragmentation. In addition, each linked list node has a next pointer, making the amount of memory per item more than what would be required for an array. Finally, each individual allocation has some memory overhead. All in all, a linked list of n items will occupy more memory than an array of n items.

    So there are benefits and drawbacks of each approach. I won't say that either can be considered "best," but there are very good reasons to implement these data structures with arrays rather than linked lists. Correctly implemented, an array-based stack or queue can be faster and more memory efficient than a linked list implementation.