Python Stack using a Doubly Linked List

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we have to implement a stack, with the help of a doubly linked list.

Input:

Output
For the input 4 3 2 1 our doubly linked list, which will have all functionalities of a stack, will be

and 1 will be the head of the linked list.

Problem Statement Understanding

Let’s think about how a stack works.
It follows the LIFO(last in first out) principle. This means the element inserted at the last will be accessible to us.

Now, lets recall what a doubly-linked list is. A doubly linked list has two pointers for every node:

  • prev, which points to the previous node in the linked list.
  • next, which points to the node next to the current node in the linked list.

If we can amend the inserting new node operation in doubly linked list such a way that the current inserted element is always at the head of the linked list and is the first element accessible to us if we want to access an element from linked list, then we can see that our linked list is mimicking the behavior of stack.

Similarly, we will try to think of other operations such as pop(), top(), etc of stack and how we can implement these operations using doubly linked list.

If our input is 4 3 2 1, then our doubly linked list, which will have all functionalities of a stack, will be

Where the head will be pointing to 1 in the linked list.

If input is 5 6 7 8, the the doubly linked list having all the functionalities of the stack will be

Head will be pointing to 8.

Let us have a glance at the algorithm.

Algorithm

There are mainly 6 functions of a stack. We will learn each function's approaches one by one.

push()

In the push() function, we push the element into the stack, and make it the top.

So, to do the same with a doubly-linked list, we will check if the list is Null or not:

  • If it is Null, then make the new data the head.
  • If the list is not empty, then make the prev of head point to the new node, the next of new node point to the head and the prev of new node point to Null.

In the end, the new node will become the head.

pop()

In the pop() function, we pop the topmost element of the stack and print it.

So, to do the same with a doubly-linked list, first, we will check if the list is Null or not:

  • If it is Null, then return None.
  • If there is only one node in the list, then remove the head, and return None.
  • If both the base cases fail, we will store the head.data . Now, we will increment the head, and make the prev of head point to Null.

In the end, we will return the head.data that we stored.

top()

In the top() function, we have to return the top element of the stack.

So, to do the same with a doubly-linked list, we will simply return the head.data.

size()

In the size() function, we have to return the size of the stack.

So, to do the same with a doubly-linked list, we will simply create a counter and initialize it with 0. Then we will traverse through the list and increment the counter by 1 till we reach the end.

In the end, we will return the counter, as that will be the size of the list.

isEmpty()

In the isEmpty() function, we have to return true if the stack is empty, else false.

So, to do the same with a doubly-linked list:

  • If the head is Null, we will return true.
  • Else we will return false.

printstack()

In the Printstack() function, we have to print the stack.

So, to do the same with a doubly-linked list, we will simply do a list traversal and print the elements one by one.

Dry Run

Code Implementation



class Node:
  

    def _init_(self, data):
        self.data = data 
        self.next = None 
        self.prev = None        
          

class Stack:
   
    def _init_(self):
        self.head = None
          

    def push(self, data):
  
        if self.head is None:
            self.head = Node(data)
        else:
            new_node = Node(data)
            self.head.prev = new_node
            new_node.next = self.head
            new_node.prev = None
            self.head = new_node
              

    def pop(self):
  
        if self.head is None:
            return None
        elif self.head.next is None:
            temp = self.head.data
            self.head = None
            return temp
        else:
            temp = self.head.data
            self.head = self.head.next
            self.head.prev = None
            return temp
  

    def top(self):
  
        return self.head.data
  

    def size(self):
  
        temp = self.head
        count = 0
        while temp is not None:
            count = count + 1
            temp = temp.next
        return count


    def isEmpty(self):
  
        if self.head is None:
           return True
        else:
           return False
              

    def printstack(self):
          
        print("stack elements are:")
        temp = self.head
        while temp is not None:
            print(temp.data, end ="->")
            temp = temp.next           
          

if _name=='_main_': 
  

  stack = Stack()
  

  print("Stack operations using Doubly LinkedList")
  stack.push(4)
  stack.push(3)
  stack.push(2)
  stack.push(1)
  stack.printstack()
  
  print("\nTop element is ", stack.top())
  
  print("Size of the stack is ", stack.size())
  
  stack.pop()
  stack.pop()
    
  stack.printstack()

  print("\nstack is empty:", stack.isEmpty())

Output

Stack operations using Doubly LinkedList
stack elements are: 1->2->3->4->
Top element is 1
Size of the stack is 4
stack elements are: 3->4->
stack is empty: False

Time Complexity: O(n), as list traversal is needed.

So, in this article, we have tried to explain the most efficient approach to implement a stack in python, using a doubly-linked list. This is a must-do problem as it requires the basic concepts of the doubly linked list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Merge Sort for Doubly Linked List
Next post Rotate a Linked List

Leave a Reply

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