Guide to Doubly Linked Lists in Data Structure Algorithms
Fatima Jannet
In doubly linked list, each node has to arrows where one points to the next node and the other one points to the previous node.
As you can see from the model, first node's previous reference is None and next reference is pointing to the 2nd node. 2nd node's previous reference is pointing to the 1st node and next reference is pointing to the 3rd node. This backward links improve efficiency in some special cases. However, each node consists of two references, one for the next and another for the previous one.
Remember : The doubly node consists of value, reference to forward & backward.
Code:
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
Append Method
Append means adding in the last. To add, we need to update the tail's next arrow to the new node. Then we have to update new node's previous reference to point to the last node which is self.tail and at the end we have to declare the new node as the tail.
Visualization :
Code :
def append(self, value):
new_node = Node(value)
if self.length == 0:
self.head = self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.length += 1
The time and space complexity for append method is O(N)
str Method
Now we will learn how to do the string representation of the DLL. For this, a temp node is crucial, temp node will only act as an arrow here. Also, we will need to assign a variable where we can put the string value from the node and return the variable at last.
Visualization :
Code :
def __str__(self)
store = ''
temp_node = self.head
if self.length == 0:
return None
else:
while temp_node != self.tail:
store += str(temp_node.value)
if temp_node is not None:
store += "<-->"
temp_node = temp_node.next
return store
Prepend method
Prepending an element means attaching a node in the beginning. We have to update the new node's next reference to self.head along with head's prev reference pointing to the new node. Finally, we have to set the new node as the head.
Visualization :
Code :
def prepend(self, value):
new_node = Node(value)
if self.length == 0:
self.head = self.tail = new_node
else:
self.head.prev = new_node
new_node.next = self.head
self.head = new_node
self.length += 1
The time and space complexity for prepend method is O(N)
Traversing
Traversal means visiting all the element of a linked list one by one. To do the operation, we will make a temporary node that will work as a arrow an will go through the whole list, printing the value until it finds the tail. We will point the temp_node to self.head
Visualization :
Code:
def traversal(self):
temp_node = self.head
while temp_node is not self.tail:
print(temp_node.value)
temp_node = temp_node.next
As there's a while loop, and we know while loop taken O(N) time complexity, so the overall time complexity will be O(N). The space complexity will be O(1) as no additional space is needed to perform this operation.
Reverse Traverse:
The main difference between singly linked list and doubly linked list is - doubly linked list has backward links, which allows reverse traversing.
To reverse traverse, we will assign the temp node to the tail, and we will move it backwards.
Visualization :
Code :
def reverse_traverse(self):
temp_node = self.tail
while temp_node is not None:
print(temp_node.value)
temp_node = temp_node.prev
Time complexity: O(N), Space complexity: O(1)
Search Method:
To search for a specific value, we will go with the head first. If the value is present in head, we return true. If not, we move to the next node and check if the value matches or not. We will take target param here. If we can't find the target value throughout the list, we return false.
Visualization :
Code :
def search(self, target):
if self.length == 0:
return None
else:
temp_node = self.head
while temp_node: #is not none
if temp_node == target:
return True
break
temp_node = temp_node.next
return False
Time complexity : O(N), Space complexity : O(1)
Get Method
We know that, we use get() using index, and printing the value of the given index. It is going to be different this time. To optimize, if the index is located in the first half, we will start from self.head and if it's located in the second half, we will start from self.tail. It is going to optimize the number of operations in DLL. As we have the opportunity to moving backwards, why not use it?
Visualization :
Code :
def get(self, index):
if index < 0 or index >= self.length:
return None
if index < self.length // 2:
temp_node = self.head
for _ in range(index): #------- O(N/2)
temp_node = temp_node.next
else:
temp_node = self.tail
for _ in range(self.length - 1, index, -1): #------- O(N/2)
temp_node = temp_node.prev
return temp_node
Time complexity: O(N), Space complexity : O(1). Although it takes O(N) times complexity, it's still faster than the linear search.
Set method
We will set two params for set method - index, value (we want to change). Set method will access the node of the given index and change the value with the provide value.
This is going to be a very easy code if we use get() inside it.
Code :
def set_value(self, index, value)
node = self.get(index)
if node:
node.value = value
return True
return False
Time complexity : O(N), Space Complexity : O(1)
Insert Method:
Adding a new node wherever we want. We will take two params here - index, value. Then we will assign the temp node right before the node we are going to change value of.
Visualization :
Code :
def insert(self, index, value):
if index < 0 or index > self.length:
return None
if index == 0:
self.prepend(value)
return
elif index == self.length:
self.append(value)
return
new_node = Node(value)
temp_node = get(index-1)
new_node.next = temp_node.next
new_node.prev = temp_node
temp_node.next.prev = new_node
temp_node.next = new_node
self.length += 1
temp_node.next.prev = new_node means previous reference of the node, which is located after the temp node.
Time complexity : O(N), Space complexity : O(1)
Pop first method :
This method will detach the first node from the list and returns the element. First, we will make a pointer. Then we gonna move head to the next node. Then we will update the first node's next reference to none and current head's prev reference to none. Lastly, we will reduce the length by 1.
Code:
def pop_first(self):
if self.length == 0:
self.head = self.tail = None
else:
popped_node = self.head
self.head = self.head.next
self.head.prev = None
popped_node.next = None
self.length -= 1
return popped_node
Time complexity : O(1), Space complexity : O(1)
Pop method:
We will remove the last element and return it. We will set the pop_last to the tail.
Code:
def pop_last(self):
pop_last = self.tail
if self.length == 0:
return None
if self.length == 1:
self.tail = self.head = None
return pop_last
else:
self.tail = self.tail.prev
self.tail.next = None
pop_last.prev = None
self.length -= 1
return pop_last
Time complexity : O(1), Space complexity : O(1)
Remove Method
Remove works based on the index. We will update the :
popped node's previous node's next reference -> popped node's next node
popped node's nest reference's previous node -> popped node's previous node
popped node's next and previous reference -> None
Visualization:
Code:
def remove(self, index)
popped_node = self.get(index)
if index < 0 or index >= self.length
return None
if self.length == 0:
return self.pop_first()
if index == -1:
return self.pop_last()
else:
popped_node.prev.next = popped_node.next
popped_node.next.prev = popped_node.prev
popped_node.next = popped_node.prev = None
return popped_node
self.length -= 1
Time complexity : O(N), Space complexity : O(1)
The whole Code:
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
def __str__(self):
return str(self.value
return f"{self.prev} <- {self.value} -> {self.next}"
def append(self, value):
new_node = Node(value)
if self.length == 0:
self.head = self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.length += 1
def prepend(self, value):
new_node = Node(value)
if self.length == 0:
self.head = self.tail = new_node
else:
self.head.prev = new_node
new_node.next = self.head
self.head = new_node
self.length += 1
def traversal(self):
temp_node = self.head
while temp_node is not self.tail:
print(temp_node.value)
temp_node = temp_node.next
def reverse_traverse(self):
temp_node = self.tail
while temp_node is not None:
print(temp_node.value)
temp_node = temp_node.prev
def search(self, target):
if self.length == 0:
return None
else:
temp_node = self.head
while temp_node: #is not none
if temp_node == target:
return True
break
temp_node = temp_node.next
return False
def get(self, index):
if index < 0 or index >= self.length:
return None
if index < self.length // 2:
temp_node = self.head
for _ in range(index):
temp_node = temp_node.next
else:
temp_node = self.tail
for _ in range(self.length - 1, index, -1):
temp_node = temp_node.prev
return temp_node
def set_value(self, index, value)
node = self.get(index)
if node:
node.value = value
return True
return False
def insert(self, index, value):
if index < 0 or index > self.length:
return None
if index == 0:
self.prepend(value)
return
elif index == self.length:
self.append(value)
return
new_node = Node(value)
temp_node = get(index-1)
new_node.next = temp_node.next
new_node.prev = temp_node
temp_node.next.prev = new_node
temp_node.next = new_node
self.length += 1
def pop_first(self):
if self.length == 0:
self.head = self.tail = None
else:
popped_node = self.head
self.head = self.head.next
self.head.prev = None
popped_node.next = None
self.length -= 1
return popped_node
def pop_last(self):
pop_last = self.tail
if self.length == 0:
return None
if self.length == 1:
self.tail = self.head = None
return pop_last
else:
self.tail = self.tail.prev
self.tail.next = None
pop_last.prev = None
self.length -= 1
return pop_last
def remove(self, index)
popped_node = self.get(index)
if index < 0 or index >= self.length
return None
if self.length == 0:
return self.pop_first()
if index == -1:
return self.pop_last()
else:
popped_node.prev.next = popped_node.next
popped_node.next.prev = popped_node.prev
popped_node.next = popped_node.prev = None
return popped_node
self.length -= 1
Subscribe to my newsletter
Read articles from Fatima Jannet directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by