 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.

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.tail = None
self.count = 0

def __repr__(self):
string = ""

string += "Doubly Linked List Empty"
return string

while(start != None):
string += f" -> {start.data}"
start = start.next
return string

def append(self, data):
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.count += 1
return

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.count -= 1
return

if index == (self.count - 1):
self.tail = self.tail.previous
self.tail.next = None
self.count -= 1
return

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