What’s New ?

The Top 10 favtutor Features You Might Have Overlooked

Read More

Doubly Linked List (Python Code with Example)

  • May 21, 2021
  • 7 Minutes Read
Doubly Linked List (Python Code with Example)

Ctrl+Z, can you even survive a day without these keys? Well, Apparently not, undo and redo features are one of the used functionalities in computer engineering. But have you ever thought about how is it even possible? I happen to have an answer this time! Undo and Redo functionality is one of the most important applications of a doubly linked list. So what exactly is a doubly linked list? Before that let’s have a quick glance at Linked List: 

What is Linked List?

Linked list is a linear data structure in which each node is an object. Different from general Arrays, the Linked list data structure does not have a contiguous memory structure. Every element is connected to the subsequent node through a pointer.

Every element present in the Linked list is known as Node. Every node contains a key or data element with an extra pointer pointing to the next element in the list. The initial pointer in the  Linked list is called Head. It is necessary to state that “Head” pointer is not another node but a pointer to the first element of the Linked list. If the Linked list are empty value of Head will be null.

linked list example

Basic implementation of Linked List in Python is: 

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextvnextal = None
 
class LinkedList:
    def __init__(self):
        self.headval = None
 
example = LinkedList()
example.headval = Node(23)
e2 = Node(90)
e3 = Node(90)
# Link first Node to second node
example.headval.nextval = e2
 
# Link second Node to third node
e2.nextval = e3

 

What is Doubly Linked List ?

It is easier to implement Singly Linked list or Linked list,whereas it is pretty difficult to traverse that in reverse, to overcome this we can utilise Doubly LinkedList, where every node takes an additional pointer to point the former node to the element in addition to the pointer for the next node.

A doubly linked list has more efficient iteration, particularly if you need to ever iterate in reverse and more efficient deletion of particular nodes.

We can conclude that a doubly linked list is a complex type of linked list where a node contains a pointer to the previous as well as the next node in the sequence. Therefore, in a doubly-linked list, a node consists of three components: node data, pointer to the next node in node(next pointer), pointer to the former node (previous pointer).

 

doubly linked list

Example

For example, consider a doubly linked list containing four nodes having, four numbers from 1 to 4 in their data part, illustrated in the following image

doubly linked list python

Step-by-Step Implementation of Doubly Linked List in Python

We will implement doubly linked list using some concepts of object oriented programming in python. We will first create a class for creating a node in a basic linked list, with three attributes: the data, previous pointer and next pointer. The code looks like this:

class Node:
    def __init__(self, data):
        self.item = data
        self.next = None
        self.prev = None

 

The item variable will store the actual element of the node. The next stores the address to the next node, while prev stores the address to the previous node in the doubly linked list.

In the next step, we will create a doublyLinkedList class, that contains different functions to insert, delete and display elements of doubly linked list.

class doublyLinkedList:
    def __init__(self):
        self.start_node = None

 

We add the following functionalities to the doublyLinkedList class. We add these functions to the class.

  1. Inserting Items to Empty List
  2. Inserting Items at the End
  3. Deleting Elements from the Start
  4. Deleting Elements from the End
  5. Traversing the Linked List

Inserting Items to Empty List

The most permissive way to insert an element in a doubly linked list is to insert the element in the empty list. The following piece of code enters an element at the origin of the doubly linked list:

    def InsertToEmptyList(self, data):
        if self.start_node is None:
            new_node = Node(data)
            self.start_node = new_node
        else:
            print("The list is empty")

 

Inserting Items at the End

Inserting an element at the end of the doubly linked list is slightly alike to inserting an element at the start of the list. Before entering the elements, we need to verify and check if the doubly linked list is empty. If the list is empty then we can easily use the function InsertToEmptyList() method to insert the element to the list. If the list already has added element, we iterate through the list till the address to the next node reaches NULL. When the next node address becomes NULL, it denotes that the current node is the last node.

The previous reference for the new node is set to the last node, and the next address for the last node is assigned to the newly inserted node. The function for inserting an item at the last node is as follows:

    # Insert element at the end
    def InsertToEnd(self, data):
        # Check if the list is empty
        if self.start_node is None:
            new_node = Node(data)
            self.start_node = new_node
            return
        n = self.start_node
        # Iterate till the next reaches NULL
        while n.next is not None:
            n = n.next
        new_node = Node(data)
        n.next = new_node
        new_node.prev = n

 

Deleting Elements from the Start

