Doubly Circular Linked List

Introduction

A Doubly Circular Linked List is a variation of the doubly linked list where the last node points back to the first node, and the first node points to the last node, thus forming a circular structure. It’s a highly efficient structure, especially for operations that require cyclic traversal.
In a regular doubly linked list, each node has two pointers:

• One pointing to the previous node.

• One pointing to the next node.

In a Doubly Circular Linked List, the first node’s previous pointer points to the last node, and the last node’s next pointer points to the first node. This structure makes it easy to traverse in both directions, making it more versatile for certain use cases like round-robin scheduling.

Need for Doubly Circular Linked List

A Doubly Circular Linked List is useful in the following scenarios:

• Circular Traversal: It allows traversing the list in a circular manner, making it useful for implementing things like a round-robin scheduler or a circular buffer.

• Efficient Operations: Operations that need to traverse or modify both ends of the list can be done in constant time, as both the head and tail are connected.

• Bidirectional Traversal: It supports both forward and backward traversal with ease.

• Memory Efficiency: The circular connection eliminates the need for special handling of the first or last node.

Operations on Doubly Circular Linked List

1. Creation of Doubly Circular Linked List

To create a doubly circular linked list, the first and last node must be connected to each other to form the circular structure.

C Code for Creation

#include <stdio.h>
#include <stdlib.h>

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

// Function to create a doubly circular linked list with one node
struct Node* createList(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = newNode;
    newNode->prev = newNode;
    return newNode;
}

// Function to display the list
void display(struct Node* head) {
    struct Node* temp = head;
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("(head)\n");
}

int main() {
    struct Node* head = createList(10);
    display(head);
    return 0;
}

Java Code for Creation

class DoublyCircularLinkedList {
    class Node {
        int data;
        Node next, prev;
        Node(int data) {
            this.data = data;
            this.next = this.prev = null;
        }
    }

    Node head;

    // Function to create the list
    public void createList(int data) {
        Node newNode = new Node(data);
        head = newNode;
        newNode.next = head;
        newNode.prev = head;
    }

    // Function to display the list
    public void display() {
        if (head == null) {
            System.out.println("List is empty.");
            return;
        }
        Node temp = head;
        do {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        } while (temp != head);
        System.out.println("(head)");
    }

    public static void main(String[] args) {
        DoublyCircularLinkedList list = new DoublyCircularLinkedList();
        list.createList(10);
        list.display();
    }
}

C++ Code for Creation

#include <iostream>
using namespace std;

class DoublyCircularLinkedList {
    struct Node {
        int data;
        Node *next, *prev;
        Node(int data) {
            this->data = data;
            this->next = this->prev = nullptr;
        }
    };

public:
    Node *head;

    // Constructor to create the list
    DoublyCircularLinkedList() {
        head = nullptr;
    }

    // Function to create the list
    void createList(int data) {
        Node *newNode = new Node(data);
        head = newNode;
        newNode->next = head;
        newNode->prev = head;
    }

    // Function to display the list
    void display() {
        if (head == nullptr) {
            cout << "List is empty." << endl;
            return;
        }
        Node *temp = head;
        do {
            cout << temp->data << " -> ";
            temp = temp->next;
        } while (temp != head);
        cout << "(head)" << endl;
    }
};

int main() {
    DoublyCircularLinkedList list;
    list.createList(10);
    list.display();
    return 0;
}

2. Traversal of Doubly Circular Linked List

Traversal in a doubly circular linked list can be done in both forward and backward directions. Since the list is circular, we can start at any node and visit all nodes by following the next or previous pointers.

• Forward Traversal:
  Start from the head node.

Traverse using the next pointer until you reach the head again.

• Backward Traversal:
  Start from the last node (which can be found by accessing the previous pointer of the head).

Traverse using the previous pointer until you reach the head node again.

Note: The traversal code is already included in the above examples (C, Java, C++) as display function.

3. Insertion Operations

Insertion at Beginning

To insert at the beginning of the doubly circular linked list:

• Create a new node.

• Point the new node's next pointer to the head and its previous pointer to the tail.

• Update the previous head's previous pointer to the new node.

• Set the head pointer to the new node.

C Code for Insertion at Beginning:

void insertAtBeginning(struct Node **head, int data) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    if (*head == NULL) {
        *head = newNode;
        newNode->next = newNode;
        newNode->prev = newNode;
    } else {
        struct Node *tail = (*head)->prev;
        newNode->next = *head;
        newNode->prev = tail;
        (*head)->prev = newNode;
        tail->next = newNode;
        *head = newNode;
    }
}

Java code for Insertion at Beginning:

public void insertAtBeginning(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;
        newNode.next = head;
        newNode.prev = head;
    } else {
        Node tail = head.prev;
        newNode.next = head;
        newNode.prev = tail;
        head.prev = newNode;
        tail.next = newNode;
        head = newNode;
    }
}

C++ code for Insertion at Beginning:

void insertAtBeginning(int data) {
    Node *newNode = new Node(data);
    if (head == nullptr) {
        head = newNode;
        newNode->next = head;
        newNode->prev = head;
    } else {
        Node *tail = head->prev;
        newNode->next = head;
        newNode->prev = tail;
        head->prev = newNode;
        tail->next = newNode;
        head = newNode;
    }
}

Insertion at End

To insert at the end:

• Create a new node.

• Point the new node’s next pointer to the head and its previous pointer to the current tail.

• Update the tail’s next pointer to the new node and the head’s previous pointer to the new node.

C code for Insertion at End:

