Doubly Linked List in Python

In this tutorial you will learn about doubly linked list. You will learn how to implement a doubly linked list in Python.

A doubly linked list, unlike a singly linked lists consists of a data value along with a next and previous pointer. Let us see a simple example of a doubly linked list.

In the above figure you can visualize a pictorial representation of a doubly linked list. Every node has a pointer to the next node and a pointer to the previous node represented by the next and prev pointer respectively. 

Operations on a Doubly Linked List

Let us know explore some common operations we can perform on a doubly linked list

  1. Insertion
  2. Deletion
  3. Traversal

Let us first being by defining a node class which contains the next and previous pointer. Whenever a new node is created the two pointers are set to null initially.

class Node(object):
   def __init__(self, value):
       self.data = value
       self.prev = None
       self.next = None

We began by initializing the constructor of the node class and initializing and declaring the data value, the next pointer and the prev pointer.

You can create a node as follows

node = Node(12)

This will create a node with the value 12.

Let us now begin by defining the doubly linked list and implementing the common operations we can perform on it

We begin by declaring a class called DoublyLinkedList and initializing the head pointer to None

class DoublyLinkedList(object):
   def __init__(self):
       self.head = None

Inserting an element in a Doubly Linked List

We will now look at how we can insert a new node in a doubly linked list

There are 3 scenarios that can occur while inserting a node in a list.

  1. Inserting at the front of the list
  2. Inserting at the back of the list
  3. Inserting at a random position in the list

Inserting a node at the front of the list

We start by defining a function called insert_front which takes in a node as an input parameter. We then check if the list is empty or not. If the list is empty we assign the head pointer to the newly created node. If the list is not empty i.e. the head pointer is not None we assign the next pointer of the newly created node to the head of the list and the prev pointer of the head to the node. We then reassign the head pointer to point to the newly created node.

def insert_front(self, node):
       if self.head is not None:
           node.next = self.head
           self.head.prev = node
           self.head = node
       else:
           self.head = node

Inserting a node at the back of the list

We will now look at how to insert a node at the end of the list or the tail of the list.

def insert_back(self, node):
        if self.head is not None:
            current_node = self.head
            while(current_node.next is not None):
                current_node = current_node.next
            current_node.next = node
            node.prev = current_node
        else:
            self.head = node

We define a function called insert_back which takes in a node as an input parameter. We again check if the list is empty or not. If the list is not empty we point the head to the new node. If the list is not empty i.e. there are already some nodes present in the list, we  traverse the list till we reach the tail of the list. Once we are at the tail of the list we assign the next pointer of the last node to point to the new node and the previous pointer of the node to point to the previous tail of the list. At the end of this operation the new node becomes the tail of the list.

Inserting at a random position in the list

We will now look at how to insert a new node in a list at a random position. We first check if the list is empty or not. If the list is empty we insert the node at the front of the list by calling the insert_front function we had implemented. If the list is not empty then we initialize a counter variable and initialize the current node to point to the head of the list. We then go through the list and keep updating the counter and the current node. As soon as we reach the index position where we would like to insert the node, we point the node to the next pointer of the current node, the previous pointer of the node to the current node, and the next pointer of the current node to the newly created node. 

We also check if the next of the new node is the last element or node. If it is not the last element in the list, we point the previous pointer of the next node to the new node.  

def insert(self, node, index):
       if self.head is not None:
           current_counter = 1
           current_node = self.head
           while current_node is not None:
               if current_counter == (index-1):
                   node.next = current_node.next
                   node.prev = current_node
                   current_node.next = node
                   if node.next is not None:
                       node.next.prev = node
               current_node = current_node.next
               current_counter += 1
       else:
           print('List is empty')
           self.insert_front(node)

Deleting an element in a DLL