The most natural way to delete an element from a doubly linked list is deleting from the start of the list. In order to achieve this, we will assign the value of the start node to the next node and then assign the previous address of the start node to NULL. But before doing this, we need to check two things. First, we need to check if the list is empty. And then we have to verify if the list has only one node or not. If the list has only one element then we can easily assign the start node to NULL. The following code can be utilised to delete node from the start of the doubly linked list.

 

    # Delete the elements from the start
    def DeleteAtStart(self):
        if self.start_node is None:
            print("The Linked list is empty, no element to delete")
            return 
        if self.start_node.next is None:
            self.start_node = None
            return
        self.start_node = self.start_node.next
        self.start_prev = None;

 

Deleting Elements from the End

To remove the element from the end, we have to again verify if the list is empty or if the list has a single element. If the list has a single element, we will assign the start node to NULL. If the doubly linked list has more than one element, we traverse through the list until the last node reaches NULL. Once we reach the last node, we assign the next address of the node previous to the last node, to NULL which actually deletes the last node. The following function can be used to delete the element from the end of the list.

 

    # Delete the elements from the end
    def delete_at_end(self):
        # Check if the List is empty
        if self.start_node is None:
            print("The Linked list is empty, no element to delete")
            return 
        if self.start_node.next is None:
            self.start_node = None
            return
        n = self.start_node
        while n.next is not None:
            n = n.next
        n.prev.next = None

 

Traversing the Linked List

Display the elements in the doubly linked list, while iterating through each element.

 

    # Traversing and Displaying each element of the list
    def Display(self):
        if self.start_node is None:
            print("The list is empty")
            return
        else:
            n = self.start_node
            while n is not None:
                print("Element is: ", n.item)
                n = n.next
        print("\n")

 

Complete python code of Doubly Linked List

 

# Initialise the Node
class Node:
    def __init__(self, data):
        self.item = data
        self.next = None
        self.prev = None
# Class for doubly Linked List
class doublyLinkedList:
    def __init__(self):
        self.start_node = None
    # Insert Element to Empty list
    def InsertToEmptyList(self, data):
        if self.start_node is None:
            new_node = Node(data)
            self.start_node = new_node
        else:
            print("The list is empty")
    # Insert element at the end
    def InsertToEnd(self, data):
        # Check if the list is empty
        if self.start_node is None:
            new_node = Node(data)
            self.start_node = new_node
            return
        n = self.start_node
        # Iterate till the next reaches NULL
        while n.next is not None:
            n = n.next
        new_node = Node(data)
        n.next = new_node
        new_node.prev = n
    # Delete the elements from the start
    def DeleteAtStart(self):
        if self.start_node is None:
            print("The Linked list is empty, no element to delete")
            return 
        if self.start_node.next is None:
            self.start_node = None
            return
        self.start_node = self.start_node.next
        self.start_prev = None;
    # Delete the elements from the end
    def delete_at_end(self):
        # Check if the List is empty
        if self.start_node is None:
            print("The Linked list is empty, no element to delete")
            return 
        if self.start_node.next is None:
            self.start_node = None
            return
        n = self.start_node
        while n.next is not None:
            n = n.next
        n.prev.next = None
    # Traversing and Displaying each element of the list
    def Display(self):
        if self.start_node is None:
            print("The list is empty")
            return
        else:
            n = self.start_node
            while n is not None:
                print("Element is: ", n.item)
                n = n.next
        print("\n")
# Create a new Doubly Linked List
NewDoublyLinkedList = doublyLinkedList()
# Insert the element to empty list
NewDoublyLinkedList.InsertToEmptyList(10)
# Insert the element at the end
NewDoublyLinkedList.InsertToEnd(20)
NewDoublyLinkedList.InsertToEnd(30)
NewDoublyLinkedList.InsertToEnd(40)
NewDoublyLinkedList.InsertToEnd(50)
NewDoublyLinkedList.InsertToEnd(60)
# Display Data
NewDoublyLinkedList.Display()
# Delete elements from start
NewDoublyLinkedList.DeleteAtStart()
# Delete elements from end
NewDoublyLinkedList.DeleteAtStart()
# Display Data
NewDoublyLinkedList.Display()

 

Applications

  • A music player that has next and previous buttons, like the concept of doubly linked list you’ll have functionality to go back and the next element. .
  • Undo Redo operations that we discussed at the beginning of the article.
  • The browser cache functionality in common web browsers like Chrome, Microsoft edge, which allows us to move front and back within pages is also a great application of a doubly linked list.
  • LRU cache, also Most Recently Used is also an instance of DLL.
  • A deck of cards in a game is a perfect example of the applicability of DLL. It is additionally utilized to store the state of the game during play. 

Conclusions 

In this article, we learned about doubly linked lists and their implementation using python with step-by-step explanation. We also discussed various applications of doubly linked lists. 

FavTutor - 24x7 Live Coding Help from Expert Tutors!

About The Author
Apurva Sharma
Hi, I am Apurva Sharma, a data science engineer, deep learning evangelist and DevOps enthusiast