In this article, we will learn how to implement a stack using a linked list. A stack is an abstract data structure that works on the Last in First Out (LIFO) mechanism. In other words, an item that gets inserted last gets removed first. A singly linked list is a data structure that contains a sequence of nodes. A node typically has a data item and a reference to the next node. We can implement a stack by Using a singly linked list. So, let’s get started.

This implementation of the Stack contains the following functionalities.

Push

The push operation adds value at the top of the Stack. In other words, it inserts a value at the beginning of the linked list. To perform this operation, first, we create a node with the given value.

If the node to be added is the first one, then, in this case, the linked list will be empty, i.e., the top pointer will be NULL. Now we assign the created node to the top, and its next will be NULL as it is the only node.

If the linked list contains other items, we set the current top as the next of the created node and update the top to point to the newly created node.

Pop

This operation removes and returns the value at the top of the Stack, i.e., it deletes the node at the beginning of the linked list. If the Stack (linked list) is empty, then it raises a stack underflow exception. Otherwise, it stores the node at the top in a temporary variable. Then, it updates the top pointer to refer to its next node. It puts the temporary node’s (node to be deleted) value in a variable, free the memory by deleting that node, and returns the deleted value.

Peek

This method returns the value at the top of the Stack, i.e., it outputs the top node’s value in the linked list. If the Stack (linked list) is empty, it raises a stack underflow exception.

Display

It prints all the contents of the Stack from top to bottom.

How to Implement a Stack using Linked List

The code of the implementation of the Stack using the linked list is given below.

class StackUnderflowError(Exception):
  #Raised when an operation such as pop is applied on an empty stack
  def __init__(self, message):
    self.message = message
    super().__init__(self.message)

#node for the linked list
class Node:
  def __init__(self, value=None, next=None):
    self.value = value 
    self.next = next #reference to the next node

#implementation of stack using linked list
class StackLinkedList:
  def __init__(self):
    self.top = None
    self.length = 0 #total number of elements in the linked list

  #this method returns the length of the stack
  def len(self):
    return self.length

  #this method adds a value at the top of the stack, i.e., at the beginning of the linked list
  def push(self, value):
    node = Node(value, self.top) #creating a new node with the given value and the next pointer to the current top
    self.top = node #update the new top
    self.length += 1 #increment the length

  #this method removes a value from the top of the stack, i.e., at the beginning of the linked list, and returns the value
  def pop(self):
    if self.top:
      temp  = self.top
      self.top = self.top.next #update the top to refer to the next of the current top
      popped_value = temp.value
      self.length -= 1 #decrement the length
      del temp 
      return popped_value
    else: #stack empty
      raise StackUnderflowError("Stack Underflow")
  
  #this method returns the value at the top of the stack, i.e., value of the first (top) node
  def peek(self):
    if self.top:
      return self.top.value
    else: #stack empty
      raise StackUnderflowError("Stack Underflow")

  #this method displays the contents of stack, i.e., print all values stored in the linked list
  def display(self):
    temp = self.top
    while temp:
      print(temp.value, end="\t")
      temp = temp.next
    print("")

stack = StackLinkedList()

#add values into a stack 
stack.push(1)
stack.push(5)
stack.push(3)
stack.push(9)
stack.push(10)

#display the contents of the stack
print("Display the contents of the stack")
stack.display()

#get the value at the top of the stack
print("Value at the top:", stack.peek())

#remove values from the stack
print("Popped item:", stack.pop())
print("Popped item:", stack.pop())

#display the contents of the stack
print("Display the contents of the stack")
stack.display()

#get the value at the top of the stack
print("Value at the top:", stack.peek())

Output

Display the contents of the stack
10	9	3	5	1	
Value at the top: 10
Popped item: 10
Popped item: 9
Display the contents of the stack
3	5	1	
Value at the top: 3

stack = StackLinkedList()

#add values into a stack 
stack.push(1)
stack.push(5)

#display the contents of the stack
print("Display the contents of the stack")
stack.display()

#get the value at the top of the stack
print("Value at the top:", stack.peek())

#remove values from the stack
print("Popped item:", stack.pop())
print("Popped item:", stack.pop())
print("Popped item:", stack.pop())

Output