Discord Server Red Security Twitter Donation to Red Security Red Security Youtube Channel Red Security Tumblr Profile
Login or Register to Hide ads and Accessing all features on the forum

Tutorial 

Doubly Linked List in Python

0 Replies, 2179 Views

[Image: BFMMlbcQvml9HSqXcvNp]

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

[Image: doubly-linked-list-1.png]

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 Heart

Possibly Related Threads…
Thread Author Replies Views Last Post
  Tutorial Linked List in Python Covid-19 2 2,535 07-30-2022, 08:25 PM
Last Post: Covid-19
  Tutorial File Handling in Python Covid-19 2 2,569 06-16-2022, 06:17 PM
Last Post: Covid-19
  Tutorial Exceptions in Python Covid-19 0 1,776 06-08-2022, 09:19 PM
Last Post: Covid-19
  Free Automate the boring stuff with Python Covid-19 0 1,541 06-07-2022, 06:58 PM
Last Post: Covid-19
  Tutorial Turtle in Python Covid-19 0 1,773 06-02-2022, 10:14 PM
Last Post: Covid-19
  Tutorial Python 3.5: Class Methods Covid-19 0 1,725 05-29-2022, 01:07 PM
Last Post: Covid-19
  Tutorial Python 3.2: Inheritance in Python Covid-19 2 2,738 05-27-2022, 06:47 PM
Last Post: Covid-19
  Tutorial Python 3.4: Encapsulation and Abstraction Covid-19 0 1,757 05-27-2022, 06:45 PM
Last Post: Covid-19
  Tutorial Python 3.3: Operator Overloading Covid-19 2 2,728 05-26-2022, 08:50 PM
Last Post: Covid-19
  Tutorial Python 3.1: OOP Covid-19 2 1,559 05-24-2022, 06:37 PM
Last Post: Covid-19



Users browsing this thread: 1 Guest(s)