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 = NoneInserting 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 = nodeWe 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()