Data Structures Data Structures References
Data Structures Data Structures References

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:

Linked List Node

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.

Linked List

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;
?>

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;
};

class LinkedList {
  public:
    Node* head;
  public:
    //constructor to create an empty LinkedList
    LinkedList(){
      head = NULL;
    }

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

// 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; 

  //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
void PrintList(struct Node* head_ref) {
  struct Node* temp = head_ref;
  if(head_ref != NULL) {
    printf("The list contains: ");
    while (1) {
      printf("%i ",temp->data);
      temp = temp->next;
      if(temp == head_ref)
        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;

  //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; 

  //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

#class Linked List
class LinkedList:
  #constructor to create an empty LinkedList
  def __init__(self):
    self.head = None

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

# 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

#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;
};

class LinkedList {
  Node head;
  //constructor to create an empty LinkedList
  LinkedList(){
    head = null;
  }

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

// 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;

    //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;
};

class LinkedList {
  public Node head;
  //constructor to create an empty LinkedList
  public LinkedList(){
    head = null;
  } 

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

// 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; 

    //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;
}

class LinkedList {
  public $head;

  //constructor to create an empty LinkedList
  public function __construct(){
    $this->head = null;
  }

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

// 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;

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

The above code will give the following output: 

The list contains: 10 20 30


Recommended Pages

AlphaCodingSkills
AlphaCodingSkills Android App
Facebook Page Twitter Page LinkedIn Page
Learning Tutorials
Learning Tutorials
Useful Links
Python Libraries
About Us  |  Privacy Policy  |  Contact Us
AlphaCodingSkills is a online learning portal that provides tutorials on Python, Java, C++, C, C#, PHP, R, Ruby, Rust, Scala, Swift, Perl, SQL, Data Structures and Algorithms. Tutorials, examples, references and content of the website are reviewed and simplified continuously to improve comprehensibility and eliminate any possible error. We use cookies to ensure best browsing experience on our website. While using this website, you acknowledge to have read and accepted our cookie and privacy policy.