Introduction
The Doubly Linked List data structure is crucial for preparing for technical rounds while facing interviews in tech giants such as Facebook, Amazon, Apple, Google, etc. (a.k.a - FAANG). You can see a variety of tricky as well as straightforward questions on this topic. This article will guide you in implementing the stack data structure using a Doubly Linked List.
To implement a stack using a Doubly Linked-List, one should be well versed in the implementation and applications of Doubly Linked-List; you should be clear in your head what a linked list is and how a Doubly Linked-List is implemented using Python along with the implementation and working of the Stack data structure.
Also see, Features of Doubly Linked List
What is a linked list?
A linked list is a linear data structure where every element acts as a node with two parts data part(which stores the actual data of the element) and the address part(which holds the address of the location of the next node). Linked lists are dynamic, which eases the insertion and deletion of the elements.
How is a doubly-linked list different?
A doubly-linked list is a variant of a linked list that consists of nodes containing two fields instead of one (unlike linked lists), called ‘next’ and ‘prev’, that refers to the previous and the next node in a sequence of nodes.
What is a stack? How can it be implemented with the help of a doubly-linked list?
A Stack is a linear data structure that allows the most recently added elements to be removed first, more popularly known as LIFO ( last in, first out). So, both the insertion and deletion of elements happen only from one end, i.e. from the top of the stack.
Also read, Fibonacci Series in Python
Abstracted methods that will be Implemented
One can use a doubly-linked list to mock the functionalities and features of a stack by implementing the following set of methods that a stack internally utilises-
push()
Since the push method is used in a stack to insert elements into it from one end of the stack, the same doubly linked list can also implement by inserting an element such that the head node pointer always points to the newly inserted element.
pop()
Since the pop method is used to remove the top element from the stack from one end, one can also implement it through a doubly linked list by changing the node the head pointer is pointing to its adjacent node in the doubly linked list.
top()
A stack uses this method to return the topmost element from it. One can do this in a doubly-linked list by replacing the data in the node that the head node is pointing to.
size()
The size method will return the count or number of elements in the stack which would be the same as the length of the doubly linked list in this case.
isEmpty()
This method returns whether the stack is empty or not, which would be equivalent to the head node pointer pointing to a NULL value in the case of our doubly linked list.
printStack()
The method to print the elements present in the stack would be simply traversing and then printing the elements in the doubly linked list.
Implementation
We will use this to implement the program.
Code:
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:
newNode = Node(data)
self.head.prev = newNode
newNode.next = self.head
newNode.prev = None
self.head = newNode
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("The elements in the stack 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(10)
stack.push(5)
stack.push(7)
stack.push(3)
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
The elements in the stack are: 3->7->5->10->
The top element is 3
The size of the stack is 4
The elements in the stack are 5->10->
Stack is empty: False.
You can also practice with the help of Online Python Compiler
Explanation
As you can see here, we were able to mimic the functionalities of a stack using a doubly-linked list abstraction.
First, we pushed four different elements in the stack using the doubly linked list.
Where the head pointer of our doubly linked list acted as the top pointer in our stack.
head->3->7->5->10->
Now 3 has become the head of the list as it is the starting node of this doubly linked list.
Then we try to test various methods of a stack that we have implemented, such as top(), pop(), size() and isEmpty(), whose results we can also see in the output that we got above.
Must Read Stack Operations
Complexity Analysis
Time Complexity: O(n), for traversing the doubly linked list in various method implementations of a stack that we did.
Space Complexity: O(1) as no extra space was created or used to implement the stack other than the doubly linked list we used.
Must Read Python List Operations
34+ registered 
