Data Structures Data Structures Resources

# Data Structure - Circular Doubly Linked List

A circular doubly linked list is a linear data structure, in which the elements are stored in the form of a node. Each node contains three sub-elements. A data part that stores the value of the element, the previous part that stores the pointer to the previous node, and the next part that stores the pointer to the next node as shown in the below image: The first node also known as HEAD is always used as a reference to traverse the list. Last element contains link to the first element as next and the first element contains link of the last element as previous. A circular doubly linked can be visualized as a chain of nodes, where every node points to previous and next node. ## Implementation of Circular Doubly Linked List

### Representation:

In C, a node can be created using structure. In C++, circular doubly linked list can be created using a class and a Node using structures. The LinkedList class contains Node as class member.

In Java, Python, C# and PHP, circular doubly linked list can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.

```//node structure
struct Node {
int data;
Node* next;
Node* prev;
};

public:
public:
//constructor to create an empty LinkedList
}
};
```
```//node structure
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
```
```# node structure
class Node:
#constructor to create a new node
def __init__(self, data):
self.data = data
self.next = None
self.prev = None

#constructor to create an empty LinkedList
def __init__(self):
```
```//node structure
class Node {
int data;
Node next;
Node prev;
};

//constructor to create an empty LinkedList
}
};
```
```//node structure
class Node {
public int data;
public Node next;
public Node prev;
};

//constructor to create an empty LinkedList
}
};
```
```//node structure
class Node {
public \$data;
public \$next;
public \$prev;
}

//constructor to create an empty LinkedList
public function __construct(){
}
};
```

### Create a Circular Doubly Linked List

Let us create a simple circular doubly linked list which contains three data nodes.

```#include <iostream>
using namespace std;

//node structure
struct Node {
int data;
Node* next;
Node* prev;
};

public:
public:
//constructor to create an empty LinkedList
}
};

//test the code
int main() {

Node* first = new Node();
first->data = 10;
first->next = NULL;
first->prev = NULL;

Node* second = new Node();
second->data = 20;
second->next = NULL;
second->prev = first;
first->next = second;

Node* third = new Node();
third->data = 30;
third->next = NULL;
third->prev = second;
second->next = third;

return 0;
}
```
```#include <stdio.h>
#include <stdlib.h>

//node structure
struct Node {
int data;
struct Node* next;
struct Node* prev;
};

// test the code
int main() {
//create the head node with name MyList
struct Node* MyList = NULL;

struct Node* first;
//allocate second node in the heap
first = (struct Node*)malloc(sizeof(struct Node));
first->data = 10;
first->next = NULL;
first->prev = NULL;
MyList = first;
first->next = MyList;
MyList->prev = first;

struct Node* second;
//allocate second node in the heap
second = (struct Node*)malloc(sizeof(struct Node));
second->data = 20;
second->next = NULL;
second->prev = first;
first->next = second;
second->next = MyList;
MyList->prev = second;

struct Node* third;
//allocate third node in the heap
third = (struct Node*)malloc(sizeof(struct Node));
third->data = 30;
third->next = NULL;
third->prev = second;
second->next = third;
third->next = MyList;
MyList->prev = third;

return 0;
}
```
```# node structure
class Node:
#constructor to create a new node
def __init__(self, data):
self.data = data
self.next = None
self.prev = None

#constructor to create an empty LinkedList
def __init__(self):

# test the code

first = Node(10)

second = Node(20)
second.prev = first
first.next = second

third = Node(30)
third.prev = second
second.next = third
```
```//node structure
class Node {
int data;
Node next;
Node prev;
};

//constructor to create an empty LinkedList
}
};

// test the code
public class Implementation {
public static void main(String[] args) {

Node first = new Node();
first.data = 10;
first.next = null;
first.prev = null;

Node second = new Node();
second.data = 20;
second.next = null;
second.prev = first;
first.next = second;

Node third = new Node();
third.data = 30;
third.next = null;
third.prev = second;
second.next = third;
}
}
```
```using System;

//node structure
class Node {
public int data;
public Node next;
public Node prev;
};

//constructor to create an empty LinkedList
}
};

// test the code
class Implementation {
static void Main(string[] args) {

Node first = new Node();
first.data = 10;
first.next = null;
first.prev = null;

Node second = new Node();
second.data = 20;
second.next = null;
second.prev = first;
first.next = second;

Node third = new Node();
third.data = 30;
third.next = null;
third.prev = second;
second.next = third;
}
}
```
```<?php
//node structure
class Node {
public \$data;
public \$next;
public \$prev;
}

//constructor to create an empty LinkedList
public function __construct(){
}
};

// test the code

\$first = new Node();
\$first->data = 10;
\$first->next = null;
\$first->prev = null;

\$second = new Node();
\$second->data = 20;
\$second->next = null;
\$second->prev = \$first;
\$first->next = \$second;

\$third = new Node();
\$third->data = 30;
\$third->next = null;
\$third->prev = \$second;
\$second->next = \$third;
?>
```

### Traverse a Circular Doubly Linked List

A circular doubly linked list can be traversed from any node of the list using a temp node. Keep on moving the temp node to the next one and displaying its content. Stop the traversal, after reaching the starting node.

