# Doubly Linked Lists in Python

A doubly linked list is a python data structure wherein the data elements are stored as nodes. In a doubly linked list, each node of the list has two references, one of the previous node and the other of the next node.

Thus, each node holds two addresses along with the data value. Since each node has two references, a doubly linked list allows us to traverse in both directions.

### Creation of a Doubly Linked List

To create a doubly linked list, we initialize the node and linked list class. Next, we set up our list by creating its first element and assigning the “head” and “tail” references to it.

### Algorithm to create a Doubly Linked List

• Step 1: Create a node class with the three required data variables.
• Step 2: Create the Doubly Linked List class and declare the head and tail nodes.
• Step 3: Create a new node and assign it a value.
• step 4: Set the “next” reference of the newly created node to none.
• Step 5: Set the “prev” reference of the newly created node to none.
• Step 6: Set both the head and tail references to the new node.
• Step 7: Terminate.

### Method to create a Doubly Linked List

``````#Creating the Node class
class Node:
def __init__(self, value = None):
self.value = value
self.next = None
self.prev = None

#Create a doubly linked list class to initialize head and tail references
def __init__(self):
self.tail = None

#Function to create Doubly Linked List
def createDLL(self, value):
new_node = Node(value)
new_node.next = None
new_node.prev = None
self.tail = new_node
print("The doubly linked list has been created.")

#Initialize the linked list with a new node
doublyLL.createDLL(5)
print([node.value for node in doublyLL])

#Output
The doubly linked list has been created.
[5]``````

### The iterator function

Since the custom-created linked list is not iterable, we have to add an “__iter__” function so as to traverse through the list.

``````#Iterator Function
def __iter__(self):
while node:
yield node
node = node.next``````

#### Time and Space Complexity

The time complexity for initializing a doubly linked list is O(1). The space complexity is O(1) as no additional memory is required to initialize the linked list.

### Insertion in Doubly Linked List

A node can be inserted in a doubly linked list in any one of the following three ways.

• At the beginning of the linked list
• In between the linked list
• At the end of the linked list

### Insertion Algorithm

#### Algorithm to insert a node at the beginning

• Step 1: Create a node and assign a value to it.
• Step 2: Assign the “prev” reference of head as the new node.
• Step 3: Assign the “next” reference of the node as head.
• Step 4: Set the created node as the new head.
• Step 5: Terminate.

#### Method to insert a node at the beginning

``````#Insertion at the beginning in a Doubly Linked List
class Node:
def __init__(self, value = None):
self.value = value
self.next = None
self.prev = None

def __init__(self):
self.tail = None

#Function to add node in the beginning
def atBeg(self, value):
new_node = Node(value)

#Initially, we have a linked list (1,3,5,7,9) called "dll".
dll.atBeg(0)
print([node.value for node in dll])

#Output
[0, 1, 3, 5, 7, 9]``````

#### Algorithm to insert a node in between the linked list

• Step 1: Create a node and assign a value to it.
• Step 2: If the previous node doesn’t exist, return an error message and move to step 5.
• Step 3: Set the “next” reference of the previous node to the new node and set the “prev” reference of the new node to the previous node.
• Step 4: Set the “next” reference of the new node to the next node and set the “prev” reference of the next node to the new node.
• Step 5: Terminate.

#### Method to insert a node in between the linked list

``````#Insertion in between a Doubly Linked List
#Function to add node in the middle
def inMid(self,prev_node, value):
if prev_node is None:
print("Mentioned node doesn't exist")
return

next_node = prev_node.next
new_node = Node(value)
prev_node.next = new_node
new_node.prev = prev_node
new_node.next = next_node
next_node.prev = new_node

#Initially, we have a linked list (1,3,5,7,9) called "dll" and "prev" node points to the value 3.
dll.inMid(prev, 11)
print([node.value for node in dll])

#Output
[1, 3, 11, 5, 7, 9]``````

#### Algorithm to insert a node at the end of the linked list

• Step 1: Create a node and assign a value to it.
• Step 2: If the list is empty, assign new node to head and tail. Move to step 6.
• Step 3: Search for the last node. Once found, set its “next” reference pointing to the new node.
• Step 4: Set the “prev” reference of the new node to the last node.
• Step 5: Assign the new node as tail.
• Step 6: Terminate.

