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

- Insertion
- Deletion
- 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.

- Inserting at the front of the list
- Inserting at the back of the list
- 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()