Reverses the Doubly Circular Linked List

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