#### Method to insert a node at the end of the linked list

``````#Insertion at the end in a Doubly Linked List
#Function to add node in the end
def atEnd(self, value):
new_node = Node(value)
self.tail = new_node
return
while(last_node.next is not None):
last_node = last_node.next
last_node.next = new_node
new_node.prev = last_node
self.tail = new_node
#Initially, we have a linked list (1,3,5,7,9) called "dll".
dll.atEnd(0)
print([node.value for node in dll])

#Output
[1, 3, 5, 7, 9, 0]``````

#### Time and Space Complexity

In python, instead of iterating over the linked list and reaching the required position, we can directly jump to any point. Therefore, the time complexity of insertion in a doubly linked list is O(1).

But, for insertion at the end, the time complexity is O(N) as we need to traverse to the last element. The space complexity O(1) because it takes a constant space to add a new node.

### Forward Traversal

A doubly linked list can be traversed in the forward direction by iterating from the first element to the last. We get the value of the next data element by simply iterating with the help of the reference address.

### Forward Traversing Method

``````#Forward Traversal through Doubly Linked List
class Node:
def __init__(self, value = None):
self.value = value
self.next = None
self.prev = None

def __init__(self):
self.tail = None

def printForwardList(self):
print("The linked list does not exist.")
else:
while temp_node:
print(temp_node.value)
temp_node = temp_node.next

#Initially, we have a linked list (1,3,5,7,9) called "dll".
dll.printForwardList()

#Output
1
3
5
7
9``````

### Reverse Traversal

A doubly linked list can be traversed in the reverse direction by iterating from the last element to the first. We get the value of the previous data element by simply iterating with the help of the reference address.

### Reverse Traversing Method

``````#Reverse Traversal through Doubly Linked List
class Node:
def __init__(self, value = None):
self.value = value
self.next = None
self.prev = None

def __init__(self):
self.tail = None

def printReverseList(self):
print("The linked list does not exist.")
else:
temp_node = self.tail
while temp_node:
print(temp_node.value)
temp_node = temp_node.prev

#Initially, we have a linked list (1,3,5,7,9) called "dll".
dll.printReverseList()

#Output
9
7
5
3
1``````

#### Time and Space Complexity

We need to loop over the linked list to traverse and print every element. The time complexity for traversal is O(N) where ‘N’ is the size of the given linked list. The space complexity is O(1) as no additional memory is required to traverse through a doubly linked list.

### Searching in a Doubly Linked List

To find a node in a given doubly linked list, we can use the technique of traversal. The only difference, in this case, is that as soon as we find the searched node, we will terminate the loop.

The worst-case scenario for search is when we have the required element at the end of the linked list, in such a case we have to iterate through the entire linked list to find the required element.

### Searching Algorithm

• Step 1: If the linked list is empty, return the message and move to step 5.
• Step 2: Iterate over the linked list using the reference address for each node.
• Step 3: Search every node for the given value.
• Step 4: If the element is found, break the loop. If not, return the message “Element not found”.
• Step 5: Terminate.

### Searching Method

``````#Searching in a Doubly Linked List
class Node:
def __init__(self, value = None):
self.value = value
self.next = None
self.prev = None

def __init__(self):
self.tail = None

def searchList(self, value):
position = 0
found = 0
print ("The linked list does not exist")
else:
while temp_node is not None:
position = position + 1
if temp_node.value == value:
print ("The required value was found at position: " + str(position))
found = 1
temp_node = temp_node.next
if found == 0:
print ("The required value does not exist in the list")

#Initially, we have a linked list (1,3,5,7,9) called "dll".
print(dll.searchList(7))

#Output
The required value was found at position: 4``````

#### Time and Space Complexity

The time complexity for searching a given element in the linked list is O(N) as we have to loop over all the nodes and check for the required one. The space complexity is O(1) as no additional memory is required to traverse through a doubly linked list and perform a search.

### Deletion of node from Doubly Linked List

To delete an existing node from a doubly linked list, we must know the value that the node holds. For deletion, we first locate the node previous to the given node. Then we point the “next” reference of this node to the next node and the “prev” reference to the previous node.

