This is how it is different than singly linked list
Singly Linked List
Doubly Linked List
So, when creating a node in Singly Linked List, we had this:
We actually had
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:
Will make it
Case 2:
Now we will code this to append a new node
So, the total code is:
The 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
#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:
same for the last node:
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:
We will first do this:
then
then
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
If the index is in 1st half
if on 2nd half
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
else will return False
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
to 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.
this to this
For this, we will just pop
Case 2:
To remove from last.
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
using
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!
Top comments (0)