# Doubly Circular Linked Lists in Python A doubly circular linked list is a data structure that is utilized to store records in a list. It is fundamentally the same as linked lists but with a few additional highlights. In this tutorial, we’ll look at what a doubly circular linked list is, how to make one in Python, and what is its output.

## Pre-Requisites

We should first discuss a few data structures before moving onto doubly circular linked lists.

A linked list is a list in which items are linked to other items in a specific way. Different types of linked lists have different ways of linking items.

The simplest linked list is the “singly linked list” or simply, a “linked list”. In this, each item links to the next item in the list. (But not in reverse). So to access the nth item, we will need to access the (n-1)th item first. And accessing the nth item enables us to access the (n+1)th item of the list.

We have direct access to the first item of the list, using which we can access the 2nd one, and then the 3rd one, and so on until the last item which does not have access to any other item in the list.

Each item in a linked list is called a node. Each node has a part that stores its data, and another part to store the link/reference to the next node.

Doubly linked lists are similar to linked lists, but in this case, each node has two links, one to the next node and one to the previous node.

So, to access the nth node, we will need to first access the (n-1)th node or the (n+1)th node. And after we have accessed the nth node, using it, we can access the (n-1)th node or the (n+1)th node. That is, traversal can happen in either direction.

Each node is made of three parts, one for data and the other two for the previous and next links. It looks something like this:

Circular linked lists are also similar to linked lists, the only difference being that the last node links to the first node instead of having no link. So it forms a circular linkage between the nodes, and if we keep on accessing the next nodes, it will never end and go back to the start after the first node.

It looks something like this:

Now that we know how doubly linked lists and circular linked lists look like, it’s not hard to understand what a doubly circular linked list will be.

Here, each node contains three parts, one for the data and the other two for the links. Each node links to the next and previous nodes of the list. For the first node, there is no previous node, so it goes in a circle and links to the last node of the list. Similarly, for the last node, there is no next node, so it goes in a circle and links to the first node of the list.

To access any node, we need to access either the node after it or the node before it, and after accessing any node, the nodes after and before it can be directly accessed. But we can also access the last node directly from the first node and vice versa.

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

In the above example, you can see that there are four nodes in the list and each node is connected to a node after it and a node before it. The last node points to the second-last node and the first node, and the first node points to the last node and the second node.

The head points to the start of the list, and now we can either traverse forward and reach the end or we can traverse backwards and reach the start of the list.

## Implementing Doubly Circular Linked Lists in Python

We have to create two classes, one for the nodes and another that will use the nodes to create the linked list.

### Class: Node

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

Initially, upon creation of a node, it will point to itself in both directions to form a doubly circular linked list with only one item.

### Class: Doubly Circular Linked List

```class DCLL:
def __init__(self):
self.count = 0

def __repr__(self):
string = ""

string += "Doubly Circular Linked List Empty"
return string

string += f" -> {temp.data}"
temp = temp.next
return string

def append(self, data):
self.insert(data, self.count)
return

def insert(self, data, index):
if (index > self.count) | (index < 0):
raise ValueError(f"Index out of range: {index}, size: {self.count}")

self.count = 1
return

if(index == 0):
temp = temp.previous
else:
for _ in range(index - 1):
temp = temp.next

temp.next.previous = Node(data)
temp.next.previous.next, temp.next.previous.previous = temp.next, temp
temp.next = temp.next.previous
if(index == 0):
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 self.count == 1:
self.count = 0
return

for _ in range(index):
target = target.next

target.previous.next, target.next.previous = target.next, target.previous
self.count -= 1

def index(self, data):
for i in range(self.count):
if(temp.data == data):
return i
temp = temp.next
return None

def get(self, index):
if (index >= self.count) | (index < 0):
raise ValueError(f"Index out of range: {index}, size: {self.count}")

for _ in range(index):
temp = temp.next
return temp.data

def size(self):
return self.count

def display(self):
print(self)
```

The above class contains many methods, let’s discuss them one by one.

The `__init__` method

We declare two members, the `head` and the `count` initialized by `None` and `0` respectively because there are no nodes in the list at the beginning.

The `__repr__` method

The `__repr__` method will return a string that will print the contents of the list appropriately on the screen.

The `append` and `insert` method

We can either append or insert nodes in the list. The `append` method is created just for convenience as it calls the `insert` method and sends the appropriate values.

In the `insert` method, we first check if the `index` is in range or not, and if not, we raise a `ValueError`. Then, if the list is empty, then we simply assign a new node to the `head` and make the `count` equal to 1. Now we reach the node just before the `index` where the new node is to be inserted.

At this point, we make the `previous` of the node at the specified index equal to the new node. Then we make the new node’s `next` and `previous` equal to the node at the specified index and the node before the specified index respectively. And now we make the `next` of the node before the specified index equal to the new node. Finally, if the specified index was `0`, then we make the `head` point to the node just before where it was pointing.

Just increment the `count` and the `insert` method is done.

The `remove` method

In this method too we first check if the `index` is out of range and throw a `ValueError` if it is. Then if there is one node only, we simply make the `head` as `None` and make the `count` as `0` and return.

If not, we reach the required node to be deleted, and if the target node is the `head`, we make the `head` point to the node after it so that we don’t lose the list.

Finally, we make the `next` of the node before the specified index point to the node after the specified index, and we make the `previous` of the node after the specified index point to the node before the specified index. This will make the node at the specified index unreachable from the list (basically skipped), and we decrement the count to finish the method.

The `index`, `get`, `size`, and `display` method

The `index` method searches linearly through the list and returns the index if the item is found, `None` otherwise.

The `get` method returns the item at the specified index, and raises a `ValueError` if the index is out of range.

The `size` method returns the number of items in the list.

The `display` method prints the list.