Reverses the Doubly Circular Linked List

A doubly circular linked list is a type of linked list where each node contains a data part and two pointers: one pointing to the next node and one pointing to the previous node. Additionally, the last node is linked back to the first node, forming a circular structure.

Reversing a doubly circular linked list means changing the direction of all the links so that the first node becomes the last, the last becomes the first, and the traversal order is reversed. In simple words, the next and previous pointers of each node are swapped, but the circular nature of the list is maintained. This operation is useful when we need to traverse or process the list in the opposite order without creating a new list.

• Original list: A ↔ B ↔ C ↔ D ↔ A
• Reversed list: A ↔ D ↔ C ↔ B ↔ A

Reversing is usually done in-place, meaning no extra memory is needed apart from temporary pointers, making it efficient.

Algorithm to Reverse a Doubly Circular Linked List

1. Check if the List is Empty or Has Only One Node:
   • If the head pointer is NULL or the list has only one node (head->next is head), no action is needed as the list is either empty or already in its reversed state.
2. Traverse and Reverse:
   • Start from the head of the list.
   • In each iteration, swap the next and prev pointers of the current node.
   • Move to the original prev node (which is now the next node after swapping).
   • Continue this process for each node in the list.
3. Update Head:
   • Once all nodes have been visited and swapped, update the head of the list to the last node visited.
4. Completion:
   • The list is now reversed, with the order of elements flipped.

Example Scenario

• Given List: A DCLL with elements: 10, 20, 30, 40.
• Task: Reverse the order of the nodes in the list.

Visualization and Steps

Initial State of the List

• List: head -> [10] <-> [20] <-> [30] <-> [40] <-> back to [10]

Step 1: Check if the List is Empty or Has Only One Node

• Check: The head is not NULL, and the list has more than one node (head->next is not head).
• Action: Proceed to reversal since the list is neither empty nor has only one node.

Step 2: Traverse and Reverse

• Process:
  • First Node [10]:
    • Swap next and prev. Now, [10]->next points to [40] and [10]->prev points to [20].
    • Move to the original prev node, which is [20].
  • Second Node [20]:
    • Swap next and prev. [20]->next points to [10] and [20]->prev points to [30].
    • Move to [30].
  • Third Node [30]:
    • Swap. [30]->next points to [20] and [30]->prev points to [40].
    • Move to [40].
  • Fourth Node [40]:
    • Swap. [40]->next points to [30] and [40]->prev points to [10].
    • Complete the cycle back at [40].

Step 3: Update Head

• Action: Update head to the last node visited, which is [40].

Completion

• Final State of the List: head -> [40] <-> [30] <-> [20] <-> [10] <-> back to [40]
• Outcome: The list is now reversed.

Conclusion

• Result: The nodes in the list are now in the reverse order: 40, 30, 20, 10.
• List Integrity: The circular and doubly linked nature of the list is preserved.

Program to Reverses the Doubly Circular Linked List

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

// Define the structure of a node
typedef struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = newNode;
    newNode->prev = newNode;
    return newNode;
}

// Function to insert a node at the end
void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* last = (*head)->prev;
        newNode->next = *head;
        newNode->prev = last;
        last->next = newNode;
        (*head)->prev = newNode;
    }
}

// Function to reverse the doubly circular linked list
void reverseDCLL(Node** head) {
    if (*head == NULL || (*head)->next == *head) {
        return; // Empty or single-node list
    }

    Node* current = *head;
    Node* temp = NULL;

    // Loop through all nodes and swap next and prev
    do {
        temp = current->next;
        current->next = current->prev;
        current->prev = temp;
        current = temp;
    } while (current != *head);

    // Update head to the new first node (previous tail)
    *head = (*head)->next;
}


// Function to print the list
void printDCLL(Node* head) {
    if (!head) {
        printf("Doubly Circular Linked List is empty.\n");
        return;
    }

    Node* temp = head;
    printf("Doubly Circular Linked List: ");
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("\n");
}

// Main function to test the implementation
int main() {
    Node* head = NULL;

    // Insert elements
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtEnd(&head, 40);
    insertAtEnd(&head, 50);
    insertAtEnd(&head, 60);

    // Print before reversing
    printf("Before Reversing:\n");
    printDCLL(head);

    // Reverse and print again
    reverseDCLL(&head);
    printf("After Reversing:\n");
    printDCLL(head);

    return 0;
}

Output

Before Reversing:
Doubly Circular Linked List: 10 20 30 40 50 60 
After Reversing:
Doubly Circular Linked List: 60 50 40 30 20 10 

Explanation of Code

Structure Definition

typedef struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
} Node;

The above code defines a node for a doubly circular linked list. Each node contains three parts: a data field to store the value, a next pointer to point to the next node in the list, and a prev pointer to point to the previous node. By linking nodes this way, we can traverse the list both forward and backward. In a doubly circular linked list, the last node’s next points to the first node, and the first node’s prev points to the last node, creating a continuous circular structure.

 Creating a Node

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = newNode;
    newNode->prev = newNode;
    return newNode;
}

The function createNode creates a new node for a doubly circular linked list. It first allocates memory for the node using malloc. Then, it sets the data field to the value provided. Since this node is initially alone in the list, both its next and prev pointers are set to point to itself, maintaining the circular structure. Finally, the function returns a pointer to this newly created node, ready to be inserted into the list.

 Inserting at the End

void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* last = (*head)->prev;
        newNode->next = *head;
        newNode->prev = last;
        last->next = newNode;
        (*head)->prev = newNode;
    }
}

The above function inserts a new node at the end of a doubly circular linked list. It first creates a new node with the given data. If the list is empty, the new node becomes the head. If the list is not empty, it finds the last node and updates the pointers so that the new node is added at the end: its next points to the head, its prev points to the last node, the last node’s next points to the new node, and the head’s prev points to the new node. This way, the circular and doubly-linked structure of the list is maintained.

Reversing the List

void reverseDCLL(Node** head) {
    if (*head == NULL || (*head)->next == *head) return;

    Node* current = *head;
    Node* temp = NULL;

    do {
        temp = current->next;
        current->next = current->prev;
        current->prev = temp;
        current = temp;
    } while (current != *head);

    *head = (*head)->next;
}

The above function reverses a doubly circular linked list. It first checks if the list is empty or has only one node; in that case, no reversal is needed. Then, starting from the head, it goes through each node and swaps the next and prev pointers, effectively reversing the direction of the list. The loop continues until it comes back to the original head, ensuring all nodes are reversed. Finally, the head pointer is updated to the new first node (which was previously the last node), so the list can be traversed correctly in the reversed order while still maintaining its circular structure.

Printing the List

void printDCLL(Node* head) {
    if (!head) {
        printf("Doubly Circular Linked List is empty.\n");
        return;
    }

    Node* temp = head;
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("\n");
}

The above function prints all the elements of a doubly circular linked list. First, it checks if the list is empty; if so, it prints a message and exits. Otherwise, it starts from the head and traverses the list using the next pointer. It prints the data of each node and continues until it reaches the head again, ensuring that all nodes in the circular list are printed exactly once. This allows you to see the values stored in the list in their current order.

Time & Space Complexity

Time Complexity

Space Complexity