We will now look at another important operation we can perform on a doubly linked list. We begin by defining a function called  delete. The function will take the node value we would like to delete from the list. We then check if the list is empty or not. If the list is empty then we return from the function. If the list is not empty, we will check if the node we would like to delete is the head node or not. If it is the head node we delete the node and assign the head pointer to None. If the node we would like to delete is not the head node, we will first traverse through the list to find the node, once we find the node in the list we will first declare the node  as a temporary node. The next pointer of the previous element in the list will point to the next pointer of the temporary node and the previous pointer of the next node in the list will point to the previous node. We then assign the temporary node to None and delete the node. 

def delete(self, value):
       if self.head is None:
           print('Doubly Linked List is empty')
           return
       if self.head.next == None:
           if self.head.data ==  value:
               temp_node = self.head
               self.head = None
               del temp_node
               return
           else:
               print("Element is not found in our list")
               return
       else:
           temp_node = self.head.next
           while temp_node is not None:
               if temp_node.data == value:
                   temp_node.prev.next = temp_node.next
                   temp_node.next.prev = temp_node.prev
                   temp_node = None
                   return
               temp_node = temp_node.next
           if temp_node.data == value:
               temp_node.prev.next = None
               del temp_node
               return
           print("Element is not found in the list")

Summary

In this blog post you learned how to implement a doubly linked list in python. We also looked at how to perform some common operations on a list like insertion and deletion.

You can find the entire code below

class Node(object):
   def __init__(self, value):
       self.data = value
       self.prev = None
       self.next = None
 
class DoublyLinkedList(object):
   def __init__(self):
       self.head = None
 
   def insert_front(self, node):
       if self.head is not None:
           node.next = self.head
           self.head.prev = node
           self.head = node
       else:
           self.head = node
 
   def insert_back(self, node):
       if self.head is not None:
           current_node = self.head
           while(current_node.next is not None):
               current_node = current_node.next
           current_node.next = node
           node.prev = current_node
       else:
           self.head = node
 
 
   def insert(self, node, index):
       if self.head is not None:
           current_counter = 1
           current_node = self.head
           while current_node is not None:
               if current_counter == (index-1):
                   node.next = current_node.next
                   node.prev = current_node
                   current_node.next = node
                   if node.next is not None:
                       node.next.prev = node
               current_node = current_node.next
               current_counter += 1
       else:
           print('List is empty')
           self.insert_front(node)
 
 
   def delete(self, value):
       if self.head is None:
           print('Doubly Linked List is empty')
           return
       if self.head.next == None:
           if self.head.data ==  value:
               temp_node = self.head
               self.head = None
               del temp_node
               return
           else:
               print("Element is not found in our list")
               return
       else:
           temp_node = self.head.next
           while temp_node is not None:
               if temp_node.data == value:
                   temp_node.prev.next = temp_node.next
                   temp_node.next.prev = temp_node.prev
                   temp_node = None
                   return
               temp_node = temp_node.next
           if temp_node.data == value:
               temp_node.prev.next = None
               del temp_node
               return
           print("Element is not found in the list")
 
   def display(self,):
       current_node = self.head
       while current_node is not None:
           if current_node.next is None:
               print(current_node.data,  end=' ', flush=True)
           else:
               print(current_node.data,  end='-->', flush=True)
           previous_node = current_node
           current_node = current_node.next
 
       print('\n')
       print('List in reverse order')
      
       while previous_node is not None:
           if previous_node.prev is None:
               print(previous_node.data,  end=' ', flush=True)
           else:
               print(previous_node.data,  end='-->', flush=True)
           previous_node = previous_node.prev
       print('\n')
 
if __name__ == "__main__":
   node1 = Node(12)
   node2 = Node(13)
 
   dll = DoublyLinkedList()
   dll.insert_front(node1)
   dll.insert_front(node2)
   dll.display()
 
   dll.insert_back(Node(14))
   dll.insert_back(Node(26))
 
   dll.insert_front(Node(1))
 
 
   dll.display()
 
 
 
   dll.insert(Node(2), 2)
   dll.insert(Node(5), 3)
 
   dll.display()
 
 
   print('Deleting node')
   dll.delete(5)
   dll.display()