```#include <iostream>
using namespace std;

//node structure
struct Node {
int data;
Node* next;
Node* prev;
};

public:
public:
//constructor to create an empty LinkedList
}

//display the content of the list
void PrintList() {
if(temp != NULL) {
cout<<"The list contains: ";
while(true) {
cout<<temp->data<<" ";
temp = temp->next;
break;
}
cout<<endl;
} else {
cout<<"The list is empty.\n";
}
}
};

// test the code
int main() {

Node* first = new Node();
first->data = 10;
first->next = NULL;
first->prev = NULL;

Node* second = new Node();
second->data = 20;
second->next = NULL;
second->prev = first;
first->next = second;

Node* third = new Node();
third->data = 30;
third->next = NULL;
third->prev = second;
second->next = third;

//print the content of list
MyList.PrintList();
return 0;
}
```

The above code will give the following output:

```The list contains: 10 20 30
```
```#include <stdio.h>
#include <stdlib.h>

//node structure
struct Node {
int data;
struct Node* next;
struct Node* prev;
};

//display the content of the list
printf("The list contains: ");
while (1) {
printf("%i ",temp->data);
temp = temp->next;
break;
}
printf("\n");
} else {
printf("The list is empty.\n");
}
}

// test the code
int main() {
//create the head node with name MyList
struct Node* MyList = NULL;

struct Node* first;
//allocate second node in the heap
first = (struct Node*)malloc(sizeof(struct Node));
first->data = 10;
first->next = NULL;
first->prev = NULL;
MyList = first;
first->next = MyList;
MyList->prev = first;

struct Node* second;
//allocate second node in the heap
second = (struct Node*)malloc(sizeof(struct Node));
second->data = 20;
second->next = NULL;
second->prev = first;
first->next = second;
second->next = MyList;
MyList->prev = second;

struct Node* third;
//allocate third node in the heap
third = (struct Node*)malloc(sizeof(struct Node));
third->data = 30;
third->next = NULL;
third->prev = second;
second->next = third;
third->next = MyList;
MyList->prev = third;

//print the content of list
PrintList(MyList);
return 0;
}
```

The above code will give the following output:

```The list contains: 10 20 30
```
```# node structure
class Node:
#constructor to create a new node
def __init__(self, data):
self.data = data
self.next = None
self.prev = None

#constructor to create an empty LinkedList
def __init__(self):

#display the content of the list
def PrintList(self):
if(temp != None):
print("The list contains:", end=" ")
while (True):
print(temp.data, end=" ")
temp = temp.next
break
print()
else:
print("The list is empty.")

# test the code

first = Node(10)

second = Node(20)
second.prev = first
first.next = second

third = Node(30)
third.prev = second
second.next = third

#print the content of list
MyList.PrintList()
```

The above code will give the following output:

```The list contains: 10 20 30
```
```//node structure
class Node {
int data;
Node next;
Node prev;
};

//constructor to create an empty LinkedList
}

//display the content of the list
void PrintList() {
Node temp = new Node();
if(temp != null) {
System.out.print("The list contains: ");
while(true) {
System.out.print(temp.data + " ");
temp = temp.next;
break;
}
System.out.println();
} else {
System.out.println("The list is empty.");
}
}
};

// test the code
public class Implementation {
public static void main(String[] args) {

Node first = new Node();
first.data = 10;
first.next = null;
first.prev = null;

Node second = new Node();
second.data = 20;
second.next = null;
second.prev = first;
first.next = second;

Node third = new Node();
third.data = 30;
third.next = null;
third.prev = second;
second.next = third;

//print the content of list
MyList.PrintList();
}
}
```

The above code will give the following output:

```The list contains: 10 20 30
```
```using System;

//node structure
class Node {
public int data;
public Node next;
public Node prev;
};

//constructor to create an empty LinkedList
}

//display the content of the list
public void PrintList() {
Node temp = new Node();
if(temp != null) {
Console.Write("The list contains: ");
while(true) {
Console.Write(temp.data + " ");
temp = temp.next;
break;
}
Console.WriteLine();
} else {
Console.WriteLine("The list is empty.");
}
}
};

// test the code
class Implementation {
static void Main(string[] args) {

Node first = new Node();
first.data = 10;
first.next = null;
first.prev = null;

Node second = new Node();
second.data = 20;
second.next = null;
second.prev = first;
first.next = second;

Node third = new Node();
third.data = 30;
third.next = null;
third.prev = second;
second.next = third;

//print the content of list
MyList.PrintList();
}
}
```

The above code will give the following output:

```The list contains: 10 20 30
```
```<?php
//node structure
class Node {
public \$data;
public \$next;
public \$prev;
}

//constructor to create an empty LinkedList
public function __construct(){
}

//display the content of the list
public function PrintList() {
\$temp = new Node();
if(\$temp != null) {
echo "The list contains: ";
while(true) {
echo \$temp->data." ";
\$temp = \$temp->next;
break;
}
echo "\n";
} else {
echo "The list is empty.\n";
}
}
};

// test the code

\$first = new Node();
\$first->data = 10;
\$first->next = null;
\$first->prev = null;

\$second = new Node();
\$second->data = 20;
\$second->next = null;
\$second->prev = \$first;
\$first->next = \$second;

\$third = new Node();
\$third->data = 30;
\$third->next = null;
\$third->prev = \$second;
\$second->next = \$third;

//print the content of list
\$MyList->PrintList();
?>
```

The above code will give the following output:

```The list contains: 10 20 30
```

5