Doubly Linked List in Python - Advanced Data Structure

Hello programmers, you will get insights into everything you need about the doubly linked list in Python in this article. We will discuss what doubly linked lists are 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 a doubly linked list is and where they are important.

Contents

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 refers to the data of that particular node.

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 the next pointer of the last node point to NULL.

Use of Doubly Linked List in Python: Doubly linked lists are very helpful for both front and back navigation. It allows the 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 more 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 detail about Doubly Linked list in Python are :

Create and Display a Doubly Linked List in Python
Delete items from the Doubly Linked List
Traversing through Doubly Linked List
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, a 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.

Deleting 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: First, the code checks whether the list has one element or is 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 a 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’s 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 similar to traversing 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 of 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 to None because the first node becomes the last node in the reversed list. The last node’s previous reference should also be 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 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 that 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 adding and deleting new components quite simple without keeping tabs on their previous and next nodes.

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