Note: It is important to have knowledge of single linked list before continuing...
Doubly Linked List:
Doubly Linked List is a type of linked list. The single linked list only stores the address of the next node but in the doubly linked list the list stores two addresses one of the previous node and one of the next node. The doubly linked list can be traversed in both directions and insertion and deletion of nodes is easy and simple as compared to single linked list. The implementation of Doubly linked list is as follows
Code:
class Node:
def __init__(self, data):
self.prev = None
self.data = data
self.next = None
Now we will see the operations that we can perform on the double linked list first we will write a traverse method for a doubly linked list that will traverse it in both directions forward and backward.
Code:
def showInfo(self):
temp = self.head
print("Printing in Forward Direction..")
while temp:
print(temp.data, end='\t')
priv = temp
temp = temp.next
print("\nPrinting in reverse Direction..")
while priv:
print(priv.data, end='\t')
priv = priv.prev
First we will go from head node to the last and using the next address and then we will traverse it from last node to first using the previous node address.
So now as we can see how we can traverse a Doubly linked list and now we will learn about the inserting of node in doubly linked list first we will talk about inserting at beginning of list so here is the implementation
Code:
def insert_begin(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
if self.head is not None:
self.head.prev = new_node
self.head = new_node
In this code we created a node and in its next portion we stored the address of first node so that it now becomes the first if the head node was not none means it has some data in it so we will add new node in its previous address portion
Now we will see how can we add a node after a specific node, So here is the implementation
Code:
def insert_after(self, prev_node, new_data):
if prev_node is None:
print("The node does not exist.")
new_node = Node(new_data)
new_node.next = prev_node.next
new_node.prev = prev_node
prev_node.next = new_node
if new_node.next:
new_node.next.prev = new_node
In this we check two conditions, the first one the previous node that we wanted to add a new node after it exists or not. And the second is whether it is the last node or not. If it is the last node, leave it as it is. if it is not then add the reference / address of the new node to the previous address portion of the next node.
Now lastly if we want to append the doubly linked list means if we want to add a node at the last of the node.
Code:
def append(self, new_data):
new_node = Node(new_data)
last = self.head
if last is None:
self.head = new_node
while last.next:
last = last.next
last.next = new_node
new_node.prev = last
Now we will learn how we can delete a specific node from a doubly linked list. As I said before that deletion is easy in doubly linked lists so here is the implementation.
Code:
def delete_node(self, dele):
if self.head is None or dele is None:
return
if self.head == dele:
self.head = dele.next
if dele.prev is not None:
dele.prev.next = dele.next
if dele.next is not None:
dele.next.prev = dele.prev
gc.collect()
Before deletion we want to keep it in mind that we have to import a method called gc (Garbage Collector) . It performs a blocking garbage collection of all generations. All objects, regardless of how long they have been in memory, are considered for collection; however, objects that are referenced in managed code are not collected. Use this method to force the system to try to reclaim the maximum amount of available memory.
So here in last there is the summary of all methods and codes of doubly linked list
Code:
import gc
class Node:
def __init__(self, data):
self.prev = None
self.data = data
self.next = None
class Linkedlist:
def __init__(self):
self.head = None
def showInfo(self):
temp = self.head
print("Printing in Forward Direction..")
while temp:
print(temp.data, end='\t')
priv = temp
temp = temp.next
print("\nPrinting in reverse Direction..")
while priv:
print(priv.data, end='\t')
priv = priv.prev
def inser_begin(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
if self.head is not None:
self.head.prev = new_node
self.head = new_node
def insert_after(self, prev_node, new_data):
if prev_node is None:
print("The node does not exist.")
new_node = Node(new_data)
new_node.next = prev_node.next
new_node.prev = prev_node
prev_node.next = new_node
if new_node.next:
new_node.next.prev = new_node
def append(self, new_data):
new_node = Node(new_data)
last = self.head
if last is None:
self.head = new_node
while last.next:
last = last.next
last.next = new_node
new_node.prev = last
def delete_node(self, dele):
if self.head is None or dele is None:
return
if self.head == dele:
self.head = dele.next
if dele.prev is not None:
dele.prev.next = dele.next
if dele.next is not None:
dele.next.prev = dele.prev
gc.collect()
number = Linkedlist()
number.inser_begin(1)
number.inser_begin(2)
number.inser_begin(3)
number.inser_begin(4)
number.inser_begin(5)
number.insert_after(number.head, 55)
number.append(33)
number.delete_node(number.head.next)
number.showInfo()
That’s it for now see you in next thread.
"Keep Good care of your Health
Allah Hafiz and Good Bye Till the next post"
Love me like you do