Doubly Linked List with Python Examples

Introduction

This is the third article in the series of articles on implementing linked lists with Python. In part 1 and part 2 of the series, we studied single linked list in detail.

In this article, we will start our discussion about doubly linked lists, which are actually an extension of single-linked lists.

In a single linked list, each node of the list has two components, the actual value of the node and the reference to the next node in the linked list. In the doubly linked list, each node has three components: the value of the node, the reference to the previous node, and the reference to the next node. For the start node of the doubly linked list, the reference to the previous node is null (None in Python). Similarly, for the last node in the doubly linked list, the reference to the next node is null.

Pros and Cons of a Doubly Linked List

First of all, let's discuss about advantages and disadvantages of using doubly linked lists over single linked lists in Python.

Pros

• Unlike a single linked list, the doubly linked list can be traversed and searched in both directions. The reference to the next node helps in traversing the node in the forward direction while the references to the previous nodes allow traversal in the backward direction.
• Basic operations such as insertion and deletion are easier to implement in the doubly linked lists since, unlike single-linked lists, we do not need to traverse to the predecessor node and store its reference. Rather, in a doubly linked list the reference of the predecessor node can be retrieved from the node that we want to delete.

Cons

• One of the major drawbacks of the doubly linked list is that you need more memory space to store one extra reference for each node.
• A few additional steps are required to be performed in order to perform insertion and deletion operations.

Implementing the Doubly Linked List with Python

In this section, we will see how we can create a very simple doubly linked list in Python. If you have read part 1 and part 2 of this series of articles, the code should be pretty straightforward.

As always, let's first create a class for the single node in the list:

class Node:
    def __init__(self, data):
        self.item = data
        self.nref = None
        self.pref = None

You can see in the above code, we create a Node class with three member variables: item, nref, and pref. The item variable will store the actual data for the node. The nref stores the reference to the next node, while pref stores the reference to the previous node in the doubly linked list.

Next, we need to create the DoublyLinkedList class, which contains different doubly linked list-related methods:

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

Throughout this article, we will keep adding methods to this class.

Inserting Items in Doubly Linked List

In this section, we will see the different ways of inserting items in a doubly linked list.

Inserting Items in Empty List

The easiest way to insert an item in a doubly linked list is to insert an item in the empty list. To do so, let's define a method insert_in_emptylist():

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

This method first checks whether the self.start_node variable is None or not. If the variable is None, it means that the list is actually empty. Next, a new node is created and its value is initialized by the value passed as a parameter to the data parameter of the insert_in_emptylist() method. Finally, the value of the self.start_node variable is set to the new node. In case the list is not empty, a message is simply displayed to the user that the list is not empty.

Add the insert_in_emptylist() method to the DoublyLinkedList class that you created earlier.

Inserting Items at the Start

To insert an item at the beginning of the doubly linked list, we have to first check whether the list is empty or not. If the list is empty, we can simply use the logic defined in the insert_in_emptylist() to insert the element since in an empty list, the first element is always at the start.

Else, if the list is not empty, we need to perform three operations:

1. For the new node, the reference to the next node will be set to self.start_node
2. For the self.start_node the reference to the previous node will be set to the newly inserted node
3. Finally, the self.start_node will become the newly inserted node

Let's put that into action in the insert_at_start() method:

def insert_at_start(self, data):
    if self.start_node is None:
        new_node = Node(data)
        self.start_node = new_node
        print("node inserted")
        return
    new_node = Node(data)
    new_node.nref = self.start_node
    self.start_node.pref = new_node
    self.start_node = new_node

Inserting Items at the End

Inserting an element at the end of the doubly linked list is somewhat similar to inserting an element at the start. First, we need to check if the list is empty. If the list is empty then we can simply use the insert_in_emptylist() method to insert the element. If the list already contains some element, we traverse through the list until the reference to the next node becomes None. When the next node reference becomes None it means that the current node is the last node.

The previous reference for the new node is set to the last node, and the next reference for the last node is set to the newly inserted node:

def insert_at_end(self, data):
    if self.start_node is None:
        new_node = Node(data)
        self.start_node = new_node
        return
    n = self.start_node
    while n.nref is not None:
        n = n.nref
    new_node = Node(data)
    n.nref = new_node
    new_node.pref = n

Inserting Item After Another Item

