### What is a Doubly Circular Linked List?

A doubly circular linked list is a data structure where no NULL exists.

DCLL differs from a normal DLL with the fact that the last node’s next pointer points to the first node and the first node’s previous pointer point to the last node.

Given below is a diagram to represent a doubly circular linked list

### Operations on a doubly circular linked list:

There are various operations that can be performed on a doubly circular linked list

1. Insertion
• At beginning
• At end
1. Deletion
• From beginning
• From end
1. Searching
2. Traversal

### Node structure of a doubly circular linked list:

The following code represents the node structure of a doubly circular linked list.

Code:

## C++ Code

``````struct node {
int data;
node * next;
node * previous;
node(int d) {
data = d;
next = NULL;
previous = NULL;
}
}
``````

## Java Code

``````class node {
int data;
node  next;
node  previous;
node(int d) {
data = d;
}
}
``````

### Operations in a doubly circular linked list

#### Insertion from the beginning:

Inserting at the beginning is not a cumbersome task here as DCLL has both next and previous pointers which make the work easy. Here I’ll be dividing the procedure into three steps:

1. Changing the pointers of the last and head node to point to the newnode.
• Make the last node’s next pointer to point to the new node using the previous pointer of the head node.
• Make the previous pointer of the head node to point to the new node.
1. Connecting the pointers of newnode with last and head node.
• Make the previous pointer of the new node to point to the last node.
• Make the next pointer of the new node to point to the head node.
1. Return the new node as the new head of our DCLL.

Code:

## C++ Code

``````node * insertion_begg(node * head, int x) {
node * newnode = new node(x);
newnode -> previous = newnode;
newnode -> next = newnode;

return newnode;
}
// Step 1: Changing the pointers of last node and head node
head -> previous -> next = newnode; // step 1
head -> previous = newnode; // step 2

// Step 2: Connecting the pointers of newnode to last node and head node
newnode -> previous = head -> previous;

// Step 3: Return newnode as new head of DCLL
return newnode;
}
``````

## Java Code

``````static node insert_begg(node head, int x) {
node newnode = new node(x);
newnode.next = newnode;
newnode.previous = newnode;
return newnode;
}

return newnode;
}
``````

#### Insertion from end:

Insertion from the end is very similar to insertion from the beginning. The only difference is what we return at the end of the function. In insertion from the beginning, we used to return the newnode as our new head whereas, in insertion from the end, we return the original head.

Code:

## C++Code

``````node * insertion_end(node * head, int x) {
node * newnode = new node(x);
newnode -> previous = newnode;
newnode -> next = newnode;

return newnode;
}
// Step 1: Changing the pointers of last node and head node
head -> previous -> next = newnode; // step 1
head -> previous = newnode; // step 2

// Step 2: Connecting the pointers of newnode to last node and head node
newnode -> previous = head -> previous;

// Step 3: Return head of DCLL
return head; // difference b/w insertion at end and beginning
}

``````

## Java Code

``````static node insert_end(node head, int x) {
node newnode = new node(x);
newnode.next = newnode;
newnode.previous = newnode;
return newnode;
}
// Step 1: Changing the pointers of last node and head node

// Step 2: Connecting the pointers of newnode to last node and head node

// Step 3: Return the head of DCLL
}
``````

#### Traversal:

In traversal, we use a pointer of type node, to iterate across the list and print the data of the node at that point until we return back to the head node. We use a do-while loop to make the task easy.

Code:

## C++ Code

``````void printDCLL(node * head) {
do {
cout << current -> data << " ";
current = current -> next;
}
``````

## Java Code

``````public static void printDCLL(node head) {
do {
System.out.print(current.data + " ");
current = current.next;
}
``````

#### Searching:

Searching is a very common function in linked lists. We have a target and we iterate through the linked list and check if any node’s data matches with the target. If found, we print “Found” else we print “Not Found”.

Code:

## C++ Code

``````void search(node * head, int target) {
do {
if (current -> data == target) {
cout << "Found";
return;
}
current = current -> next;

}
``````

## Java Code

``````static void search(node head, int x) {
do {
if (current.data == x) {
System.out.println("Found");
return;
}
current = current.next;
}
``````

1. Since it has a previous pointer, keeping a track of every node is very easy.
2. Reversal of a linked list can be implemented in a simple way.
3. It can be used to implement various data structures.
4. Bi-directional traversal is possible in DCLL.