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.

push
push(11)
push
push(22)
Stack using Linked List
push(33)


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.

Stack using Linked List
Current stack content
pop in stack
Stack after 1st pop()
pop in stack
Stack after 2nd pop()
pop in stack
Stack after 3rd pop()


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.

Stack using Linked List
Current Stack

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.

size():

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.

display():

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.

Stack using Linked List

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

Stack using Linked List

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

Stack using Linked List

Now increment the temp pointer and go to the next node. It is null, so stop.

Stack using Linked List

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())

Output:

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

Leave a Reply

Your email address will not be published. Required fields are marked *