Doubly Linked List in Python – Advanced Data Structure

Hello programmers, you will get insights into all that you need to know about the doubly linked list in Python in this article. We will discuss what doubly linked list is and where they are used in python programming. We will also look at creating a doubly linked list in python and performing various operations on it. So without any further delay, let’s begin with the topic.

Before we understand the creation and operations performed over the doubly linked list in python, Let me brief you about what is a doubly linked list and where they are important.

What is a Doubly Linked List in Python?

A doubly linked list in Python is a linked data structure with a set of sequentially linked nodes. Each node has three fields – two link fields, which are references to the previous and next node’s address in the sequence. In addition, one data field referring to the data of that particular node.

Doubly linked list

Data Part: stores the data.

Prev Part: stores the address of the previous node.

Next Part: stores the address of the next node.

Since there is no node before the first node and after the last node, the prev pointer of the first node and next pointer of the last node points to NULL.

Use of Doubly Linked List used in python: Doubly linked lists are very helpful where both front and back navigation is required. It allows traversal of the list in either direction. A doubly linked list requires changing more links than a singly linked list while adding or removing nodes. But, the operations are potentially simpler and efficient as it does not require keeping track of the previous node, unlike the singly linked list. It has various applications to implement Undo and Redo functions.

Things we will learn in details about Doubly Linked list in Python are :

  1. Create and Display a Doubly Linked List in python
  2. Delete items from the Doubly Linked List
  3. Traversing through Doubly Linked List
  4. Reversing a Doubly Linked List

Create and display a Doubly Linked List in Python:

Example to Create a Double Linked List

class Node:    
    def __init__(self,data):    
        self.data = data;    
        self.nref = None;    
        self.pref = None;    
            
class DoublyLinkedList:    
    def __init__(self):    
        self.head = None;    
        self.tail = None;    
            
    def addNode(self, data):    
        newNode = Node(data);    
            
        if(self.head == None):    
            self.head = self.tail = newNode;    
            self.head.nref = None;    
            self.tail.pref = None;    
        else:    
            self.tail.next = newNode;    
            newNode.nref = self.tail;    
            self.tail = newNode;    
            self.tail.pref = None;    
                
    def display(self):    
        current = self.head;    
        if(self.head == None):    
            print("List is empty");    
            return;    
        print("Nodes of doubly linked list: ");    
        while(current != None):     
            print(current.data),;    
            current = current.next;    
                
dList = DoublyLinkedList();    
dList.addNode(1);    
dList.addNode(2);    
dList.addNode(3);    
dList.addNode(4);    
dList.addNode(5);    
     
dList.display();

Output:

Nodes of doubly linked list:  1 2 3 4 5

Explanation:

Creating a doubly-linked list:- In this example, we define a class with three member variables: data, nref, and pref. The data variable will store the data for the node. The nref holds the reference to the next node, while pref holds the reference to the previous node in the doubly linked list. Then a DoublyLinkedList class containing different doubly linked list related functions is created. The two nodes of the doubly linked list class initially point to null.

Inserting Nodes to a doubly-linked list:- The addNode() function adds new nodes to the list. Firstly, it checks if the head is null; it inserts the node as the head. If the head is not null, new node attaches to the end of the list. Lastly, the new node’s previous pointer now points to the tail, and the new node itself becomes the tail.

Display a doubly-linked list: display() function shows all the nodes present in the list. The new node ‘current’ points to the head. All the nodes are printed till the current data points to null. In each iteration, the current will point to the next node.

Deleteing items from the Doubly Linked List:

Deleting Items from the start:

 def delete_at_start(self):
        if self.start_node is None:
            print("The list has no element to delete")
            return 
        if self.start_node.nref is None:
            self.start_node = None
            return
        self.start_node = self.start_node.nref
        self.start_pref = None;

Delete Items from the end:

     def delete_at_end(self):
        if self.start_node is None:
            print("The list has no element to delete")
            return 
        if self.start_node.nref is None:
            self.start_node = None
            return
        n = self.start_node
        while n.nref is not None:
            n = n.nref
        n.pref.nref = None

Explanation:

Deleting from first: At first, the code checks whether the list has one element or it’s empty. If it has only a single element, it is deleted by setting the previous reference of that node to None. In the case of the list which has multiple elements, then the value of the start node is set to the next node, and then the previous reference of the start node is set to None.

Deleting from the end: Just like for deleting an element from the first, the list is first if it is empty or contains a single element. In the case of a single node, the start node is just set to None. If the list has multiple elements, the list is iterated till the last node is reached. Then the next reference of the node previous node is None, which basically removes the last node.

Traversing through Doubly Linked List :

Example for Traversing a Doubly Linked List:

def traverse_list(self):
        if self.start_node is None:
            print("List has no element")
            return
        else:
            n = self.start_node
            while n is not None:
                print(n.data , " ")
                n = n.nref

Explanation:

Traversing a doubly linked list is quite similar to that of tarversing a singly linked list. The traverse_list() function is added to the DoubleLinkedList class added earlier. The function first checks if the list is empty. If not, it prints the data of all nodes while traversing the list.

Reversing a Doubly Linked List :

Example to Reverse a Doubly Linked List

def reverse_linked_list(self):
        if self.start_node is None:
            print("The list has no element to delete")
            return 
        p = self.start_node
        q = p.nref
        p.nref = None
        p.pref = q
        while q is not None:
            q.pref = q.nref
            q.nref = p
            p = q
            q = q.pref
        self.start_node = p

Explanation:

In the above example, the next reference of the start node is set none because the first node becomes the last node in the reversed list. The previous reference of the last node should is also set to None since it becomes the previous node. Lastly, The next references of all the other nodes in the original list are swapped with the previous references.

Pros and Cons of a Doubly Linked List in Python

Pros

  • Unlike one linked list, the doubly linked list may be traversed and hunted in the two directions. The reference to another node aids in exposing the node from the forward direction while the references to the prior nodes permit traversal from the backward direction.
  • We can easily add a new node prior to a specified node.
  • We don’t have to traverse into the predecessor node and save its own reference. Instead, at a doubly-linked listing, the mention of the predecessor node could be recovered from the node which we would like to delete.

Cons

  • A doubly linked list requires more distance for each node because one additional field is obligatory for the pointer to the preceding node.
  • It takes more room for each node because one additional field is obligatory for the pointer to the preceding node.

Must Read

Conclusion

The doubly linked list in Python is very useful especially once you need to perform a lot of inserts and delete operations. The hyperlinks to the previous and following nodes make it quite simple to add and delete new components without keeping tabs on their previous and next nodes.

In this guide, we saw how a doubly linked list could be implemented with Python.

0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments