This is how it is different than singly linked list
Singly Linked List
So, when creating a node in Singly Linked List, we had this:
Which we wrote in class as this:
B
But the doubly Linked List, we will have :
Now, lets create Doubly Linked List class
We will create the Doubly Linked List calling the class:
This makes a doubly Linked List:
the whole code:
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self, value):
new_node = Node(value)
self.head = new_node
self.tail = new_node
self.length = 1
def print_list(self):
temp = self.head
while temp is not None:
print(temp.value)
temp = temp.next
#Creating a doubly Linked List which has a node 7
my_doubly_linked_list = DoublyLinkedList(7)
#Printing the list
my_doubly_linked_list.print_list()
Append
Case 1:
When there is no value and adding one
and make this to this
We will first check if head is point to None:
Now we will code this to append a new node
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self, value):
new_node = Node(value)
self.head = new_node
self.tail = new_node
self.length = 1
def print_list(self):
temp = self.head
while temp is not None:
print(temp.value)
temp = temp.next
def append(self, value):
new_node = Node(value)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.length += 1
return True
#A linked list of a node 1
my_doubly_linked_list = DoublyLinkedList(1)
#Appending node 2
my_doubly_linked_list.append(2)
my_doubly_linked_list.print_list()
Pop
Case 1:
If the List has 0 nodes
For this , we will have:
Because we won't return anything
Case 2: If we have more than 2 value
First we will create a temp variable
Then we will set tail to the previous node:
Then we will set the tail's next direction to None to break if from the last item:
Case 3:
When we have just 1 value:
We will pop it and also set the head and tail to None:
The list will be something like this:
So, the code will look like this:
Also , we can change it to this format:
Total code:
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self, value):
new_node = Node(value)
self.head = new_node
self.tail = new_node
self.length = 1
def print_list(self):
temp = self.head
while temp is not None:
print(temp.value)
temp = temp.next
def append(self, value):
new_node = Node(value)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.length += 1
return True
def pop(self):
#For 0 items in list
if self.length == 0:
return None
temp = self.tail
#For 1 items in list
if self.length == 1:
self.head = None
self.tail = None
#For more than 1 nodes in list
else:
self.tail = self.tail.prev
self.tail.next = None
temp.prev = None
self.length -= 1
return temp
#Creates a list of Node 1 & Node 2
my_doubly_linked_list = DoublyLinkedList(1)
my_doubly_linked_list.append(2)
# (2) Items - Returns Node 2
print(my_doubly_linked_list.pop())
# (1) Item - Returns Node 1
print(my_doubly_linked_list.pop())
# (0) Items - Returns None
print(my_doubly_linked_list.pop())
Prepend
Case: 1
When we have nothing in the list
So, we will set the head & tail to it:
Case 2:
if we have more than 1 values:
Total code becomes:
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self, value):
new_node = Node(value)
self.head = new_node
self.tail = new_node
self.length = 1
def print_list(self):
temp = self.head
while temp is not None:
print(temp.value)
temp = temp.next
def append(self, value):
new_node = Node(value)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.length += 1
return True
def pop(self):
if self.length == 0:
return None
temp = self.tail
if self.length == 1:
self.head = None
self.tail = None
else:
self.tail = self.tail.prev
self.tail.next = None
temp.prev = None
self.length -= 1
return temp
def prepend(self, value):
new_node = Node(value)
# If we have no value in the list
if self.length == 0:
self.head = new_node
self.tail = new_node
#If we have more than 1 values
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
self.length += 1
return True
#Doubly list with Node 1 & Node 3
my_doubly_linked_list = DoublyLinkedList(2)
my_doubly_linked_list.append(3)
#Prepending Node 1
my_doubly_linked_list.prepend(1)
my_doubly_linked_list.print_list()
Get
For the Singly Linked List we had this code right:
We will then turn this to this
Case 1:
Let's return something that is within the Doubly Linked List. Let's return index 1
S
setting tail as temp and iterate backward
and return the temp when we get that
So, the total code will be
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self, value):
new_node = Node(value)
self.head = new_node
self.tail = new_node
self.length = 1
def print_list(self):
temp = self.head
while temp is not None:
print(temp.value)
temp = temp.next
def append(self, value):
new_node = Node(value)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.length += 1
return True
def pop(self):
if self.length == 0:
return None
temp = self.tail
if self.length == 1:
self.head = None
self.tail = None
else:
self.tail = self.tail.prev
self.tail.next = None
temp.prev = None
self.length -= 1
return temp
def prepend(self, value):
new_node = Node(value)
if self.length == 0:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
self.length += 1
return True
def pop_first(self):
if self.length == 0:
return None
temp = self.head
if self.length == 1:
self.head = None
self.tail = None
else:
self.head = self.head.next
self.head.prev = None
temp.next = None
self.length -= 1
return temp
def get(self, index):
if index < 0 or index >= self.length:
return None
temp = self.head
#Checking if the index is in 1st half
if index < self.length/2:
for _ in range(index):
temp = temp.next
#Checking if the index is in 2nd half
else:
temp = self.tail
for _ in range(self.length - 1, index, -1):
temp = temp.prev
return temp #Will return the node . But for value, use temp.value
#Creating a doubly list of 0,5,9,3
my_doubly_linked_list = DoublyLinkedList(0)
my_doubly_linked_list.append(5)
my_doubly_linked_list.append(9)
my_doubly_linked_list.append(3)
#Lokking for index 1 no node
print(my_doubly_linked_list.get(1))
#Looking for index 2 no node
print(my_doubly_linked_list.get(2))
Set
Let's set this index 1 value from 3 to 4.
so,here we are going to check if the index is within range and if so, then we will change the value
The whole code is
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self, value):
new_node = Node(value)
self.head = new_node
self.tail = new_node
self.length = 1
def print_list(self):
temp = self.head
while temp is not None:
print(temp.value)
temp = temp.next
def append(self, value):
new_node = Node(value)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.length += 1
return True
def pop(self):
if self.length == 0:
return None
temp = self.tail
if self.length == 1:
self.head = None
self.tail = None
else:
self.tail = self.tail.prev
self.tail.next = None
temp.prev = None
self.length -= 1
return temp
def prepend(self, value):
new_node = Node(value)
if self.length == 0:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
self.length += 1
return True
def pop_first(self):
if self.length == 0:
return None
temp = self.head
if self.length == 1:
self.head = None
self.tail = None
else:
self.head = self.head.next
self.head.prev = None
temp.next = None
self.length -= 1
return temp
def get(self, index):
if index < 0 or index >= self.length:
return None
temp = self.head
if index < self.length/2:
for _ in range(index):
temp = temp.next
else:
temp = self.tail
for _ in range(self.length - 1, index, -1):
temp = temp.prev
return temp
def set_value(self, index, value):
temp = self.get(index)
#if the index is within the range
if temp:
temp.value = value
return True
#if the index is not within range
return False
#Doubly linked list of 11,3,23,7
my_doubly_linked_list = DoublyLinkedList(11)
my_doubly_linked_list.append(3)
my_doubly_linked_list.append(23)
my_doubly_linked_list.append(7)
#setting index value to 4
my_doubly_linked_list.set_value(1,4)
my_doubly_linked_list.print_list()
Insert
At a particular index, we are going to insert a node.
Firstly, we are going to check if the index is within the range
Case 1:
If needs to add it at the beginning
Case 2:
Adding it to the last of the list
case 3:
Adding in somewhere middle.
Assume that we want to make this
to that
so, trying to insert the node between 1 & 2.
So, we will set index 1 to before and index 2 to after
We are going to make this
So, the code is
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self, value):
new_node = Node(value)
self.head = new_node
self.tail = new_node
self.length = 1
def print_list(self):
temp = self.head
while temp is not None:
print(temp.value)
temp = temp.next
def append(self, value):
new_node = Node(value)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.length += 1
return True
def pop(self):
if self.length == 0:
return None
temp = self.tail
if self.length == 1:
self.head = None
self.tail = None
else:
self.tail = self.tail.prev
self.tail.next = None
temp.prev = None
self.length -= 1
return temp
def prepend(self, value):
new_node = Node(value)
if self.length == 0:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
self.length += 1
return True
def pop_first(self):
if self.length == 0:
return None
temp = self.head
if self.length == 1:
self.head = None
self.tail = None
else:
self.head = self.head.next
self.head.prev = None
temp.next = None
self.length -= 1
return temp
def get(self, index):
if index < 0 or index >= self.length:
return None
temp = self.head
if index < self.length/2:
for _ in range(index):
temp = temp.next
else:
temp = self.tail
for _ in range(self.length - 1, index, -1):
temp = temp.prev
return temp
def set_value(self, index, value):
temp = self.get(index)
if temp:
temp.value = value
return True
return False
def insert(self, index, value):
#to check if the index is within range
if index < 0 or index > self.length:
return False
#to add a node at the start
if index == 0:
return self.prepend(value)
#to add a node at the end
if index == self.length:
return self.append(value)
#to add a node within the list
new_node = Node(value)
before = self.get(index - 1)
after = before.next
new_node.prev = before
new_node.next = after
before.next = new_node
after.prev = new_node
self.length += 1
return True
#Doubly linked list of nodes 1 ,3
my_doubly_linked_list = DoublyLinkedList(1)
my_doubly_linked_list.append(3)
#at the index 1, adding node 2
my_doubly_linked_list.insert(1,2)
my_doubly_linked_list.print_list()
Remove
Checking if the index is out of range
Case 1:
Returning the first item.
Case 3:
To remove something from middle
For example, we will remove the index 2 number value. Firstly, pointing a variable to it
Which can be something like this
Total code will be
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self, value):
new_node = Node(value)
self.head = new_node
self.tail = new_node
self.length = 1
def print_list(self):
temp = self.head
while temp is not None:
print(temp.value)
temp = temp.next
def append(self, value):
new_node = Node(value)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.length += 1
return True
def pop(self):
if self.length == 0:
return None
temp = self.tail
if self.length == 1:
self.head = None
self.tail = None
else:
self.tail = self.tail.prev
self.tail.next = None
temp.prev = None
self.length -= 1
return temp
def prepend(self, value):
new_node = Node(value)
if self.length == 0:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
self.length += 1
return True
def pop_first(self):
if self.length == 0:
return None
temp = self.head
if self.length == 1:
self.head = None
self.tail = None
else:
self.head = self.head.next
self.head.prev = None
temp.next = None
self.length -= 1
return temp
def get(self, index):
if index < 0 or index >= self.length:
return None
temp = self.head
if index < self.length/2:
for _ in range(index):
temp = temp.next
else:
temp = self.tail
for _ in range(self.length - 1, index, -1):
temp = temp.prev
return temp
def set_value(self, index, value):
temp = self.get(index)
if temp:
temp.value = value
return True
return False
def insert(self, index, value):
if index < 0 or index > self.length:
return False
if index == 0:
return self.prepend(value)
if index == self.length:
return self.append(value)
new_node = Node(value)
before = self.get(index - 1)
after = before.next
new_node.prev = before
new_node.next = after
before.next = new_node
after.prev = new_node
self.length += 1
return True
def remove(self, index):
#Checking the range
if index < 0 or index >= self.length:
return None
#to remove from the beginning
if index == 0:
return self.pop_first()
#to remove from the last
if index == self.length - 1:
return self.pop()
#to remove from the middle of the doubly linked list
temp = self.get(index)
temp.next.prev = temp.prev
temp.prev.next = temp.next
temp.next = None
temp.prev = None
self.length -= 1
return temp
# a doubly linked list of 0,1 & 2 nodes
my_doubly_linked_list = DoublyLinkedList(0)
my_doubly_linked_list.append(1)
my_doubly_linked_list.append(2)
# removing index 1 out of the list
print(my_doubly_linked_list.remove(1), '\n')
my_doubly_linked_list.print_list()
Done!