Stack implementation using linked list

 
A stack is an linear data structure that serves as a collection of elements, with three main operations: push, pop and peek. We have discussed about these operations in previous post and covered array implementation of stack data structure. In this post, linked list implementation of stack is covered.
 

A stack can be easily implemented through a linked list. In linked list implementation, a stack is then a pointer to the “head” of the list where pushing and popping items happens at the head of the list, with perhaps a counter to keep track of the size of the list.

The advantage of using linked list over arrays is that it is possible to implement a stack that can grow or shrink as much as needed. Using array will put a restriction to the maximum capacity of the array which can lead to stack overflow. Here each new node will be dynamically allocated, so overflow is not possible unless memory is exhausted.

 
C implementation –
 

Download   Run Code

Output:

Inserting 1
Inserting 2
Inserting 3
Top element is 3
Removing 3
Removing 2
Removing 1
Stack is empty

 

The time complexity of push and pop operations is O(1).
 

 
References: https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz