The problem with stack implementation using an array is working with only a fixed number of data elements, so we can also go for stack implementation using linked-list. Linked-list is the data structure that allocated memory dynamically, but in both cases, the time complexity is the same for all the operations like push, pop and peek.
Stack Implementation Using Linked-List
We already knew that linked lists allocate memory dynamically. Stack implementation using linked-list, the nodes are maintained in non-contiguous memory. Each node contains a pointer to the immediate next in line node in the Stack.
In Stack, implementation using Linked-List, every new element inserted to the top of the Stack which means every new inserting element pointed by the top and whenever we want to delete element from the Stack which is pointing to the top of the Stack by moving the top by moving top to is the previous node in the linked -list. The following field of the first element must always be NULL. There is an overflow condition in the Stack if the space left in the memory heap is not sufficient to create a node.
Procedure for Stack Implementation Using Linked-List
Push Operation
Adding a new node in the Stack is termed a push operation.
Pushing a node in the linked list is quite different from inserting an element in the array. Push operation on stack implementation using linked-list involves several steps:
- Create a node first and allocate memory to it.
- If the list is empty, then the node is pushed as the first node of the linked list. This operation assigns a value to the data part of the node and gives NULL to the address part of the node.
- If some nodes are already in the linked list, then we have to add a new node at the beginning to the list not to violate the Stack's property. For this, assign the element to the address field of the new node and make a new node which will be starting node of the list.
- An overflow condition occurs when we try to push an operation if the Stack is already full.
|
void push() { int value; struct node *ptr1 = (struct node*)malloc(sizeof(struct node)); if (ptr1 == NULL) { print("can not push a node"); } else { printf(“enter the value”); scanf(“%d”, &value); if( start == NULL) { ptr1 -> value = value; ptr1 -> next = NULL; start = ptr1; } Else { ptr1 - > value = value; ptr1 -> next = start; start = ptr1; } print("data element pushed"); } } |
Pop Operation
Deleting a node from the Stack is known as a pop operation.
The popping node from the linked list is different from the popping element from the array. To perform the pop operation involves the following steps:
- In Stack, the node is removed from the end of the linked list. Therefore, must delete the value stored in the head pointer, and the node must get free. The following link node will become the head node now.
- An underflow condition will occur when we try to pop an operation when the Stack is already empty. The Stack will be meaningless if the head pointer of the list points to NULL.
|
void pop() { int data; struct node *ptr1; if( start == NULL) { printf(“underflow condition”); } else { data = start -> value; ptr1 = start; start = start -> next; free(ptr1); printf(“dta element popped”); } } |
Traversing
Displaying all the nodes of a stack means traversing all the nodes of linked-list once organized in the form of a stack. Traversing involves the following steps:
- Copy the head pointer to the temp pointer.
- Move the temporary pointer through all the nodes of the ist and print the value field attached to every node.
|
void print { int x; struct node *ptr1; ptr1 == start; if (ptr1 == NULL) { printf("empty stack"); } else { printf(“ displaying stack elements”); while(ptr1!= NULL) { printf(“%d”, ptr1 -> value); ptr1 = ptr1 -> next; } } } |
Pros and Cons of Stack Implementation Using Linked-List
There is some pros and cons of stack implementation using linked-list:
Pros of Stack Implementation Using Linked-List.
-
Dynamic Data Structure
Linked-list is a dynamic data structure, so it can grow and shrink at runtime by allocating and deallocating memory.
-
Insertion and Deletion
Unlike in an array, we don't have to shift elements after insertion and deletion of stuff. Insertion and deletion in linked-list are relatively easier by updating the address present in the next pointer of a node.
-
No Memory Wastage
In linked lists, the size can be increased and decreased at the run time leading to no memory wastage.
Cons of Stack Implementation Using Linked-List.
-
Memory Usage
More memory is required to store elements in a linked list because each node contains a pointer in the linked list, and it requires extra memory for itself.
-
Traversal
Node traversal in linked lists is quite tricky. For example, if we want to access a node at position n, then we have to traverse all the nodes before it. So the time required to access a node is large.
-
Reverse Traversing
Reverse traversing in stack implementation using linked-list is quite tricky because extra memory is required for back pointer hence wastage of memory.
With this, we came to the end of the stack implementation using linked-list articles.
Advance your career as a MEAN stack developer with the Post Graduate Program In Full Stack Web Development. Enroll now!
Next Step
"Queue implementation using linked-list" can be our next topic where we will learn how to implement a queue using linked-list structure.
If you are interested in building a career in the field of software development, then feel free to explore Simplilearn's Courses that will give you the work-ready software development training you need to succeed today.
If you have any questions regarding the "stack implementation using linked-list" article, please feel free to ask in the comment section below. We will be pleased to resolve your problems as soon as possible. Until then, stay safe and please keep tuned with the Simplilearn channel.