To insert an item after another item, we first check whether or not the list is empty. If the list is actually empty, we simply display the message that the "list is empty".

Otherwise, we iterate through all the nodes in the doubly linked list. In case the node after which we want to insert the new node is not found, we display the message to the user that the item is not found. Otherwise, if the node is found, it is selected and we perform four operations:

1. Set the previous reference of the newly inserted node to the selected node
2. Set the next reference of the newly inserted node to the next reference of the selected
3. If the selected node is not the last node, set the previous reference of the next node after the selected node to the newly added node
4. Finally, set the next reference of the selected node to the newly inserted node

To sum all this up:

def insert_after_item(self, x, data):
    if self.start_node is None:
        print("List is empty")
        return
    else:
        n = self.start_node
        while n is not None:
            if n.item == x:
                break
            n = n.nref
        if n is None:
            print("item not in the list")
        else:
            new_node = Node(data)
            new_node.pref = n
            new_node.nref = n.nref
            if n.nref is not None:
                n.nref.prev = new_node
            n.nref = new_node

Inserting Item Before Another Item

To insert an item before another item, we first check whether or not the list is empty. If the list is actually empty, we simply display the message that the "list is empty".

Otherwise, we iterate through all the nodes in the doubly linked list. In case the node before which we want to insert the new node is not found, we display the message to the user that the item is not found. If the node is found, it is selected and we perform four operations:

1. Set the next reference of the newly inserted node to the selected node.
2. Set the previous reference of the newly inserted node to the previous reference of the selected.
3. Set the next reference of the node previous to the selected node, to the newly added node.
4. Finally, set the previous reference of the selected node to the newly inserted node.

All-in-all, let's put all this into the insert_before_item() method:

def insert_before_item(self, x, data):
    if self.start_node is None:
        print("List is empty")
        return
    else:
        n = self.start_node
        while n is not None:
            if n.item == x:
                break
            n = n.nref
        if n is None:
            print("item not in the list")
        else:
            new_node = Node(data)
            new_node.nref = n
            new_node.pref = n.pref
            if n.pref is not None:
                n.pref.nref = new_node
            n.pref = new_node

Traversing a Doubly Linked List

Traversing a doubly linked list is very similar to traversing a singly 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.item , " ")
            n = n.nref

Deleting Elements From Doubly Linked List

Like insertion, there can be multiple ways to delete elements from a doubly linked list. In this section, we will review some of them.

Deleting Elements From the Start

The easiest way to delete an element from a doubly linked list is from the start. To do so, all you have to do is set the value of the start node to the next node and then set the previous reference of the start node to None. However, before we do that we need to perform two checks. First, we need to see if the list is empty. And then we have to see if the list contains only one element or not. If the list contains only one element then we can simply set the start node to None:

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_prev = None;

Deleting Elements From the End

To delete the element from the end, we again check if the list is empty or if the list contains a single element. If the list contains a single element, all we have to do is set the start node to None. If the list has more than one element, we iterate through the list until the last node is reached. Once we reach the last node, we set the next reference of the node previous to the last node, to None which actually removes the last node:

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

Deleting Elements by Value

Deleting an element by value is the trickiest of all the deletion methods in doubly linked lists since several cases have to be handled in order to remove an element by value. Let's first see what the method looks like and then we will see the explanation of the individual piece of code:

def delete_element_by_value(self, x):
    if self.start_node is None:
        print("The list has no element to delete")
        return 
    if self.start_node.nref is None:
        if self.start_node.item == x:
            self.start_node = None
        else:
            print("Item not found")
        return 

    if self.start_node.item == x:
        self.start_node = self.start_node.nref
        self.start_node.pref = None
        return

    n = self.start_node
    while n.nref is not None:
        if n.item == x:
            break;
        n = n.nref
    if n.nref is not None:
        n.pref.nref = n.nref
        n.nref.pref = n.pref
    else:
        if n.item == x:
            n.pref.nref = None
        else:
            print("Element not found")

First, we create the delete_element_by_value() method that takes the node value as a parameter and deletes that node. At the beginning of the method, we check if the list is empty or not. If the list is empty we simply display to the user that the list is empty:

if self.start_node is None:
    print("The list has no element to delete")
    return 

