Stack using Linked List – Concepts and coding
The implementation of the stack as an array has one major flaw, which is that it can only handle a predetermined number of data values at once. This indicates that the quantity of data must be specified right at the beginning of the implementation process itself. When we are unsure of the total amount of data that will be utilised, a stack that is implemented using an array is not an appropriate solution. Using a linked list data structure can be a viable alternative to implementing a stack data structure. The stack that makes use of linked lists is capable of functioning for an unlimited number of value entries. That is to say, stacks that are implemented using linked lists can successfully handle data of variable sizes. Therefore, there is no requirement to set a specific size at the start of the implementation. The Stack that is implemented using linked lists has the capacity to organise an unlimited number of data values.
The following procedures can be used to create a stack using a linked list.
Create a class called Node to stand in for each individual node in the linked list. The Node class ought to have two attributes: a value to store the element, and a pointer to the following node in the list. Both of these attributes are required.
Setting the value of the variable top to nothing will allow you to monitor which element is currently on top of the stack.
push(item): To add an element to the stack, you must first create a new Node with the value of the element and set its next pointer to the top of the stack. This is known as the push operation. The top variable should then be set to the newly created node.
pop(): Before removing an item from the stack, you must first determine whether or not the stack is empty (i.e., if top is None). In the event that this is not the case, retrieve the element that is currently located at the top of the stack (also known as the value of the top node), move the top variable to the next node in the list, and then delete the previous top node.
peek(): To retrieve the element at the top of the stack without removing it, simply return the value of the top node. This is referred to as the peek operation.
On peek, 33 will be returned, but stack content will not change
is_empty(): Verify that the top variable has the value None. If this is the case, the stack consists of nothing; if not, it does not.
Measurement involves traversing the linked list from the beginning node all the way to the end node and counting the number of nodes along the way. This indicates the total number of elements that are contained within the stack.
Return the value that is obtained by adding one to the value of the top. This value represents the number of elements that are contained in the stack.
In the case of linked list implementation of stack, temporary pointer temp is initialized with the top pointer. We will keep reversing one by one node until temp points to Null. Initially, temp points to the first node and print the data of the current node, i.e. 33.
Now increment the temp pointer and go to the next node. It is not null, so print the data of that node, i.e. 22
Now increment the temp pointer and go to the next node. It is not null, so print the data of that node, i.e. 11
Now increment the temp pointer and go to the next node. It is null, so stop.
Advantages of Linked list implementation
- The linked list implementation of a stack is capable of expanding and contracting in size in response to the requirements at runtime.
- It is implemented in a variety of virtual machines, including JVM.
Disadvantages of Linked list implementation
- Take note that this implementation makes use of a dynamic linked list; this means that the list can expand or contract depending on the requirements. However, due to the fact that each node in the linked list stores a value as well as a pointer to the following node, the memory requirements are higher than those of the array implementation.
- Accessing the stack in a random order is not possible.
Suggested Reading: Stack using Array
Python code to implement Stack using Linked List
# New Node is inserted at beginig of list. # Top always points to first node in list class Node: def __init__(self, data): self.data = data self.next = None class Stack: def __init__(self): self.TOP = None def push(self, data): # Top is at front of list NewNode = Node(data) NewNode.next = self.TOP self.TOP = NewNode def pop(self): if self.TOP == None: return None else: data = self.TOP.data self.TOP = self.TOP.next return data def peek(self): if self.TOP == None: return None else: return self.TOP.data def is_empty(self): return self.TOP == None def size(self): count = 0 temp = self.TOP while temp is not None: count += 1 temp = temp.next return count def display(self): temp = self.TOP print('Stack Content : ', end ='') while (temp is not None): print(temp.data, end = ' ') temp = temp.next print('') S = Stack() print('EMPTY?: ', S.is_empty()) S.push(11) S.push(22) S.push(33) print('Peek: ', S.peek()) print('Size: ', S.size()) S.display() print('Poped Item: ', S.pop()) print('Poped Item: ', S.pop()) print('Poped Item: ', S.pop()) print('Poped Item: ', S.pop())
EMPTY?: True Peek: 33 Size: 3 Stack Content : 33 22 11 Poped Item: 33 Poped Item: 22 Poped Item: 11 Poped Item: None
YouTube Channel: CodeCrucks