C - 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 as shown below:

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

Create a Circular Doubly Linked List

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

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

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