void insertAtEnd(struct Node *head, int data) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    struct Node *tail = head->prev;
    newNode->data = data;
    newNode->next = head;
    newNode->prev = tail;
    tail->next = newNode;
    head->prev = newNode;
}

Java code for Insertion at End:

public void insertAtEnd(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;
        newNode.next = head;
        newNode.prev = head;
    } else {
        Node tail = head.prev;
        newNode.next = head;
        newNode.prev = tail;
        tail.next = newNode;
        head.prev = newNode;
    }
}

C++ code for Insertion at End:

void insertAtEnd(int data) {
    Node *newNode = new Node(data);
    if (head == nullptr) {
        head = newNode;
        newNode->next = head;
        newNode->prev = head;
    } else {
        Node *tail = head->prev;
        newNode->next = head;
        newNode->prev = tail;
        tail->next = newNode;
        head->prev = newNode;
    }
}

Insertion at Specific Position

• Traverse to the specified position.

• Insert the new node between the current node and its previous node.

C code for Insertion at Specific Position:

void insertAtPosition(struct Node *head, int data, int position) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    struct Node *temp = head;
    newNode->data = data;
    
    for (int i = 1; i < position; i++) {
        temp = temp->next;
    }
    newNode->next = temp->next;
    newNode->prev = temp;
    temp->next->prev = newNode;
    temp->next = newNode;
}

Java code for Insertion at Specific Position:

public void insertAtPosition(int data, int position) {
    Node newNode = new Node(data);
    Node temp = head;
    for (int i = 1; i < position; i++) {
        temp = temp.next;
    }
    newNode.next = temp.next;
    newNode.prev = temp;
    temp.next.prev = newNode;
    temp.next = newNode;
}

C++ code for Insertion at Specific Position:

void insertAtPosition(int data, int position) {
    Node *newNode = new Node(data);
    Node *temp = head;
    for (int i = 1; i < position; i++) {
        temp = temp->next;
    }
    newNode->next = temp->next;
    newNode->prev = temp;
    temp->next->prev = newNode;
    temp->next = newNode;
}

4. Deletion Operations

Deletion at Beginning

To delete the node at the beginning:

• Update the head pointer to the next node.

• Adjust the previous pointer of the new head and the next pointer of the last node.

C code for Deletion at Beginning:

void deleteAtBeginning(struct Node **head) {
    if (*head == NULL) return;
    
    struct Node *temp = *head;
    struct Node *tail = (*head)->prev;
    
    if (*head == (*head)->next) {
        free(temp);
        *head = NULL;
    } else {
        tail->next = (*head)->next;
        (*head)->next->prev = tail;
        *head = (*head)->next;
        free(temp);
    }
}

Java code for Deletion at Beginning:

public void deleteAtBeginning() {
    if (head == null) return;
    
    if (head.next == head) {
        head = null;
    } else {
        Node tail = head.prev;
        head = head.next;
        head.prev = tail;
        tail.next = head;
    }
}

C++ code for Deletion at Beginning:

void deleteAtBeginning() {
    if (head == nullptr) return;
    
    if (head->next == head) {
        delete head;
        head = nullptr;
    } else {
        Node *tail = head->prev;
        head = head->next;
        head->prev = tail;
        tail->next = head;
        delete tail;
    }
}

Deletion at End

To delete the node at the end:

• Update the previous pointer of the head node and the next pointer of the second-last node.

C Code for Deletion at End:

void deleteAtEnd(struct Node *head) {
    if (head == NULL) return;
    
    struct Node *tail = head->prev;
    struct Node *secondLast = tail->prev;
    
    secondLast->next = head;
    head->prev = secondLast;
    free(tail);
}

Java code for Deletion at End:

public void deleteAtEnd() {
    if (head == null) return;
    
    Node tail = head.prev;
    if (tail == head) {
        head = null;
    } else {
        Node secondLast = tail.prev;
        secondLast.next = head;
        head.prev = secondLast;
    }
}

C++ code for Deletion at End:

void deleteAtEnd() {
    if (head == nullptr) return;
    
    Node *tail = head->prev;
    if (tail == head) {
        delete head;
        head = nullptr;
    } else {
        Node *secondLast = tail->prev;
        secondLast->next = head;
        head->prev = secondLast;
        delete tail;
    }
}

Deletion at Specific Position

• Traverse to the specified position.

• Update the next pointer of the previous node and the previous pointer of the next node.

C code for Deletion at Specific Position:

void deleteAtPosition(struct Node *head, int position) {
    struct Node *temp = head;
    
    for (int i = 1; i < position; i++) {
        temp = temp->next;
    }
    
    temp->prev->next = temp->next;
    temp->next->prev = temp->prev;
    free(temp);
}

Java code for Deletion at Specific Position:

public void deleteAtPosition(int position) {
    if (head == null) return;
    
    Node temp = head;
    for (int i = 1; i < position; i++) {
        temp = temp.next;
    }
    temp.prev.next = temp.next;
    temp.next.prev = temp.prev;
}

C++ code for Deletion at Specific Position:

void deleteAtPosition(int position) {
    if (head == nullptr) return;
    
    Node *temp = head;
    for (int i = 1; i < position; i++) {
        temp = temp->next;
    }
    temp->prev->next = temp->next;
    temp->next->prev = temp->prev;
    delete temp;
}

Conclusion

The Doubly Circular Linked List is a powerful data structure with the ability to traverse in both directions and maintain a circular connection between the first and last nodes. This makes it ideal for tasks that require cyclic operations, like round-robin scheduling or circular buffers. Understanding and implementing this data structure will help you develop more advanced and efficient algorithms.

For more such content, click here

Until then,

Happy Coding!