Last Updated: Mar 27, 2024
Difficulty: Medium

# Python Stack Using Doubly Linked List

## 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

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

def push(self, data):

else:
newNode = Node(data)
newNode.prev = None

def pop(self):

return None
return temp
else:
return temp

def top(self):

def size(self):

count = 0
while temp is not None:
count = count + 1
temp = temp.next
return count

def isEmpty(self):

return True
else:
return False

def printStack(self):

print("The elements in the stack are:")
while temp is not None:
print(temp.data, end ="->")
temp = temp.next

if _name=='_main_':

stack = Stack()

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:

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.

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.

### 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.

### What do you mean by a doubly-linked list?

It is a specific type of linked list with two pointers, i.e. a next and a previous node pointer, instead of one, which gives it bidirectionality.

### What are the various methods and properties that a stack has?

We have used and implemented the following set of stack methods here: push(), pop(), top(), size(), isEmpty(), printStack().

## Conclusion

In this article, we looked at implementing a stack through a doubly linked list in Python, which is one of the must-do problems and abstractions that one should understand well. Here, we tried to implement various functionalities and properties of a stack such as push(), pop(), top() etc., using a doubly-linked list data structure.

If you want to prepare for interviews, you can visit Coding Ninjas Studio and brush up on your skills for top product-based companies on topics such as linked lists.

Recommended Problems -

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

You can also consider our Mern Stack Course to give your career an edge over others.

Keep Coding!!!

Topics covered
1.
Introduction
2.
Abstracted methods that will be Implemented
2.1.
Implementation
2.2.
Complexity Analysis
3.