A node can be deleted from a doubly linked list in any one of the following three ways.

• Deleting the first node
• Deleting any given node
• Deleting the last node

### Deletion Algorithm

#### Algorithm to delete a node from the beginning

• Step 1: If the linked list is empty, return a null statement and go to step 6.
• Step 2: If there’s only one element, delete that node and set head and tail to none. Go to step 6.
• Step 3: Set a “next_node” pointing to the element next to the head node.
• Step 4: Set the “prev” reference of “nex_node” to none.
• Step 5: Assign “next_node” as the new head.
• Step 6: Terminate.

#### Method to delete a node from the beginning

``````#Deletion at the beginning of a Doubly Linked List
class Node:
def __init__(self, value = None):
self.value = value
self.next = None
self.prev = None

def __init__(self):
self.tail = None

#Function to delete node from the beginning
def delBeg(self):
return
return
next_node.prev = None
return

#Initially, we have a linked list (1,3,5,7,9) called "dll".
dll.delBeg()
print([node.value for node in dll])

#Output
[3, 5, 7, 9]``````

#### Algorithm to delete a node from between the linked list

• Step 1: If the linked list is empty, return a null statement and go to step 7.
• Step 2: Create a “temp_node” and set it to the head node. Iterate over the list till the element to be deleted is found.
• Step 3: Set “prev_node” as the element behind the node to be deleted.
• Step 4: Set “next_node” as the element after the node to be deleted.
• Step 5: Assign the “next” reference of “prev_node” to the “next_node”.
• Step 6: Assign the “prev” reference of “next_node” to the “prev_node”.
• Step 7: Terminate.

#### Method to delete a node from between the linked list

``````#Function to delete a node from between the linked list
def delMid(self, del_value):
return
found = False
while (temp_node) :
if(temp_node.value == del_value):
found = True
break
temp_node = temp_node.next
if (found == True):
prev_node = temp_node.prev
next_node = temp_node.next
prev_node.next = next_node
next_node.prev = prev_node
return
else:

#Initially, we have a linked list (1,3,5,7,9) called "dll".
dll.delMid(3)
print([node.value for node in dll])

#Output
[1, 5, 7, 9]``````

#### Algorithm to delete a node from the end

• Step 1: If the linked list is empty, return a null statement and go to step 7.
• Step 2: If there’s only one element, delete that node and set head and tail to none. Go to step 7.
• Step 3: Set a “temp_node” pointing at head. Iterate the linked list till that node points to the second last node of the list.
• Step 4: Assign tail as the temp node. Set temp node to the next node, i.e., last in the list.
• Step 5: Delete the temp_node.
• Step 6: Assign “head” to the “next” reference of the tail.
• Step 7: Terminate.

#### Method to delete a node from the end

``````#Function to delete node from the end
def delEnd(self):
return
return
else:
while (temp_node.next is not self.tail):
temp_node = temp_node.next
self.tail = temp_node
temp_node.next = None
return

#Initially, we have a linked list (1,3,5,7,9) called "dll".
dll.delEnd()
print([node.value for node in dll])

#Output
[1, 3, 5, 7]``````

#### Time and Space Complexity

The time complexity for deletion in a doubly linked list is O(N) as we have to loop over all the nodes and search for the required one. The space complexity is O(1) as no additional memory is required to delete an element from a doubly linked list.

### Deletion of entire Doubly Linked List

The deletion of an entire doubly linked list is quite a simple process. We need to set the previous references of all nodes in the list to none. Then, we have to set the two reference nodes “head” and “tail” to none.

#### Algorithm to delete an entire doubly linked list

• Step 1: If the linked list is empty, return an error message and go to step 5.
• Step 2: Iterate over the linked list and set all the previous references to none.
• Step 3: Delete the “head” node by setting it to none.
• Step 4: Delete the “tail” node by setting it to none.
• Step 5: Terminate.

#### Method to delete an entire doubly linked list

``````#Deletion of an entire Doubly Linked List
class Node:
def __init__(self, value = None):
self.value = value
self.next = None
self.prev = None

def __init__(self):
self.tail = None

def delDLL(self):
print("The doubly linked list does not exist.")
else:
while (temp_node):
temp_node.prev = None
temp_node = temp_node.next