Next, we check if the list has a single element and that element is actually the element we want to delete. If the only element is the one that we want to delete, we simply set the self.start_node to None which means that the list will now have no item. If there is only one item and that is not the item that we want to delete, we will simply display the message that the item to be deleted is not found:

if self.start_node.nref is None:
    if self.start_node.item == x:
        self.start_node = None
    else:
        print("Item not found")
    return 

Next, we handle the case where the list has more than one item but the item to be deleted is the first item. In that case, we simply execute the logic that we wrote for the method delete_at_start(). The following piece of code deletes an element from the start in case of multiple items:

if self.start_node.item == x:
    self.start_node = self.start_node.nref
    self.start_node.pref = None
    return

Finally, if the list contains multiple items and the item to be deleted is not the first item, we traverse all the elements in the list except the last one and see if any of the nodes have a value that matches the value to be deleted. If the node is found, we perform the following two operations:

1. Set the value of the next reference of the previous node to the next reference of the node to be deleted
2. Set the previous value of the next node to the previous reference of the node to be deleted

Finally, if the node to be deleted is the last node, the next reference of the node previous to the last node is set to None:

n = self.start_node
while n.nref is not None:
    if n.item == x:
        break;
    n = n.nref
if n.nref is not None:
    n.pref.nref = n.nref
    n.nref.pref = n.pref
else:
    if n.item == x:
        n.pref.nref = None
    else:
        print("Element not found")

Reversing a Doubly Linked List

To reverse a doubly linked list, you basically have to perform the following operations:

1. The next reference of the start node should be set to none because the first node will become the last node in the reversed list
2. The previous reference of the last node should be set to None since the last node will become the previous node
3. The next references of the nodes (except the first and last node) in the original list should be swapped with the previous references

The method for reversing a doubly linked list should look something like:

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

Testing Doubly Linked List Methods

In this section, we will test the doubly linked methods that we created in the previous sections. Let's first create the object of the DoublyLinkedList class:

new_linked_list = DoublyLinkedList()

Testing Insertion Methods

Let's test the insertion methods first. We'll first add elements to the empty list:

new_linked_list.insert_in_emptylist(50)

Now if you traverse the list, you should see 50 as the only element in the list as shown below:

new_linked_list.traverse_list()

This will give us:

50

Now let's add a few elements at the start:

new_linked_list.insert_at_start(10)
new_linked_list.insert_at_start(5)
new_linked_list.insert_at_start(18)

Now if you traverse the list, you should see the following elements in the list:

18
5
10
50

Adding elements to the end shouldn't be too difficult:

new_linked_list.insert_at_end(29)
new_linked_list.insert_at_end(39)
new_linked_list.insert_at_end(49)

Now if you traverse the doubly linked list, you should see the following elements:

18
5
10
50
29
39
49 

Let's insert an element after 50:

new_linked_list.insert_after_item(50, 65)

Now the list should look like this:

18
5
10
50
65
29
39
49 

Finally, let's add an element before item 29.

new_linked_list.insert_before_item(29, 100)

The list at this point, should contain the following elements:

18
5
10
50
65
100
29
39
49 

Testing Deletion Methods

Let's now test the deletion methods on the items that we inserted in the last sections. Let's first delete an element from the start:

new_linked_list.delete_at_start()

Item 18 will be removed from the list:

5
10
50
65
100
29
39
49 

Similarly, the following script deletes the element from the end of the doubly linked list:

new_linked_list.delete_at_end()

Traversing the list now will return the following items:

5
10
50
65 
100 
29
39

Finally, you can also delete the elements by value using the delete_element_by_value() method:

new_linked_list.delete_element_by_value(65)

If you traverse the list now, you will see that item 65 will be deleted from the list.

Testing Reverse Method

Finally, let's reverse the list using the reverse_linked_list() method. Execute the following script:

new_linked_list.reverse_linked_list()

Now if you traverse the list, you will see the reversed linked list:

39
29
100
50
10
5 

Conclusion

The doubly linked list is extremely useful specifically when you have to perform lots of inserts and delete operations. The links to the previous and next nodes make it very easy to insert and delete new elements without keeping track of the previous and next nodes.

In this article, we saw how a doubly linked list can be implemented with Python. We also saw different ways to perform insert and delete operations on doubly linked lists. Finally, we studied how to reverse a doubly linked list.