Generic selectors
Exact matches only
Search in title
Search in content
wb_sunny

Doubly Linked List in Python – Made Easy

Doubly Linked Lists Python Title

A doubly linked list is a data structure that is used to store lists. It is very similar to linked lists but with a few extra features. In this tutorial, we will discuss what a doubly-linked list is, we will implement it in python and see it’s output.

Pre-Requisite: Linked List

Before we move on to doubly linked lists, we need to discuss what linked lists are.

A linked list, as the name suggests, is a list in which the list items are linked to other list items in a particular way. The exact way the items are linked differs in different types of linked lists.

The most common linked list is the “singly linked list” or simply, “linked list”, in this, each item links to the next item in the list. So, to access the 10th item, we need to first access the 9th item because it links to the 10th item. And once we access the 10th item, it will allow us to access the 11th item through the link that the 10th item has.

Each item in a linked list is called a node. In a singly linked list, each node has two parts. The first part stores the data of the node, and the second part stores the link to the next node.

Now let us look at doubly linked lists.

What is a Doubly Linked List?

A doubly linked list is also a list in which the nodes are connected through links, but in this case, each node links to the next item as well as the previous item. So, once we have accessed the 10th node, we can access the 9th node and the 11th node, and to access a particular node, we will need to access either the node before it or the node after it.

The way we do this is that each node has three parts. The first part is the actual data to be stored, the second part is the link to the previous node in the list, and the third part is the link to the next node in the list.

The benefit of having two links is that it makes operations such as appending and deleting much easier and faster than a singly linked list.

To visualize, a doubly linked list looks something like this:

Doubly Linked List Repr 2
Doubly Linked List Representation

In the above example, you can see that there are four items/nodes in the linked list. Each node has some data or content, and each node points/links to the next and the previous node of the list. The first node’s previous link and the last node’s next link do not point to anything, so they store None (in the case of python).

To start, a list head points to the first node in the list, and a list tail points to the last node in the list. So the first and last nodes are directly accessible through them. To reach the other nodes, we either go through the head or the tail and then subsequently access the next or previous nodes respectively till we reach the target.

Implementing a Doubly Linked List in Python

Creating a doubly linked list is very straightforward. We have to create two classes, one class for nodes and the other class that will create the linked list using the nodes created by the first class.

1. Class: Node

For the node class, we only have three members in the class. One to store data, one to store the next node, and one for the previous node.

The class definition will look something like this:

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

Here, initially, the nodes don’t point to any other node, and it may or may not have data depending on how it was created.

2. Class: Doubly Linked List

This class will contain much more than the node class. It will contain the head node, the tail node, the number of items in the list, and many necessary methods like the method to insert new nodes, delete existing nodes, search the existing nodes, and print the list.

The class will look something like this:

class DLL:
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0
        
    def __repr__(self):
        string = ""
        
        if(self.head == None):
            string += "Doubly Linked List Empty"
            return string
        
        string += f"Doubly Linked List:\n{self.head.data}"        
        start = self.head.next
        while(start != None):
            string += f" -> {start.data}"
            start = start.next
        return string
        
    def append(self, data):
        if self.head == None:
            self.head = Node(data)
            self.tail = self.head
            self.count += 1
            return
        
        self.tail.next = Node(data)
        self.tail.next.previous = self.tail
        self.tail = self.tail.next
        self.count += 1
        
    def insert(self, data, index):
        if (index > self.count) | (index < 0):
            raise ValueError(f"Index out of range: {index}, size: {self.count}")
            
        if(index == self.count):
            self.append(data)
            return
            
        if(index == 0):
            self.head.previous = Node(data)
            self.head.previous.next = self.head
            self.head = self.head.previous
            self.count += 1
            return
        
        start = self.head
        for _ in range(index):
            start = start.next
        start.previous.next = Node(data)
        start.previous.next.previous = start.previous
        start.previous.next.next = start
        start.previous = start.previous.next
        self.count += 1
        return
    
    def remove(self, index):
        if (index >= self.count) | (index < 0):
            raise ValueError(f"Index out of range: {index}, size: {self.count}")
        
        if index == 0:
            self.head = self.head.next
            self.head.previous = None
            self.count -= 1
            return
            
        if index == (self.count - 1):
            self.tail = self.tail.previous
            self.tail.next = None
            self.count -= 1
            return
        
        start = self.head
        for i in range(index):
            start = start.next
        start.previous.next, start.next.previous = start.next, start.previous
        self.count -= 1
        return
    
    def index(self, data):
        start = self.head
        for i in range(self.count):
            if(start.data == data):
                return i
            start = start.next
        return None
    
    def size(self):
        return self.count
    
    def display(self):
        print(self)

The above class has many members, let us discuss them one by one.

3. The __init__ method

In the constructor, we are declaring three variables. head and tail are initialized with None, which means there are no variables in the list at the beginning, and so the count is also initialized with 0.

4. The __repr__ method

The __repr__ method will return the string that will print the linked list. So either the list is empty, in which case we print that, or the list is not empty, so we print the data in each node one by one.

5. The append and insert method

We can either append or insert nodes at a specified position in this implementation. To append, we will check if the list is empty, if so then the head and tail can point to the new node. Otherwise, we will make the last node’s next point to the new node, then make the new node’s previous point to the last node, and finally, make the tail point to the new node.

To insert at a specified position, if the position is at the end, then we just append the node, otherwise, if the position is at the beginning, then we make the first node’s previous point to the new node, then make the new node’s next point to the first node, and finally, we make the head point to the new node.

If the position specified is in the middle, then we first reach that position, make the next of the node before that position point to the new node, then make the new node’s previous point to the node before that position, then make the new node’s next point to the node at that position, and finally, we make the previous of the node at that position point to the new node.

We also check if the given index is valid or not, and if not, we can raise a ValueError. Also, we increment the count after every successful insert operation.

6. The remove method

To remove an item we must specify where the item is to be removed from. If the specified index is out of range, we raise a ValueError. If the index is 0, we are removing the first item, to do this, we make the head point to the second node. If the head is null, it means that the list is now empty, if not, then we have to make the new head‘s previous store None.

Similarly, if the index is one less than the size of the list, it means we have to remove the last item, so we make the tail point to the second-last node and then make the new tail‘s next store None.

If the index is somewhere in the middle, we first reach that position, then make the next of the node before that position point to the node after that position, and finally, make the previous of the node after that position point to the node before that position.

In removal, we are only making the node inaccessible from the list, and the actual process of removing it from memory is left to the garbage collection module of Python.

7. The index, size, and display method.

The index method is used to search for an item in the list, we go through the entire list based on the list size and return the index if we find the target. If not, we return None.

The size method returns the value of the count member of the class, which stores the number of items in the list.

And the display method prints the object, which calls the __repr__ method and the returned string is printed to the screen.

The Output

After executing multiple statements on the class, here is the output:

Dll Init Append And Insert Example
Example illustrating initialization, append method, and insert method.
Dll Remove Index Size And Display Example
Example illustrating remove method, index method, size method, and display method.

Conclusion

In this tutorial, we studied Doubly Linked Lists and implemented it in Python. We started by understanding the working of a singly linked list, then we discussed how a doubly linked list is different. We wrote the code for the data structure in python and discussed how each method is working, and finally we reviewed the output of the code.

I hope you had a great time learning, and see you in the next tutorial.