Why is the stack implemented as a linked list? What is the need, why is the implementation of the array insufficient?

Question

Many times, the stack is implemented as a linked list. Whether the representation of the array is not good enough, we can easily execute push pop in the array, and the linked list in the array complicates the code and has no advantage over the implementation of the array.

Can you give some example when the implementation of a linked list is more profitable, or we can not do without it.

Answer 1

I would say that many practical stack implementations are written using arrays. For example, the .NET Stack implementation uses an array as a backup storage.

Arrays are generally more efficient, as you can keep the stack nodes all next to it in continuous memory, which can fit nicely into your fast cache lines on the processor.

I assume that you see realistic stack implementations that use linked lists, because they are easier to write and do not force you to write a little extra code to manage the storage of arrays, as well as with the growth / copy / reserve heuristic space.

In addition, if you really want to use small memory, implementing a linked list may make sense, since you are not “losing” space that is not currently in use. However, on modern processors with a large amount of memory, it is usually better to use arrays to take advantage of the cache that they offer, rather than worry about page problems using the linked list method.

Answer 2

The size of the array is limited and predetermined. When you do not know how many of them are, then a linked list is ideal.

More detailed comparison: - (+ for the dominant linked list and - for the array)

Size and type constraint:-

• (+) Further members of the array are aligned at an equal distance and need continuous memory, and irregular memory solutions can be implemented in another list of links, therefore it is sometimes useful for memory in case of huge data (avoids querying the processor for the resource).

• (+) Suppose that in the case when you use the array as a stack, and the array is of type int.Now, how will you fit double into it?

Portability

• (+) An array can throw exceptions, such as an index from related exceptions, but you can increase the chain at any time in the linked list.

Speed and performance

• (-) If its about performance, then obviously most of the complexity is in O (1) for arrays. In the case of a linked list, you will need to select the starting node to start tracing, and this adds to the execution penalty.

Answer 3

When the stack size can vary greatly, you lose space if you have generalized procedures that always allocate a huge array.

Answer 4

Obviously, a fixed-size array has the limitation of knowing the maximum size before starting work.
If you consider a dynamic array , then the Linked List versus Arrays covers the details, including the complexity of the operations.

Answer 5

Stack is implemented using the Linked List, because Push and Pop operations have O (1) complexity compared to O (n) for arrays. (except for the flexibility of Linked List size)