Doubly Circular Linked List

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

Insertion
- At beginning
- At end

Deletion
- From beginning
- From end

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

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.

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.

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);
  if (head == NULL) {
    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;
  newnode -> next = head;

  // 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);
  if (head == null) {
    newnode.next = newnode;
    newnode.previous = newnode;
    return newnode;
  }
  newnode.previous = head.previous;
  newnode.next = head;
  head.previous.next = 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);
  if (head == NULL) {
    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;
  newnode -> next = head;

  // 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);
  if (head == null) {
    newnode.next = newnode;
    newnode.previous = newnode;
    return newnode;
  }
  // Step 1: Changing the pointers of last node and head node
  head.previous.next = newnode;
  head.previous = newnode;

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

  // Step 3: Return the head of DCLL
  return head;
}

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) {
  if(head==NULL) return;
  node * current = head;
  do {
    cout << current -> data << " ";
    current = current -> next;
  } while (current != head);
}

Java Code

public static void printDCLL(node head) {
  if (head == null) return;
  node current = head;
  do {
    System.out.print(current.data + " ");
    current = current.next;
  } while (current != head);
}

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) {
  node * current = head;
  do {
    if (current -> data == target) {
      cout << "Found";
      return;
    }
    current = current -> next;
  } while (current != head);

  cout << "Not Found";
}

Java Code

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

Advantages of Circular Linked List:

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

Special thanks to Yash Mishra for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article