# 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; }; class LinkedList { public: Node* head; public: //constructor to create an empty LinkedList LinkedList(){ head = NULL; } };

//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 #class Linked List class LinkedList: #constructor to create an empty LinkedList def __init__(self): self.head = None

//node structure class Node { int data; Node next; Node prev; }; class LinkedList { Node head; //constructor to create an empty LinkedList LinkedList(){ head = null; } };

//node structure class Node { public int data; public Node next; public Node prev; }; class LinkedList { public Node head; //constructor to create an empty LinkedList public LinkedList(){ head = null; } };

//node structure class Node { public $data; public $next; public $prev; } class LinkedList { public $head; //constructor to create an empty LinkedList public function __construct(){ $this->head = null; } };

### 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; }; class LinkedList { public: Node* head; public: //constructor to create an empty LinkedList LinkedList(){ head = NULL; } }; //test the code int main() { //create an empty LinkedList LinkedList MyList; //Add first node. Node* first = new Node(); first->data = 10; first->next = NULL; first->prev = NULL; //linking with head node MyList.head = first; //linking next of the node with head first->next = MyList.head; //linking prev of the head MyList.head->prev = first; //Add second node. Node* second = new Node(); second->data = 20; second->next = NULL; //linking with first node second->prev = first; first->next = second; //linking next of the node with head second->next = MyList.head; //linking prev of the head MyList.head->prev = second; //Add third node. Node* third = new Node(); third->data = 30; third->next = NULL; //linking with second node third->prev = second; second->next = third; //linking next of the node with head third->next = MyList.head; //linking prev of the head MyList.head->prev = 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; //Add first node. 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; //linking with head node MyList = first; //linking next of the node with head first->next = MyList; //linking prev of the head MyList->prev = first; //Add second node. struct Node* second; //allocate second node in the heap second = (struct Node*)malloc(sizeof(struct Node)); second->data = 20; second->next = NULL; //linking with first node second->prev = first; first->next = second; //linking next of the node with head second->next = MyList; //linking prev of the head MyList->prev = second; //Add third node. struct Node* third; //allocate third node in the heap third = (struct Node*)malloc(sizeof(struct Node)); third->data = 30; third->next = NULL; //linking with second node third->prev = second; second->next = third; //linking next of the node with head third->next = MyList; //linking prev of the head 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 #class Linked List class LinkedList: #constructor to create an empty LinkedList def __init__(self): self.head = None # test the code # create an empty LinkedList MyList = LinkedList() #Add first node. first = Node(10) #linking with head node MyList.head = first #linking next of the node with head first.next = MyList.head #linking prev of the head MyList.head.prev = first #Add second node. second = Node(20) #linking with first node second.prev = first first.next = second #linking next of the node with head second.next = MyList.head #linking prev of the head MyList.head.prev = second #Add third node. third = Node(30) #linking with second node third.prev = second second.next = third #linking next of the node with head third.next = MyList.head #linking prev of the head MyList.head.prev = third

//node structure class Node { int data; Node next; Node prev; }; class LinkedList { Node head; //constructor to create an empty LinkedList LinkedList(){ head = null; } }; // test the code public class Implementation { public static void main(String[] args) { //create an empty LinkedList LinkedList MyList = new LinkedList(); //Add first node. Node first = new Node(); first.data = 10; first.next = null; first.prev = null; //linking with head node MyList.head = first; //linking next of the node with head first.next = MyList.head; //linking prev of the head MyList.head.prev = first; //Add second node. Node second = new Node(); second.data = 20; second.next = null; //linking with first node second.prev = first; first.next = second; //linking next of the node with head second.next = MyList.head; //linking prev of the head MyList.head.prev = second; //Add third node. Node third = new Node(); third.data = 30; third.next = null; //linking with second node third.prev = second; second.next = third; //linking next of the node with head third.next = MyList.head; //linking prev of the head MyList.head.prev = third; } }

using System; //node structure class Node { public int data; public Node next; public Node prev; }; class LinkedList { public Node head; //constructor to create an empty LinkedList public LinkedList(){ head = null; } }; // test the code class Implementation { static void Main(string[] args) { //create an empty LinkedList LinkedList MyList = new LinkedList(); //Add first node. Node first = new Node(); first.data = 10; first.next = null; first.prev = null; //linking with head node MyList.head = first; //linking next of the node with head first.next = MyList.head; //linking prev of the head MyList.head.prev = first; //Add second node. Node second = new Node(); second.data = 20; second.next = null; //linking with first node second.prev = first; first.next = second; //linking next of the node with head second.next = MyList.head; //linking prev of the head MyList.head.prev = second; //Add third node. Node third = new Node(); third.data = 30; third.next = null; //linking with second node third.prev = second; second.next = third; //linking next of the node with head third.next = MyList.head; //linking prev of the head MyList.head.prev = third; } }

<?php //node structure class Node { public $data; public $next; public $prev; } class LinkedList { public $head; //constructor to create an empty LinkedList public function __construct(){ $this->head = null; } }; // test the code //create an empty LinkedList $MyList = new LinkedList(); //Add first node. $first = new Node(); $first->data = 10; $first->next = null; $first->prev = null; //linking with head node $MyList->head = $first; //linking next of the node with head $first->next = $MyList->head; //linking prev of the head $MyList->head->prev = $first; //Add second node. $second = new Node(); $second->data = 20; $second->next = null; //linking with first node $second->prev = $first; $first->next = $second; //linking next of the node with head $second->next = $MyList->head; //linking prev of the head $MyList->head->prev = $second; //Add third node. $third = new Node(); $third->data = 30; $third->next = null; //linking with second node $third->prev = $second; $second->next = $third; //linking next of the node with head $third->next = $MyList->head; //linking prev of the head $MyList->head->prev = $third; ?>