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:
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:
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.