Circular Singly Linked List

A circular singly linked list is a variation of a singly linked list where the last node points back to the first node, forming a circular structure. It is a linear data structure consisting of a sequence of elements, called nodes, where each node points to the next node in the sequence. Unlike arrays, elements in a linked list are not stored in contiguous memory locations. Each node contains two fields:

• Data: The value or information stored in the node.
• Next Pointer: A reference (or pointer) to the next node in the sequence. In the case of the last node, the next pointer points back to the first node.

The circular singly linked list forms a linear collection of elements where each node points to its successor, and the last node points back to the first node, creating a circular structure. It is a dynamic data structure, meaning it can grow or shrink in size during runtime, as nodes can be added or removed without requiring memory to be reallocated.

The head is the first node in the list, and it serves as the entry point for traversing the list. In a circular singly linked list, the last node points back to the head, forming a loop. If the list is empty, the head points to NULL.

Unlike arrays that have a fixed size, a circular singly linked list dynamically allocates memory for each node when it is created. This means the size of the list can grow or shrink as nodes are added or removed at runtime.

Insertions and deletions of nodes, particularly at the beginning or middle of the list, are more efficient compared to arrays since you do not need to shift elements.

Circular singly linked lists can be traversed in a loop starting from the head and continuing back to the head after reaching the tail. However, there is no way to traverse backward, which can be a limitation in some use cases.

The nodes in a circular singly linked list do not need to be stored in contiguous memory locations, unlike arrays. Each node is linked to the next through pointers, and they can be located anywhere in memory.

The size of the linked list is not fixed, and it is determined by the number of nodes present in the list at any given time. This makes it more flexible for applications where the number of elements is unknown or changes frequently.

Each node in a circular singly linked list requires extra memory for the pointer (next reference), which slightly increases memory usage compared to arrays.

The last node in a circular singly linked list points back to the head, instead of having its next pointer set to NULL.

Here's a visual representation of a circular singly linked list:

Head -> [Data | Next] -> [Data | Next] -> [Data | Next] -> Head

In the above representation:

• The Head points to the first node of the list.
• Each node contains Data and a Next pointer to the next node.
• The last node's Next pointer points back to the Head, indicating the circular structure.

A simple circular singly linked list with three nodes could look like this:

Head -> [10 | Next] -> [20 | Next] -> [30 | Next] -> Head

In the above example:

• The Head points to the first node containing the data 10.
• The second node contains the data 20 and points to the third node.
• The third node contains the data 30 and points back to the Head, indicating the circular structure of the list.

Here's a detailed breakdown of common circular singly linked list operations:

• insertAtBeginning():
  
  • Description: Inserts a new node at the start (or head) of a circular singly linked list.
  • Example:
    • Suppose you have the following circular singly linked list:
      

      Head -> [10 | Next] -> [20 | Next] -> [30 | Next] -> Head

    • You want to insert the value 5 at the beginning of the list. After calling insertAtBeginning(), the list becomes:
      

      Head -> [5 | Next] -> [10 | Next] -> [20 | Next] -> [30 | Next] -> Head

  • Time complexity: The time complexity of inserting a node at the beginning of a circular singly linked list is \(O(1)\) (constant time). The following steps are performed:
    
    • Create a new node.
    • If the list is not empty, set the next pointer of the new node to point to the current head node (the first node in the list). If the list is empty, set the next pointer of the new node to point to itself, creating a circular structure.
    • Update the head pointer to point to the new node.
    • If the list is not empty, the last node's next pointer should be updated to point to the new head.
    
    Since no traversal is required, this operation takes constant time, \(O(1)\).
  • Space complexity: The space complexity of inserting a node at the beginning of a circular singly linked list is \(O(1)\) (constant space). The space required to allocate the new node is a fixed amount and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
• insertAtEnd():
  
  • Description: Inserts a new node at the end (or tail) of a circular singly linked list.
  • Example:
    • Suppose you have the following circular singly linked list:
      

      Head -> [10 | Next] -> [20 | Next] -> [30 | Next] -> Head

    • You want to insert the value 40 at the end of the list. After calling insertAtEnd(), the list becomes:
      

      Head -> [10 | Next] -> [20 | Next] -> [30 | Next] -> [40 | Next] -> Head

  • Time complexity: The time complexity of inserting a node at the end of a circular singly linked list is \(O(n)\) (linear time) in the general case.
    
    • Best Case (Empty List): If the list is empty, inserting a new node at the end is the same as inserting at the beginning. The following steps are performed:
      
      • Create a new node.
      • Set the next pointer of the new node to point to itself, as it will be the only node in the list.
      • Update the head pointer to point to the new node.
      
      Since no traversal is required, this operation takes constant time, \(O(1)\).
    • Average/Worst Case (Non-Empty List): If the list is not empty, you have to traverse the entire list to reach the last node. The following steps are performed:
      • Start from the head node.
      • Traverse the list by following the next pointers until you reach the last node (the node whose next pointer points to the head).
      • Create a new node.
      • Set the next pointer of the new node to point to the head.
      • Update the next pointer of the last node to point to the new node.
      
      The traversal takes \(O(n)\) time, where \(n\) is the number of nodes in the list. Updating the pointer takes \(O(1)\).
  • Space complexity: The space complexity of inserting a node at the end of a circular singly linked list is \(O(1)\) (constant space). The space required to allocate the new node is a fixed amount and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
• insertAfterNode():
  
  • Description: Inserts a new node in a singly linked list immediately after a given node. If the target node doesn't exist, you may opt to do nothing and just return control to the caller without modifying the list.
  • Example:
    • Suppose you have the following linked list:
      

      Head -> [10 | Next] -> [20 | Next] -> [30 | NULL]

    • You want to insert the value 25 after the node containing 20. After calling insertAfterNode(), the list becomes:
      

      Head -> [10 | Next] -> [20 | Next] -> [25 | Next] -> [30 | NULL]

  • Time complexity: The time complexity for inserting a node after a node in a singly linked list is \(O(1)\) (constant time). The following steps are performed:
    
    • Create a new node.
    • Set the next pointer of the new node to point to the node that follows the given node.
    • Update the next pointer of the given node to point to the new node.
    
    Since no traversal is required, this operation takes constant time, \(O(1)\).
  • Space complexity: The space complexity for inserting a node after a node in a singly linked list is \(O(1)\) (constant time). The space required to allocate the new node is a fixed amount and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
• insertAfterNode():
  
  • Description: Inserts a new node in a circular singly linked list immediately after a given node. If the target node doesn't exist, the function does nothing and simply returns control to the caller without modifying the list.
  • Example:
    • Suppose you have the following circular singly linked list:
      

      Head -> [10 | Next] -> [20 | Next] -> [30 | Next] > Head

    • You want to insert the value 25 after the node containing 20. After calling insertAfterNode(), the list becomes:
      

      Head -> [10 | Next] -> [20 | Next] -> [25 | Next] -> [30 | Next] -> Head

  • Time complexity: The time complexity for inserting a node after a given node in a circular singly linked list is \(O(1)\) (constant time). The following steps are performed:
    
    • Create a new node.
    • Set the next pointer of the new node to point to the node that follows the given node.
    • Update the next pointer of the given node to point to the new node.
    
    Since no traversal is required, this operation takes constant time, \(O(1)\).
  • Space complexity: The space complexity for inserting a node after a node in a circular singly linked list is \(O(1)\) (constant time). The space required to allocate the new node is a fixed amount and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
• insertAtPosition():
  
  • Description: Inserts a new node at a specified position in a circular singly linked list. Positions are usually indexed starting from 0 or 1. If the position is 1 (or 0, based on indexing), this implies insertion at the beginning of the list. If the position is greater than the size of the list or less than 1, the function may return an error or take no action since the insertion would be out of range.
  • Example:
    • Suppose you have the following circular singly linked list:
      

      Head -> [10 | Next] -> [20 | Next] -> [30 | Next] > Head

    • You want to insert a new node with value 35 at position 3. After calling insertAtPosition(), the list becomes:
      

      Head -> [10 | Next] -> [20 | Next] -> [35 | Next] -> [30 | Next] -> Head

  • Time complexity: The time complexity for inserting a new node at a specified position in a circular singly linked list is \(O(n)\) (linear time). The following steps are performed:
    
    • Create a new node.
    • Locate the preceding node (the node whose next pointer points to the target position).
    • Update the next pointer of the new node to point to the next node in the sequence.
    • Update the next pointer of the preceding node to point to the new node.
    
    The traversal takes \(O(n)\) time, where \(n\) is the number of nodes in the list. Updating the pointers takes \(O(1)\).
  • Space complexity: The space complexity of inserting a new node at a specified position in a circular singly linked list is \(O(1)\) (constant space). The space required to allocate the new node is a fixed amount and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
• deleteAtBeginning():
  
  • Description: Removes a node at the start (or head) of a circular singly linked list. If the list is empty, it prints a message "List is empty" and returns, since there is no node to delete.
  • Example:
    • Suppose you have the following circular singly linked list:
      

      Head -> [10 | Next] -> [20 | Next] -> [30 | Next] > Head

    • You want to delete the value 10 at the beginning of the list. After calling deleteAtBeginning(), the list becomes:
      

      Head -> [20 | Next] -> [30 | Next]-> Head

  • Time complexity: The time complexity for removing a node at the beginning of a circular singly linked list is \(O(1)\) (constant time). The following steps are performed:
    
    • If the list is empty, return.
    • If there is only one node, set the head to NULL (empty list).
    • Otherwise:
      • Find the last node in the list (the node pointing to head).
      • Update the last node's next pointer to point to the second node.
      • Set the head pointer to the second node.
      • Deallocate the memory of the old head node.
    Since no traversal is required in the case of a one-node list, and only a single traversal is required for a multi-node list, this operation still takes \(O(1)\) on average.
  • Space complexity: The space complexity for removing a node at the beginning of a circular singly linked list is \(O(1)\) (constant space). Only a fixed amount of space is used to store references to the head node and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
• deleteAtEnd():
  
  • Description: Removes a node at the end (or tail) of a circular singly linked list. If the list is empty, it prints a message "List is empty" and returns, since there is no node to delete.
  • Example:
    • Suppose you have the following circular singly linked list:
      

      Head -> [10 | Next] -> [20 | Next] -> [30 | Next] > Head

    • You want to remove the value 30 at the end of the list. After calling deleteAtEnd(), the list becomes:
      

      Head -> [10 | Next] -> [20 | Next] -> Head

  • Time complexity: The time complexity for removing a node at the end of a circular singly linked list is \(O(n)\) (linear time). The following steps are performed:
    
    • If the list is empty, return.
    • If there is only one node, set the head to NULL (empty list).
    • Otherwise:
      • Start from the head node.
      • Traverse the list to find the second-to-last node (the node whose next pointer points to the last node).
      • Update the next pointer of the second-to-last node to point to the head, maintaining the circular structure.
      • Deallocate the memory for the old last node.
    Since traversal is required to reach the second-to-last node, the worst-case time complexity is \(O(n)\), where \(n\) is the number of nodes in the list.
  • Space complexity: The space complexity for removing a node at the end of a circular singly linked list is \(O(1)\) (constant space). Only a fixed amount of space is used to store references and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
• deleteAtPosition():
  
  • Description: Removes a node at a specified position in a circular singly linked list. Positions are usually indexed starting from 0 or 1. If the position is 0 (or 1, based on indexing), it means the head node should be removed. If the specified position is out of bounds, a message is printed, and no changes are made to the list.
  • Example:
    • Suppose you have the following circular singly linked list:
      

      Head -> [10 | Next] -> [20 | Next] -> [30 | Next] > Head

    • You want to remove the node at position 2. After calling deleteAtPosition(), the list becomes:
      

      Head -> [10 | Next] -> [30 | Next] -> Head

  • Time complexity: The time complexity for removing a node at a specified position in a circular singly linked list is \(O(n)\) (linear time). The following steps are performed:
    
    • If the list is empty, return.
    • If the position is 0 (or 1, based on indexing), remove the head node:
      • If there is only one node, set head = NULL.
      • Otherwise, find the last node (the node whose next points to the head).
      • Update the head pointer to the next node.
      • Update the last node's next pointer to point to the new head.
      • Deallocate the memory of the removed node.
    • If the position is greater than 0, traverse the list to find the node before the target node.
    • Update its next pointer to skip the target node and point to the node after it.
    • Deallocate the memory of the removed node.
    Since traversal is required to reach the node before the target, the worst-case time complexity is \(O(n)\), where \(n\) is the number of nodes in the list.
  • Space complexity: The space complexity for removing a node at a specified position in a circular singly linked list is \(O(1)\) (constant space). Only a fixed amount of space is used to store references, and it does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
• traverse():
  
  • Description: Visits each node in a circular singly linked list and performs an action, such as printing the node's value. Unlike a singly linked list, traversal starts at the head and continues until the head is encountered again, ensuring the circular structure is maintained.
  • Time complexity: The time complexity of the traverse() function in a circular singly linked list is \(O(n)\) (linear time). The function iterates through each node exactly once, from the head back to the head. Since every node is visited once, the number of operations performed is directly proportional to the number of nodes.
  • Space complexity: The space complexity of the traverse() function in a circular singly linked list is \(O(1)\) (constant space). The function only uses a constant amount of space to store variables such as the current node reference during the traversal. Regardless of the size of the linked list, the amount of extra space used does not change.
• reverse():
  
  • Description: Reverses the order of nodes in a circular singly linked list. Unlike a regular singly linked list, the last node's next pointer must be correctly updated to point to the new head, ensuring the circular structure is maintained.
  • Example:
    • Suppose you have the following circular linked list:
      

      Head -> [10 | Next] -> [20 | Next] -> [30 | Next] -> Head

    • After calling reverse(), the list becomes:
      

      Head -> [30 | Next] -> [20 | Next] -> [10 | Next] -> Head

  • Time complexity: The time complexity of the reverse() function in a circular singly linked list is \(O(n)\) (linear time). The function traverses each node exactly once and updates pointers accordingly.
  • Space complexity: The space complexity of the reverse() function in a circular singly linked list is \(O(1)\) (constant space). The function only uses a fixed amount of extra space for variables, such as pointers for the current, previous, and next nodes, regardless of the list size.
• search():
  
  • Description: Finds whether a specific element (or key) exists in a circular singly linked list. Unlike a regular singly linked list, the traversal must stop when the search wraps around back to the head, ensuring we do not loop indefinitely.
  • Time complexity: The time complexity of the search() function in a circular singly linked list is \(O(n)\) (linear time). The function may need to examine every node in the list before finding the key (or determining that it is not present).
  • Space complexity: The space complexity of the search() function in a circular singly linked list is \(O(1)\) (constant space). The function only uses a fixed amount of extra space to store variables, such as a pointer to the current node. No additional data structures are used.
• size():
  
  • Description: Calculates and returns the number of nodes in a circular singly linked list. Unlike a regular singly linked list, traversal must stop when the function loops back to the head to avoid infinite loops.
  • Time complexity: The time complexity of the size() function in a circular singly linked list is \(O(n)\) (linear time). The function traverses the entire linked list once to count the number of nodes, where \(n\) is the number of nodes in the list.
  • Space complexity: The space complexity of the size() function in a circular singly linked list is \(O(1)\) (constant space). The function uses only a fixed amount of extra space for variables, regardless of the size of the list.
• get():
  
  • Description: Retrieves the value of a node in a circular singly linked list at a specified index. Since the list is circular, traversal stops when the head is encountered again. If the index is out of range, a message is printed indicating that the index is invalid.
  • Time complexity: The time complexity of the get() function in a circular singly linked list is \(O(n)\) (linear time). The function traverses the list until it reaches the specified index, stopping if it loops back to the head before finding the index.
  • Space complexity: The space complexity of the get() function in a circular singly linked list is \(O(1)\) (constant space). The function only uses a fixed amount of extra space for variables, regardless of the list size.
• set():
  
  • Description: Updates the value of a node at a specified index in a circular singly linked list. Since the list is circular, traversal stops when the head is encountered again. If the index is out of range, a message is printed indicating that the index is invalid.
  • Time complexity: The time complexity of the set() function in a circular singly linked list is \(O(n)\) (linear time). The function traverses the list until it reaches the specified index, stopping if it loops back to the head before finding the index.
  • Space complexity: The space complexity of the set() function in a circular singly linked list is \(O(1)\) (constant space). The function only uses a fixed amount of extra space for variables, regardless of the list size.
• isEmpty():
  
  • Description: Checks whether a circular singly linked list is empty.
  • Time complexity: The time complexity of the isEmpty() function in a circular singly linked list is \(O(1)\) (constant time). The function only checks if the head pointer is NULL, which takes constant time.
  • Space complexity: The space complexity of the isEmpty() function in a circular singly linked list is \(O(1)\) (constant space). The function does not use any additional memory beyond a single pointer check.
• merge():
  
  • Description: Combines two sorted circular singly linked lists into a single sorted circular singly linked list while maintaining circularity.
  • Time complexity: The time complexity of the merge() function in a circular singly linked list is \(O(n + m)\) (linear time). Each node from both lists is visited exactly once, and linking operations are performed in constant time. Where \(n\) is the number of nodes in the first circular linked list and \(m\) is the number of nodes in the second circular linked list.
  • Space complexity: The space complexity of the merge() function in a circular singly linked list is \(O(1)\) (constant space). The function uses a fixed number of pointers without any additional data structures, ensuring that the space required does not depend on the size of the input lists.
• sort():
  
  • Description: Arranges the elements of a circular singly linked list in a specific order (typically ascending or descending) while maintaining its circular nature.
  • Time complexity: The time complexity of the sort() function in a circular singly linked list, when using merge sort, is \(O(n \log n)\) (linearithmic time). The algorithm recursively divides the list into halves and requires \(O(n)\) time to merge them back together. The logarithmic factor \(\log n\) results from the number of times the list is split in half.
  • Space complexity: The space complexity of the sort() function in a circular singly linked list, using Merge Sort, is \(O(\log n)\) (logarithmic space) due to recursion depth. If implemented iteratively, space complexity can be reduced to \(O(1)\), ensuring no extra space is used beyond a few pointers.
• clear():
  
  • Description: Removes all nodes from a circular singly linked list, freeing up the memory they occupy and making the list empty. The head pointer is set to NULL, breaking the circular link.
  • Time complexity: The time complexity of the clear() function in a circular singly linked list is \(O(n)\) (linear time). The function traverses the list once, freeing each node's memory.
  • Space complexity: The space complexity of the clear() function in a circular singly linked list is \(O(1)\) (constant space). The function only uses a fixed amount of space for temporary pointers during traversal, regardless of the list size.

Non-Generic Circular Singly Linked List Implementation

Here is the Non-Generic circular singly linked list implementation in C:

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

// Defines a structure to represent a node in a circular singly linked list
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = newNode;  // Points to itself initially (circular behavior)
    return newNode;
}

// Function to insert a node at the beginning of the list
void insertAtBeginning(Node** headRef, int data) {
    Node* newNode = createNode(data);
    if (*headRef == NULL) {
        *headRef = newNode;
    } else {
        Node* temp = *headRef;
        while (temp->next != *headRef) {  // Traverse until we find the last node
            temp = temp->next;
        }
        temp->next = newNode;  // Update last node's next to new node
        newNode->next = *headRef;  // New node points to head
        *headRef = newNode;  // Update head
    }
}

// Function to insert a node at the end of the list
void insertAtEnd(Node** headRef, int data) {
    if (*headRef == NULL) {
        *headRef = createNode(data);
    } else {
        Node* temp = *headRef;
        while (temp->next != *headRef) {  // Traverse until we find the last node
            temp = temp->next;
        }
        Node* newNode = createNode(data);
        temp->next = newNode;
        newNode->next = *headRef;  // Make the new node point to the head
    }
}

// Function to insert a new node after a given previous node
void insertAfterNode(Node* prevNode, int data) {
    if (prevNode == NULL) {
        printf("The given previous node cannot be NULL.\n");
        return;
    }
    
    Node* newNode = createNode(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

// Function to insert a node before a given next node
void insertBeforeNode(Node** headRef, Node* nextNode, int data) {
    if (*headRef == NULL) {
        printf("The list cannot be empty\n");
        return;
    }

    if (nextNode == NULL) {
        printf("The given next node cannot be NULL\n");
        return;
    }

    Node* newNode = createNode(data);
    
    if (*headRef == nextNode) {  // If the nextNode is the head, insert at beginning
        insertAtBeginning(headRef, data);
        return;
    }

    Node* temp = *headRef;
    while (temp != NULL && temp->next != nextNode) {
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("The given next node is not found in the list\n");
        free(newNode);
        return;
    }

    newNode->next = temp->next;
    temp->next = newNode;
}

// Function to insert a node at a specific position (0-based index)
void insertAtPosition(Node** headRef, int data, int position) {
    Node* newNode = createNode(data);
    
    if (position == 0) {  // Insert at the beginning
        insertAtBeginning(headRef, data);
        return;
    }

    Node* temp = *headRef;
    for (int i = 0; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("Position out of bounds\n");
        free(newNode);
        return;
    }

    newNode->next = temp->next;
    temp->next = newNode;
}

// Function to delete a node at the beginning of the list
void deleteAtBeginning(Node** headRef) {
    if (*headRef == NULL) {
        printf("List is empty\n");
        return;
    }
    
    Node* temp = *headRef;
    if (temp->next == *headRef) {  // If there's only one node
        free(temp);
        *headRef = NULL;
        return;
    }

    // Traverse to the last node
    Node* last = *headRef;
    while (last->next != *headRef) {
        last = last->next;
    }

    last->next = (*headRef)->next;  // Last node's next points to second node
    *headRef = (*headRef)->next;  // Update head
    free(temp);
}

// Function to delete a node at the end of the list
void deleteAtEnd(Node** headRef) {
    if (*headRef == NULL) {
        printf("List is empty\n");
        return;
    }

    Node* temp = *headRef;
    if (temp->next == *headRef) {  // Only one node
        free(temp);
        *headRef = NULL;
        return;
    }

    // Traverse to the second last node
    Node* last = *headRef;
    while (last->next != *headRef) {
        last = last->next;
    }

    // Delete last node
    Node* secondLast = *headRef;
    while (secondLast->next != last) {
        secondLast = secondLast->next;
    }

    secondLast->next = *headRef;  // Second last node points to head
    free(last);
}

// Function to delete a node at a specific position (0-based index) in a circular singly linked list
void deleteAtPosition(Node** headRef, int position) {
    if (*headRef == NULL) {
        printf("List is empty\n");
        return;
    }

    Node* temp = *headRef;

    // If the position is 0, we need to delete the head
    if (position == 0) {
        // If there is only one node in the list
        if (temp->next == *headRef) {
            free(temp);
            *headRef = NULL;
            return;
        }

        // Traverse to the last node
        Node* last = *headRef;
        while (last->next != *headRef) {
            last = last->next;
        }

        // Update the head and unlink the node
        last->next = temp->next;
        *headRef = temp->next;
        free(temp);
        return;
    }

    // Find the previous node of the node to be deleted
    for (int i = 0; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
        if (temp == *headRef) {
            // If we have reached the head again, the position is out of bounds
            printf("Position out of bounds\n");
            return;
        }
    }

    // If position is more than number of nodes or temp is NULL
    if (temp == NULL || temp->next == *headRef) {
        printf("Position out of bounds\n");
        return;
    }

    // Node temp->next is the node to be deleted
    Node* nodeToDelete = temp->next;
    temp->next = nodeToDelete->next; // Unlink the node from the list
    free(nodeToDelete); // Free the memory of the deleted node
}

// Function to traverse the circular list and print all elements
void traverse(Node* head) {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }

    Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);  // Stop when we reach the head again
    printf("(head)\n");
}

// Function to search for an element in the list
int search(Node* head, int key) {
    if (head == NULL) return 0;

    Node* temp = head;
    do {
        if (temp->data == key)
            return 1;
        temp = temp->next;
    } while (temp != head);
    
    return 0;
}

// Function to get the size of the circular linked list
int size(Node* head) {
    if (head == NULL) return 0;
    
    int size = 1;
    Node* temp = head->next;
    while (temp != head) {
        size++;
        temp = temp->next;
    }
    return size;
}

// Function to check if the list is empty
int isEmpty(Node* head) {
    return head == NULL;
}

// Function to access an element at a specific index (0-based)
int get(Node* head, int index) {
    if (head == NULL) return -1;

    int count = 0;
    Node* temp = head;
    do {
        if (count == index)
            return temp->data;
        count++;
        temp = temp->next;
    } while (temp != head);
    
    return -1; // Index out of range
}

// Function to set an element at a specific index (0-based)
void set(Node* head, int index, int newValue) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }

    int count = 0;
    Node* current = head;
    do {
        if (count == index) {
            current->data = newValue;  // Update the node's value
            return;
        }
        count++;
        current = current->next;
    } while (current != head);
    
    printf("Index out of range\n"); // Handle case where index exceeds list length
}

// Function to reverse the circular linked list
void reverse(Node** headRef) {
    if (*headRef == NULL || (*headRef)->next == *headRef) {
        return;  // No need to reverse for empty or single node
    }

    Node *prev = NULL, *current = *headRef, *next = NULL;
    do {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    } while (current != *headRef);
    
    (*headRef)->next = prev;  // Make the last node point to the new head
    *headRef = prev;
}

// Function to clear the entire circular linked list and free memory
void clear(Node** headRef) {
    if (*headRef == NULL) return;
    
    Node* current = *headRef;
    Node* next;
    do {
        next = current->next;
        free(current);
        current = next;
    } while (current != *headRef);

    *headRef = NULL;
}
// Function to find the middle of a circular singly linked list
void middle(Node** mid, Node* head) {
    if (head == NULL || head->next == head) {
        *mid = head;
        return;
    }

    Node* slow = head;
    Node* fast = head;

    // Move fast two steps and slow one step
    while (fast->next != head && fast->next->next != head) {
        fast = fast->next->next;
        slow = slow->next;
    }

    *mid = slow;
}

// Function to merge two circular linked lists
void merge(Node** headRef, Node* head1, Node* head2) {
    Node* tempHead = NULL, *last = NULL;
    Node* first1 = head1, *first2 = head2;
    
    printf("Starting merge...\n");

    if (head1 == NULL) {
        printf("First list is empty. Returning a new node from the second list.\n");
        Node* newNode = createNode(head2->data); // Create a new node with the data of the first node of head2
        *headRef = newNode; // Set the new node as the head
        head2 = head2->next;
        if (head2 == first2) head2 = NULL; // Handle circular structure
        return;
    }
    if (head2 == NULL) {
        printf("Second list is empty. Returning a new node from the first list.\n");
        Node* newNode = createNode(head1->data); // Create a new node with the data of the first node of head1
        *headRef = newNode; // Set the new node as the head
        head1 = head1->next;
        if (head1 == first1) head1 = NULL; // Handle circular structure
        return;
    }

    printf("Both lists are non-empty. Merging...\n");

    do {
        Node* newNode;
        if (head1 && (head2 == NULL || head1->data <= head2->data)) {
            printf("Adding node from List 1: %d\n", head1->data);
            newNode = createNode(head1->data);
            head1 = head1->next;
            if (head1 == first1) {
                printf("End of List 1 reached.\n");
                head1 = NULL;  // Stop merging this list
            }
        } else {
            printf("Adding node from List 2: %d\n", head2->data);
            newNode = createNode(head2->data);
            head2 = head2->next;
            if (head2 == first2) {
                printf("End of List 2 reached.\n");
                head2 = NULL;
            }
        }

        if (!tempHead) {
            tempHead = newNode;
            printf("New head node created: %d\n", tempHead->data);
        } else {
            last->next = newNode;
        }
        last = newNode;
    } while (head1 != NULL || head2 != NULL);

    // Make the list circular
    last->next = tempHead;
    *headRef = tempHead;
    printf("Merge completed. Circular list created with head: %d\n", (*headRef)->data);
}

// Function to sort a circular singly linked list (Merge Sort)
void sort(Node** headRef) {
    if (*headRef == NULL || (*headRef)->next == *headRef)
        return;

    Node* head = *headRef;
    Node* mid = NULL;
    middle(&mid, head);

    Node* nextToMid = mid->next;
    mid->next = head; // Break circularity for first half
    Node* secondHalf = nextToMid;

    // Find last node of second half
    while (secondHalf->next != head)
        secondHalf = secondHalf->next;
    
    secondHalf->next = nextToMid; // Break circularity for second half

    // Sort both halves
    sort(&head);
    sort(&nextToMid);

    // Merge sorted halves
    merge(headRef, head, nextToMid);
}

// Main function to test the circular linked list operations
int main() {
    Node* list = NULL; // Initialize an empty linked list

    // 1. Insert elements at the beginning
    insertAtBeginning(&list, 5);
    insertAtBeginning(&list, 3);
    insertAtBeginning(&list, 1);

    printf("List after inserting at the beginning: ");
    traverse(list);

    // 2. Insert elements at the end
    insertAtEnd(&list, 7);
    insertAtEnd(&list, 9);

    printf("List after inserting at the end: ");
    traverse(list);

    // 3. Insert element at position 2
    insertAtPosition(&list, 4, 2);

    printf("List after inserting 4 at position 2: ");
    traverse(list);

    // 4. Insert element after the second node
    Node* secondNode = list->next;
    insertAfterNode(secondNode, 6);

    printf("List after inserting 6 after the second node: ");
    traverse(list);

    // 5. Insert element before the node with value 7
    Node* temp = list;
    while (temp != NULL && temp->data != 7) {
        temp = temp->next;
    }
    insertBeforeNode(&list, temp, 8);

    printf("List after inserting 8 before the node with value 7: ");
    traverse(list);

    // 6. Delete the first node
    deleteAtBeginning(&list);

    printf("List after deleting the first node: ");
    traverse(list);

    // 7. Delete the last node
    deleteAtEnd(&list);

    printf("List after deleting the last node: ");
    traverse(list);

    // 8. Delete the node at position 2
    deleteAtPosition(&list, 2);

    printf("List after deleting the node at position 2: ");
    traverse(list);
	
	// 9. Check if list is empty
	if (isEmpty(list)) {
		printf("The list is empty.\n");
	} else {
		printf("The list is not empty.\n");
	}
	
    // 10. Search for an element
    int key = 6;
    if (search(list, key)) {
        printf("Element %d found in the list.\n", key);
    } else {
        printf("Element %d not found in the list.\n", key);
    }

    // 11. Reverse the list
    reverse(&list);

    printf("List after reversing: ");
    traverse(list);

    // 12. Sort the list
    sort(&list);

    printf("List after sorting: ");
    traverse(list);

    // 13. Get the size of the list
    printf("Size of the list: %d\n", size(list));

    // 14. Access an element at a specific index
    int index = 2;
    int value = get(list, index);
    if (value != -1) {
        printf("Element at index %d: %d\n", index, value);
    } else {
        printf("Index %d is out of range.\n", index);
    }

    // 15. Set a new value at a specific index
    set(list, 2, 10);
    printf("List after setting value 10 at index 2: ");
    traverse(list);

    // 16. Clear the list
    clear(&list);

    printf("List after clearing: ");
    traverse(list);

    return 0;
}

Here is the Non-Generic circular singly linked list implementation in C++:

#include <iostream>

using namespace std;

// Node structure for circular singly linked list
struct Node {
    int data;
    Node* next;

    // Constructor to create a new node
    Node(int data) : data(data), next(nullptr) {}
};

// Insert at the beginning
void insertAtBeginning(Node*& head, int data) {
    Node* newNode = new Node(data);
    if (!head) {
        newNode->next = newNode;
        head = newNode;
        return;
    }
    Node* temp = head;
    while (temp->next != head) temp = temp->next;
    temp->next = newNode;
    newNode->next = head;
    head = newNode;
}

// Insert at the end
void insertAtEnd(Node*& head, int data) {
    Node* newNode = new Node(data);
    if (!head) {
        newNode->next = newNode;
        head = newNode;
        return;
    }
    Node* temp = head;
    while (temp->next != head) temp = temp->next;
    temp->next = newNode;
    newNode->next = head;
}

// Delete at the beginning
void deleteAtBeginning(Node*& head) {
    if (!head) {
        cout << "List is empty\n";
        return;
    }
    if (head->next == head) {
        delete head;
        head = nullptr;
        return;
    }
    Node* temp = head;
    while (temp->next != head) temp = temp->next;
    Node* toDelete = head;
    temp->next = head->next;
    head = head->next;
    delete toDelete;
}

// Function to insert a new node after a given previous node
void insertAfterNode(Node* prevNode, int data) {
    if (prevNode == nullptr) {
        cout << "The given previous node cannot be NULL." << endl;
        return;
    }

    Node* newNode = new Node(data);

    // Insert the new node after the previous node
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

// Function to insert a new node before a given next node
void insertBeforeNode(Node*& headRef, Node* nextNode, int data) {
    if (headRef == nullptr) {
        cout << "The list cannot be empty." << endl;
        return;
    }

    if (nextNode == nullptr) {
        cout << "The given next node cannot be NULL." << endl;
        return;
    }

    Node* newNode = new Node(data);

    // If inserting before the head, update head reference
    if (headRef == nextNode) {
        // Find the last node to update its next pointer
        Node* temp = headRef;
        while (temp->next != headRef) {
            temp = temp->next;
        }

        temp->next = newNode; // Update last node's next pointer
        newNode->next = headRef;
        headRef = newNode; // New node becomes the head
        return;
    }

    // Find the node just before nextNode
    Node* temp = headRef;
    while (temp->next != headRef && temp->next != nextNode) {
        temp = temp->next;
    }

    if (temp->next != nextNode) {
        cout << "The given next node is not found in the list." << endl;
        delete newNode;
        return;
    }

    newNode->next = temp->next;
    temp->next = newNode;
}

// Function to insert at a specific position
void insertAtPosition(Node*& head, int data, int position) {
    Node* newNode = new Node(data);

    // If inserting at position 0 (beginning)
    if (position == 0) {
        if (head == nullptr) {
            newNode->next = newNode; // First node points to itself
            head = newNode;
        } else {
            // Find the last node
            Node* temp = head;
            while (temp->next != head) {
                temp = temp->next;
            }

            // Insert the new node at the beginning
            newNode->next = head;
            temp->next = newNode;
            head = newNode;
        }
        return;
    }

    // Traverse to the (position-1)th node
    Node* temp = head;
    for (int i = 0; i < position - 1 && temp->next != head; i++) {
        temp = temp->next;
    }

    if (temp->next == head && position > 0) {
        cout << "Position out of bounds.\n";
        delete newNode;
        return;
    }

    newNode->next = temp->next;
    temp->next = newNode;
}

// Delete at the end
void deleteAtEnd(Node*& head) {
    if (!head) {
        cout << "List is empty\n";
        return;
    }
    if (head->next == head) {
        delete head;
        head = nullptr;
        return;
    }
    Node* temp = head;
    while (temp->next->next != head) temp = temp->next;
    delete temp->next;
    temp->next = head;
}

// Traverse the list
void traverse(Node* head) {
    if (!head) {
        cout << "List is empty\n";
        return;
    }
    Node* temp = head;
    do {
        cout << temp->data << " -> ";
        temp = temp->next;
    } while (temp != head);
    cout << "(head)\n";
}

// Function to delete a node at a specific position
void deleteAtPosition(Node*& head, int position) {
    if (head == nullptr) {
        cout << "List is empty\n";
        return;
    }

    Node* temp = head;

    // Case 1: Deleting the head node
    if (position == 0) {
        if (head->next == head) {
            delete head; // Only one node in the list
            head = nullptr;
            return;
        }

        // Find the last node to update its next pointer
        Node* last = head;
        while (last->next != head) {
            last = last->next;
        }

        last->next = head->next;
        head = head->next;
        delete temp;
        return;
    }

    // Case 2: Deleting a node at position > 0
    Node* prev = nullptr;
    for (int i = 0; i < position; i++) {
        prev = temp;
        temp = temp->next;

        // If we circle back to the head, position is out of bounds
        if (temp == head) {
            cout << "Position out of bounds\n";
            return;
        }
    }

    prev->next = temp->next;
    delete temp;
}

// Function to check if the list is empty
bool isEmpty(Node* head) {
    return head == nullptr;
}

// Function to access an element at a specific index (0-based)
int get(Node* head, int index) {
    if (head == nullptr) {
        cout << "List is empty\n";
        return -1;
    }

    Node* temp = head;
    int count = 0;

    do {
        if (count == index)
            return temp->data;
        count++;
        temp = temp->next;
    } while (temp != head);

    cout << "Index out of range\n";
    return -1;
}

// Function to set an element at a specific index (0-based)
void set(Node* head, int index, int newValue) {
    if (head == nullptr) {
        cout << "List is empty\n";
        return;
    }

    Node* temp = head;
    int count = 0;

    do {
        if (count == index) {
            temp->data = newValue;
            return;
        }
        count++;
        temp = temp->next;
    } while (temp != head);

    cout << "Index out of range\n";
}

// Function to search for an element in a circular linked list
bool search(Node* head, int key) {
    if (head == nullptr) return false;

    Node* temp = head;
    do {
        if (temp->data == key)
            return true;
        temp = temp->next;
    } while (temp != head);

    return false;
}

// Reverse the list
void reverse(Node*& head) {
    if (!head || head->next == head) return;
    Node* prev = nullptr, *current = head, *next = nullptr, *tail = head;
    do {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    } while (current != head);
    head->next = prev;
    head = prev;
}

// Get size of the list
int size(Node* head) {
    if (!head) return 0;
    int count = 0;
    Node* temp = head;
    do {
        count++;
        temp = temp->next;
    } while (temp != head);
    return count;
}

// Clear the list
void clear(Node*& head) {
    if (!head) return; // If the list is empty, return immediately.

    Node* temp = head;
    Node* nextNode;

    // Traverse and delete each node
    while (temp->next != head) {
        nextNode = temp->next;
        delete temp;
        temp = nextNode;
    }

    // Delete the last remaining node
    delete temp;

    head = nullptr; // Set head to null after clearing the list
}

// Function to merge two sorted circular linked lists
void merge(Node*& headRef, Node* head1, Node* head2) {
    Node* tempHead = nullptr, *last = nullptr;
    Node* first1 = head1, *first2 = head2;
    
    //std::cout << "Starting merge...\n";

    if (head1 == nullptr) {
        //std::cout << "First list is empty. Returning a new node from the second list.\n";
        Node* newNode = new Node(head2->data); // Create a new node with the data of the first node of head2
        headRef = newNode; // Set the new node as the head
        head2 = head2->next;
        if (head2 == first2) head2 = nullptr; // Handle circular structure
        return;
    }
    if (head2 == nullptr) {
        //std::cout << "Second list is empty. Returning a new node from the first list.\n";
        Node* newNode = new Node(head1->data); // Create a new node with the data of the first node of head1
        headRef = newNode; // Set the new node as the head
        head1 = head1->next;
        if (head1 == first1) head1 = nullptr; // Handle circular structure
        return;
    }

    //std::cout << "Both lists are non-empty. Merging...\n";

    do {
        Node* newNode;
        if (head1 && (head2 == nullptr || head1->data <= head2->data)) {
            //std::cout << "Adding node from List 1: " << head1->data << "\n";
            newNode = new Node(head1->data);
            head1 = head1->next;
            if (head1 == first1) {
                //std::cout << "End of List 1 reached.\n";
                head1 = nullptr;  // Stop merging this list
            }
        } else {
            //std::cout << "Adding node from List 2: " << head2->data << "\n";
            newNode = new Node(head2->data);
            head2 = head2->next;
            if (head2 == first2) {
                //std::cout << "End of List 2 reached.\n";
                head2 = nullptr;
            }
        }

        if (!tempHead) {
            tempHead = newNode;
            //std::cout << "New head node created: " << tempHead->data << "\n";
        } else {
            last->next = newNode;
        }
        last = newNode;
    } while (head1 != nullptr || head2 != nullptr);

    // Make the list circular
    last->next = tempHead;
    headRef = tempHead;
    //std::cout << "Merge completed. Circular list created with head: " << headRef->data << "\n";
}


// Function to find the middle of a circular linked list
void middle(Node*& mid, Node* head) {
    if (head == nullptr || head->next == head) {  // Check if list is empty or contains one node
        mid = head;
        return;
    }

    Node* slow = head;
    Node* fast = head;

    // Move fast two steps and slow one step
    while (fast->next != head && fast->next->next != head) {
        fast = fast->next->next;
        slow = slow->next;
    }

    mid = slow;  // Assign the slow pointer to mid (middle node)
}

void sort(Node*& headRef) {
    // If the list is empty or contains a single node, no need to sort
    if (headRef == nullptr || headRef->next == headRef)
        return;

    Node* head = headRef;
    Node* mid = nullptr;

    // Find the middle node
    middle(mid, head);

    Node* nextToMid = mid->next;
    mid->next = head;  // Break circularity for first half
    Node* secondHalf = nextToMid;

    // Find the last node of the second half
    while (secondHalf->next != head)
        secondHalf = secondHalf->next;

    secondHalf->next = nextToMid;  // Break circularity for second half

    // Sort both halves recursively
    sort(head);
    sort(nextToMid);

    // Merge the sorted halves
    merge(headRef, head, nextToMid);
}


int main() {
    Node* list = nullptr;  // Initialize an empty linked list

    // 1. Insert elements at the beginning
    insertAtBeginning(list, 5);
    insertAtBeginning(list, 3);
    insertAtBeginning(list, 1);

    std::cout << "List after inserting at the beginning: ";
    traverse(list);

    // 2. Insert elements at the end
    insertAtEnd(list, 7);
    insertAtEnd(list, 9);

    std::cout << "List after inserting at the end: ";
    traverse(list);

    // 3. Insert element at position 2
    insertAtPosition(list, 4, 2);

    std::cout << "List after inserting 4 at position 2: ";
    traverse(list);

    // 4. Insert element after the second node
    Node* secondNode = list->next;
    insertAfterNode(secondNode, 6);

    std::cout << "List after inserting 6 after the second node: ";
    traverse(list);

    // 5. Insert element before the node with value 7
    Node* temp = list;
    while (temp != nullptr && temp->data != 7) {
        temp = temp->next;
    }
    insertBeforeNode(list, temp, 8);

    std::cout << "List after inserting 8 before the node with value 7: ";
    traverse(list);

    // 6. Delete the first node
    deleteAtBeginning(list);

    std::cout << "List after deleting the first node: ";
    traverse(list);

    // 7. Delete the last node
    deleteAtEnd(list);

    std::cout << "List after deleting the last node: ";
    traverse(list);

    // 8. Delete the node at position 2
    deleteAtPosition(list, 2);

    std::cout << "List after deleting the node at position 2: ";
    traverse(list);
	
	// 9. Check if the list is empty
    if (isEmpty(list)) {
        cout << "The list is empty." << endl;
    } else {
		cout << "The list is not empty." << endl;
	}
	
    // 10. Search for an element
    int key = 6;
    if (search(list, key)) {
        std::cout << "Element " << key << " found in the list." << std::endl;
    } else {
        std::cout << "Element " << key << " not found in the list." << std::endl;
    }

    // 11. Reverse the list
    reverse(list);

    std::cout << "List after reversing: ";
    traverse(list);

    // 12. Sort the list
    sort(list);

    std::cout << "List after sorting: ";
    traverse(list);

    // 13. Get the size of the list
    std::cout << "Size of the list: " << size(list) << std::endl;

    // 14. Access an element at a specific index
    int index = 2;
    int value = get(list, index);
    if (value != -1) {
        std::cout << "Element at index " << index << ": " << value << std::endl;
    } else {
        std::cout << "Index " << index << " is out of range." << std::endl;
    }

    // 15. Set a new value at a specific index
    set(list, 2, 10);
    std::cout << "List after setting value 10 at index 2: ";
    traverse(list);

    // 16. Clear the list
    clear(list);

    std::cout << "List after clearing: ";
    traverse(list);

    return 0;
}

Here is the Non-Generic circular singly linked list implementation in Java:

public class CircularLinkedList {

    // Node structure for a circular singly linked list
    static class Node {
        int data;
        Node next;

        // Constructor
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    // Insert at the beginning
    public static Node insertAtBeginning(Node head, int data) {
        Node newNode = new Node(data);
        if (head == null) {
            newNode.next = newNode; // Make it circular
            return newNode;
        }

        Node temp = head;
        while (temp.next != head) {
            temp = temp.next;
        }
        temp.next = newNode;
        newNode.next = head;
        return newNode; // New head
    }

    // Insert at the end
    public static Node insertAtEnd(Node head, int data) {
        Node newNode = new Node(data);
        if (head == null) {
            newNode.next = newNode;
            return newNode;
        }

        Node temp = head;
        while (temp.next != head) {
            temp = temp.next;
        }
        temp.next = newNode;
        newNode.next = head;
        return head; // Head remains the same
    }
    
    // Function to insert a new node after a given previous node
    public static void insertAfterNode(Node prevNode, int data) {
        if (prevNode == null) {
            System.out.println("The given previous node cannot be NULL.");
            return;
        }

        Node newNode = new Node(data);
        newNode.next = prevNode.next;
        prevNode.next = newNode;
    }

    // Function to insert a new node before a given next node
    public static Node insertBeforeNode(Node head, Node nextNode, int data) {
        if (head == null) {
            System.out.println("The list cannot be empty.");
            return null;
        }

        if (nextNode == null) {
            System.out.println("The given next node cannot be NULL.");
            return head;
        }

        Node newNode = new Node(data);

        // If inserting before the head, update head reference
        if (head == nextNode) {
            Node temp = head;
            while (temp.next != head) {
                temp = temp.next;
            }

            temp.next = newNode;  // Update last node's next pointer
            newNode.next = head;
            return newNode; // New node becomes the head
        }

        // Find the node just before nextNode
        Node temp = head;
        while (temp.next != head && temp.next != nextNode) {
            temp = temp.next;
        }

        if (temp.next != nextNode) {
            System.out.println("The given next node is not found in the list.");
            return head;
        }

        newNode.next = temp.next;
        temp.next = newNode;
        return head;
    }
    
    // Insert at a specific position
    public static Node insertAtPosition(Node head, int data, int position) {
        if (position == 0) {
            return insertAtBeginning(head, data);
        }

        Node newNode = new Node(data);
        Node temp = head;
        for (int i = 0; i < position - 1 && temp.next != head; i++) {
            temp = temp.next;
        }

        newNode.next = temp.next;
        temp.next = newNode;
        return head;
    }

    // Delete at the beginning
    public static Node deleteAtBeginning(Node head) {
        if (head == null) {
            System.out.println("List is empty");
            return null;
        }

        if (head.next == head) {
            return null;
        }

        Node temp = head;
        while (temp.next != head) {
            temp = temp.next;
        }

        temp.next = head.next;
        return head.next;
    }

    // Delete at the end
    public static Node deleteAtEnd(Node head) {
        if (head == null || head.next == head) {
            return null;
        }

        Node temp = head;
        while (temp.next.next != head) {
            temp = temp.next;
        }
        temp.next = head;
        return head;
    }

    // Delete at a specific position
    public static Node deleteAtPosition(Node head, int position) {
        if (head == null) {
            return null;
        }

        if (position == 0) {
            return deleteAtBeginning(head);
        }

        Node temp = head;
        for (int i = 0; i < position - 1 && temp.next != head; i++) {
            temp = temp.next;
        }

        if (temp.next == head) {
            return head;
        }

        temp.next = temp.next.next;
        return head;
    }

    // Traverse the list
    public static void traverse(Node head) {
        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)");
    }
	
	// Check if the list is empty
	public static boolean isEmpty(Node head) {
		return head == null;
	}
	
    // Function to merge two sorted circular linked lists
    public static Node merge(Node head1, Node head2) {
        if (head1 == null) return head2;
        if (head2 == null) return head1;

        Node dummy = new Node(0); // Temporary dummy node
        Node tail = dummy;
        Node first1 = head1, first2 = head2;

        do {
            Node newNode;
            if (head1 != null && (head2 == null || head1.data <= head2.data)) {
                newNode = new Node(head1.data);
                head1 = head1.next;
                if (head1 == first1) head1 = null;
            } else {
                newNode = new Node(head2.data);
                head2 = head2.next;
                if (head2 == first2) head2 = null;
            }

            tail.next = newNode;
            tail = newNode;

        } while (head1 != null || head2 != null);

        // Make the merged list circular
        tail.next = dummy.next;
        return dummy.next;
    }

    // Function to find the middle node of a circular linked list
    public static Node middle(Node head) {
        if (head == null || head.next == head) return head;

        Node slow = head, fast = head;
        while (fast.next != head && fast.next.next != head) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    // Function to sort a circular linked list using merge sort
    public static Node sort(Node head) {
        if (head == null || head.next == head) return head;

        Node mid = middle(head);
        Node secondHalf = mid.next;
        mid.next = head;  // Break circularity for the first half

        // Find last node of second half and break circularity
        Node temp = secondHalf;
        while (temp.next != head) temp = temp.next;
        temp.next = secondHalf;

        // Recursively sort both halves
        Node firstSorted = sort(head);
        Node secondSorted = sort(secondHalf);

        // Merge both halves
        return merge(firstSorted, secondSorted);
    }
    
    // Function to get an element at a specific index (0-based)
    public static int get(Node head, int index) {
        if (head == null) {
            System.out.println("List is empty");
            return -1;
        }

        Node temp = head;
        int count = 0;

        do {
            if (count == index)
                return temp.data;
            count++;
            temp = temp.next;
        } while (temp != head);

        System.out.println("Index out of range");
        return -1;
    }

    // Function to set an element at a specific index (0-based)
    public static void set(Node head, int index, int newValue) {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }

        Node temp = head;
        int count = 0;

        do {
            if (count == index) {
                temp.data = newValue;
                return;
            }
            count++;
            temp = temp.next;
        } while (temp != head);

        System.out.println("Index out of range");
    }

    // Function to search for an element in a circular linked list
    public static boolean search(Node head, int key) {
        if (head == null) return false;

        Node temp = head;
        do {
            if (temp.data == key)
                return true;
            temp = temp.next;
        } while (temp != head);

        return false;
    }

    // Function to reverse a circular linked list
    public static Node reverse(Node head) {
        if (head == null || head.next == head) return head;

        Node prev = null, current = head, next = null;
        Node tail = head;

        do {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        } while (current != head);

        head.next = prev; // Fix circular link
        return prev; // New head
    }
    
    // Get the size of the list
    public static int size(Node head) {
        if (head == null) return 0;

        int count = 0;
        Node temp = head;
        do {
            count++;
            temp = temp.next;
        } while (temp != head);
        return count;
    }

    // Clear the circular linked list
	public static void clear(Node head) {
		if (head == null) {
			System.out.println("List is already empty.");
			return null;
		}

		Node current = head;
		do {
			Node next = current.next; // Save the next node
			current.next = null;      // Break the link to the next node
			current = next;           // Move to the next node
		} while (current != head);    // Loop until we reach the head node again

		return null;  // Return null to indicate the list is empty
	}


    // Main method for testing
    public static void main(String[] args) {
        Node head = null;

        // 1. Insert elements at the beginning
        head = insertAtBeginning(head, 5);
        head = insertAtBeginning(head, 10);
        head = insertAtBeginning(head, 3);

        System.out.println("List after inserting at the beginning: ");
        traverse(head);

        // 2. Insert element at the end
        head = insertAtEnd(head, 7);
        head = insertAtEnd(head, 2);

        System.out.println("List after inserting at the end: ");
        traverse(head);

        // 3. Insert at a specific position
        head = insertAtPosition(head, 4, 2);
        System.out.println("List after inserting at position 2: ");
        traverse(head);
		
		// 4. Insert after a specific node
        insertAfterNode(head.next, 8);
        System.out.println("List after inserting 8 after second node: ");
        traverse(head);

        // 5. Insert before a specific node
        head = insertBeforeNode(head, head.next, 12);
        System.out.println("List after inserting 12 before second node: ");
        traverse(head);
		
        // 6. Delete at the beginning
        head = deleteAtBeginning(head);
        System.out.println("List after deleting at the beginning: ");
        traverse(head);

        // 7. Delete at the end
        head = deleteAtEnd(head);
        System.out.println("List after deleting at the end: ");
        traverse(head);

        // 8. Delete at a specific position
        head = deleteAtPosition(head, 2);
        System.out.println("List after deleting at position 2: ");
        traverse(head);
		
		// 9. Check if the list is empty
		if (isEmpty(head)) {
			System.out.println("The list is empty.");
		} else {
			System.out.println("The list is not empty.");
		}
	
        // 10. Search for an element
        int key = 7;
        if (search(head, key)) {
            System.out.println("Element " + key + " found in the list");
        } else {
            System.out.println("Element " + key + " not found in the list");
        }

        // 11. Reverse the list
        head = reverse(head);
        System.out.println("List after reversing: ");
        traverse(head);

        // 12. Get the size of the list
        System.out.println("Size of the list: " + size(head));
		
		// 13. Get element at a specific index
		int indexToGet = 2;
		int value = get(head, indexToGet);
		if (value != -1) {
			System.out.println("Element at index " + indexToGet + ": " + value);
		}

		// 14. Set value at a specific index
		int indexToSet = 1;
		int newValue = 25;
		System.out.println("Setting value at index " + indexToSet + " to " + newValue);
		set(head, indexToSet, newValue);
		
		System.out.println("Updated list after set operation:");
		traverse(head);
	
		// 15. Sort the list
        head = sort(head);

        System.out.println("Sorted list:");
		traverse(head);
		
        // 16. Clear the list
        head = clear(head);
        System.out.println("List after clearing: ");
        traverse(head);
    }
}

Here is the Non-Generic circular singly linked list implementation in C#:

using System;

public class CircularLinkedList
{
    // Node structure for circular singly linked list
    public class Node
    {
        public int Data;
        public Node Next;

        // Constructor to create a new node
        public Node(int data)
        {
            Data = data;
            Next = null;
        }
    }

    // Insert at the beginning
    public static Node InsertAtBeginning(Node head, int data)
    {
        Node newNode = new Node(data);
        if (head == null)
        {
            newNode.Next = newNode; // Circular link to itself if list is empty
            return newNode;
        }

        Node temp = head;
        // Traverse to the last node to point it to the new node
        while (temp.Next != head)
        {
            temp = temp.Next;
        }

        temp.Next = newNode;
        newNode.Next = head; // Link the new node to head
        return newNode;
    }

    // Insert at the end
    public static Node InsertAtEnd(Node head, int data)
    {
        Node newNode = new Node(data);
        if (head == null)
        {
            newNode.Next = newNode; // Circular link to itself if list is empty
            return newNode;
        }

        Node temp = head;
        // Traverse to the last node
        while (temp.Next != head)
        {
            temp = temp.Next;
        }

        temp.Next = newNode;
        newNode.Next = head; // Link the new node to head
        return head;
    }

    // Insert at a specific position
    public static Node InsertAtPosition(Node head, int data, int position)
    {
        Node newNode = new Node(data);
        if (position == 0)
        {
            return InsertAtBeginning(head, data);
        }

        Node temp = head;
        int count = 0;
        // Traverse to the position where new node should be inserted
        while (temp.Next != head && count < position - 1)
        {
            temp = temp.Next;
            count++;
        }

        if (count != position - 1)
        {
            Console.WriteLine("Position out of bounds");
            return head;
        }

        newNode.Next = temp.Next;
        temp.Next = newNode;
        return head;
    }

    // Insert after a given node
    public static void InsertAfterNode(Node prevNode, int data)
    {
        if (prevNode == null)
        {
            Console.WriteLine("The given previous node cannot be null");
            return;
        }

        Node newNode = new Node(data);
        newNode.Next = prevNode.Next;
        prevNode.Next = newNode;
    }

    // Insert before a given node
    public static Node InsertBeforeNode(Node head, Node nextNode, int data)
    {
        if (nextNode == null)
        {
            Console.WriteLine("The given next node cannot be null");
            return head;
        }

        if (head == nextNode)
        {
            return InsertAtBeginning(head, data);
        }

        Node temp = head;
        while (temp.Next != head && temp.Next != nextNode)
        {
            temp = temp.Next;
        }

        if (temp.Next == nextNode)
        {
            Node newNode = new Node(data);
            newNode.Next = nextNode;
            temp.Next = newNode;
        }
        else
        {
            Console.WriteLine("The given next node is not present in the list");
        }

        return head;
    }

    // Delete at the beginning
    public static Node DeleteAtBeginning(Node head)
    {
        if (head == null)
        {
            Console.WriteLine("List is empty");
            return null;
        }

        if (head.Next == head) // Only one node in the list
        {
            return null;
        }

        Node temp = head;
        // Traverse to the last node to point it to the second node
        while (temp.Next != head)
        {
            temp = temp.Next;
        }

        temp.Next = head.Next;
        return head.Next; // New head is the next node
    }

    // Delete at the end
    public static Node DeleteAtEnd(Node head)
    {
        if (head == null)
        {
            Console.WriteLine("List is empty");
            return null;
        }

        if (head.Next == head) // Only one node in the list
        {
            return null;
        }

        Node temp = head;
        while (temp.Next.Next != head)
        {
            temp = temp.Next;
        }

        temp.Next = head; // Last node points to the head again
        return head;
    }

    // Delete at a specific position
    public static Node DeleteAtPosition(Node head, int position)
    {
        if (head == null)
        {
            Console.WriteLine("List is empty");
            return null;
        }

        if (position == 0)
        {
            return DeleteAtBeginning(head);
        }

        Node temp = head;
        int count = 0;
        while (temp.Next != head && count < position - 1)
        {
            temp = temp.Next;
            count++;
        }

        if (count != position - 1)
        {
            Console.WriteLine("Position out of bounds");
            return head;
        }

        temp.Next = temp.Next.Next;
        return head;
    }
	
	// Check if the list is empty
	public static bool IsEmpty(Node head)
	{
		return head == null;
	}
	
    // Traverse the circular list
    public static void Traverse(Node head)
    {
        if (head == null)
        {
            Console.WriteLine("List is empty.");
            return;
        }

        Node temp = head;
        do
        {
            Console.Write(temp.Data + " -> ");
            temp = temp.Next;
        } while (temp != head);
        Console.WriteLine("(head)");
    }
    
    // Function to get an element at a specific index (0-based)
    public static int Get(Node head, int index)
    {
        if (head == null)
        {
            Console.WriteLine("List is empty");
            return -1;
        }
    
        Node temp = head;
        int count = 0;
    
        do
        {
            if (count == index)
                return temp.Data;  // Return the data at the specified index
            count++;
            temp = temp.Next;
        } while (temp != head);
    
        Console.WriteLine("Index out of range");
        return -1;  // If index is out of bounds
    }
    
    // Function to set an element at a specific index (0-based)
    public static void Set(Node head, int index, int newValue)
    {
        if (head == null)
        {
            Console.WriteLine("List is empty");
            return;
        }
    
        Node temp = head;
        int count = 0;
    
        do
        {
            if (count == index)
            {
                temp.Data = newValue;  // Set the new value at the specified index
                return;
            }
            count++;
            temp = temp.Next;
        } while (temp != head);
    
        Console.WriteLine("Index out of range");  // If index is out of bounds
    }

    // Search for an element in the circular list
    public static bool Search(Node head, int key)
    {
        if (head == null)
        {
            return false;
        }

        Node temp = head;
        do
        {
            if (temp.Data == key)
            {
                return true;
            }
            temp = temp.Next;
        } while (temp != head);

        return false;
    }

    // Reverse the circular linked list
    public static Node Reverse(Node head)
    {
        if (head == null || head.Next == head)
        {
            return head; // No reversal needed for empty or single-node list
        }

        Node prev = null;
        Node current = head;
        Node next = null;

        do
        {
            next = current.Next;
            current.Next = prev;
            prev = current;
            current = next;
        } while (current != head);

        head.Next = prev; // Circular link
        return prev; // New head
    }

    // Get the size of the circular list
    public static int Size(Node head)
    {
        if (head == null)
        {
            return 0;
        }

        int count = 0;
        Node temp = head;
        do
        {
            count++;
            temp = temp.Next;
        } while (temp != head);

        return count;
    }
    
    // Function to merge two sorted circular linked lists
    public static Node Merge(Node head1, Node head2)
    {
        if (head1 == null) return head2;
        if (head2 == null) return head1;
    
        Node dummy = new Node(0); // Temporary dummy node
        Node tail = dummy;
        Node first1 = head1, first2 = head2;
    
        do
        {
            Node newNode;
            if (head1 != null && (head2 == null || head1.Data <= head2.Data))
            {
                newNode = new Node(head1.Data);
                head1 = head1.Next;
                if (head1 == first1) head1 = null;
            }
            else
            {
                newNode = new Node(head2.Data);
                head2 = head2.Next;
                if (head2 == first2) head2 = null;
            }
    
            tail.Next = newNode;
            tail = newNode;
    
        } while (head1 != null || head2 != null);
    
        // Make the merged list circular
        tail.Next = dummy.Next;
        return dummy.Next;
    }
    
    // Function to find the middle node of a circular linked list
    public static Node Middle(Node head)
    {
        if (head == null || head.Next == head) return head;
    
        Node slow = head, fast = head;
        while (fast.Next != head && fast.Next.Next != head)
        {
            fast = fast.Next.Next;
            slow = slow.Next;
        }
        return slow;
    }
    
    // Function to sort a circular linked list using merge sort
    public static Node Sort(Node head)
    {
        if (head == null || head.Next == head) return head;
    
        Node mid = Middle(head);
        Node secondHalf = mid.Next;
        mid.Next = head;  // Break circularity for the first half
    
        // Find last node of second half and break circularity
        Node temp = secondHalf;
        while (temp.Next != head) temp = temp.Next;
        temp.Next = secondHalf;
    
        // Recursively sort both halves
        Node firstSorted = Sort(head);
        Node secondSorted = Sort(secondHalf);
    
        // Merge both halves
        return Merge(firstSorted, secondSorted);
    }

    // Clear the circular linked list
	public static Node Clear(Node head)
	{
		if (head == null)
		{
			Console.WriteLine("List is already empty.");
			return null;
		}

		Node current = head;
		do
		{
			Node next = current.Next; // Save the next node
			current.Next = null;      // Break the link to the next node
			current = next;           // Move to the next node
		} while (current != head);    // Loop until we reach the head node again

		return null;  // Return null to indicate the list is empty
	}


    // Main method to test
    public static void Main(string[] args)
    {
        Node head = null;

        // 1. Insert elements at the beginning
        head = InsertAtBeginning(head, 5);
        head = InsertAtBeginning(head, 10);
        head = InsertAtBeginning(head, 3);

        Console.WriteLine("List after inserting at the beginning:");
        Traverse(head);

        // 2. Insert element at the end
        head = InsertAtEnd(head, 7);
        head = InsertAtEnd(head, 2);

        Console.WriteLine("List after inserting at the end:");
        Traverse(head);

        // 3. Insert at a specific position
        head = InsertAtPosition(head, 4, 2);
        Console.WriteLine("List after inserting at position 2:");
        Traverse(head);

        // 4. Insert after a specific node
        InsertAfterNode(head.Next, 8);
        Console.WriteLine("List after inserting 8 after second node:");
        Traverse(head);

        // 5. Insert before a specific node
        head = InsertBeforeNode(head, head.Next, 12);
        Console.WriteLine("List after inserting 12 before second node:");
        Traverse(head);

        // 6. Delete at the beginning
        head = DeleteAtBeginning(head);
        Console.WriteLine("List after deleting at the beginning:");
        Traverse(head);

        // 7. Delete at the end
        head = DeleteAtEnd(head);
        Console.WriteLine("List after deleting at the end:");
        Traverse(head);

        // 8. Delete at a specific position
        head = DeleteAtPosition(head, 2);
        Console.WriteLine("List after deleting at position 2:");
        Traverse(head);
		
		// 9. Check if the list is empty
		if (IsEmpty(head))
		{
			Console.WriteLine("The list is empty.");
		}
		else
		{
			Console.WriteLine("The list is not empty.");
		}

        // 10. Search for an element
        int key = 7;
        if (Search(head, key))
        {
            Console.WriteLine($"Element {key} found in the list");
        }
        else
        {
            Console.WriteLine($"Element {key} not found in the list");
        }

        // 11. Reverse the list
        head = Reverse(head);
        Console.WriteLine("List after reversing:");
        Traverse(head);

        // 12. Get the size of the list
        Console.WriteLine("Size of the list: " + Size(head));
		
		// 13. Get value at a specific index
		int indexToGet = 2;  // 0-based index
		int value = Get(head, indexToGet);
		Console.WriteLine($"Value at index {indexToGet}: {value}");

		// 14. Set a new value at a specific index
		int indexToSet = 2;  // 0-based index
		int newValue = 99;
		Set(head, indexToSet, newValue);

		Console.WriteLine($"List after setting index {indexToSet} to {newValue}:");
		Traverse(head);
	
        // 15. Sort the list
        head = Sort(head);
        Console.WriteLine("Sorted list:");
        Traverse(head);

        // 16. Clear the list
        head = Clear(head);
        Console.WriteLine("List after clearing:");
        Traverse(head);
    }
}

Generic Circular Singly Linked List Implementation

Here is the Generic circular singly linked list implementation in C:

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

// StackElement structure to hold data and a toString function pointer
typedef struct {
    void* data;           // Pointer to hold the actual data
    char* toString;       // This will be modified to hold the string representation
} StackElement;

// Node structure for circular singly linked list
typedef struct Node {
    StackElement element;
    struct Node* next;     // Pointer to the next node
} Node;

// Function to create a new node
Node* createNode(StackElement element) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->element = element;
    newNode->next = newNode; // In circular list, the node points to itself initially
    return newNode;
}

// Function to insert a node at the beginning of the list (in a circular way)
void insertAtBeginning(Node** head, StackElement element) {
    Node* newNode = createNode(element);

    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* temp = *head;
        // Find the last node (which points to the head)
        while (temp->next != *head) {
            temp = temp->next;
        }
        temp->next = newNode;  // Set the last node's next to new node
        newNode->next = *head; // New node points to head
        *head = newNode;       // Update head to the new node
    }
}

// Function to insert a node at the end of the list (in a circular way)
void insertAtEnd(Node** head, StackElement element) {
    Node* newNode = createNode(element);

    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* temp = *head;
        // Find the last node
        while (temp->next != *head) {
            temp = temp->next;
        }
        temp->next = newNode;  // Set the last node's next to new node
        newNode->next = *head; // New node points to head
    }
}

// Function to insert a node after a given previous node
void insertAfterNode(Node* prevNode, StackElement element) {
    // Check if the previous node is NULL
    if (prevNode == NULL) {
        printf("The given previous node cannot be NULL\n");
        return;
    }

    // Create the new node with the given StackElement
    Node* newNode = createNode(element);

    // Insert the new node after prevNode
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

// Function to insert a node before a given next node
void insertBeforeNode(Node** head, Node* nextNode, StackElement element) {
    // Check if the head is NULL (list is empty)
    if (*head == NULL) {
        printf("The list cannot be empty\n");
        return;
    }

    // Check if the nextNode is NULL
    if (nextNode == NULL) {
        printf("The given next node cannot be NULL\n");
        return;
    }

    // Create the new node with the given StackElement
    Node* newNode = createNode(element);

    // If the nextNode is the head node, handle the insertion at beginning
    if (*head == nextNode) {
        // Insert the new node before the head node
        Node* temp = *head;
        while (temp->next != *head) { // Find the last node
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->next = *head;
        *head = newNode;
        return;
    }

    Node* temp = *head;
    while (temp != NULL && temp->next != nextNode) {
        temp = temp->next;
    }

    // If temp is NULL, then nextNode is not found in the list
    if (temp == NULL) {
        printf("The given next node is not found in the list\n");
        free(newNode);
        return;
    }

    newNode->next = temp->next;
    temp->next = newNode;
}

// Function to insert a node at a specific position in a circular singly linked list
void insertAtPosition(Node** head, StackElement element, int position) {
    // Create the new node with the given StackElement
    Node* newNode = createNode(element);

    // If the list is empty and position is 0, insert as the only node
    if (*head == NULL) {
        if (position == 0) {
            *head = newNode;
            newNode->next = *head; // Make it circular
        } else {
            printf("Position out of bounds\n");
        }
        return;
    }

    // If position is at the beginning (position 0)
    if (position == 0) {
        Node* temp = *head;
        // Find the last node (that points to the head)
        while (temp->next != *head) {
            temp = temp->next;
        }
        // Insert the new node at the beginning
        temp->next = newNode;
        newNode->next = *head;
        *head = newNode;
        return;
    }

    // Traverse the list to find the correct position
    Node* temp = *head;
    for (int i = 0; i < position - 1 && temp->next != *head; i++) {
        temp = temp->next;
    }

    // If position is greater than the number of nodes in the list
    if (temp->next == *head && position > 0) {
        printf("Position out of bounds\n");
        free(newNode);
        return;
    }

    // Insert the new node at the specified position
    newNode->next = temp->next;
    temp->next = newNode;
}


// Function to delete the first node
void deleteAtBeginning(Node** head) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }

    if (*head == (*head)->next) {
        free(*head);
        *head = NULL;
    } else {
        Node* temp = *head;
        // Find the last node
        while (temp->next != *head) {
            temp = temp->next;
        }
        temp->next = (*head)->next; // Last node points to the second node
        free(*head);
        *head = temp->next;
    }
}

// Function to delete the last node
void deleteAtEnd(Node** head) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }

    if (*head == (*head)->next) {
        free(*head);
        *head = NULL;
    } else {
        Node* temp = *head;
        // Traverse to the second-last node
        while (temp->next->next != *head) {
            temp = temp->next;
        }
        free(temp->next);       // Free the last node
        temp->next = *head;     // Set the second-last node's next to head
    }
}

// Function to delete a node at a specific position
void deleteAtPosition(Node** head, int position) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }

    if (position == 0) {
        deleteAtBeginning(head);
        return;
    }

    Node* temp = *head;
    for (int i = 0; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }

    if (temp == NULL || temp->next == *head) {
        printf("Position out of bounds\n");
        return;
    }

    Node* nodeToDelete = temp->next;
    temp->next = nodeToDelete->next;
    free(nodeToDelete);
}

// Function to traverse the list and print all elements
void traverse(Node* head) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }

    Node* temp = head;
    do {
        printf("%s -> ", temp->element.toString);
        temp = temp->next;
    } while (temp != head);
    printf("HEAD\n"); // To signify it's a circular list
}

// Function to search for an element in the list
int search(Node* head, StackElement keyElement) {
    if (head == NULL) {
        return 0;
    }

    Node* temp = head;
    do {
        if (strcmp(temp->element.toString, keyElement.toString) == 0) {
            return 1; // Found
        }
        temp = temp->next;
    } while (temp != head);

    return 0; // Not found
}

// Function to reverse the circular linked list (O(n) time complexity)
void reverse(Node** head) {
    if (*head == NULL || (*head)->next == *head) {
        return;
    }

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

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

// Function to get the size of the list
int size(Node* head) {
    int size = 0;
    if (head == NULL) return size;

    Node* temp = head;
    do {
        size++;
        temp = temp->next;
    } while (temp != head);

    return size;
}
// Function to check if the list is empty
int isEmpty(Node* head) {
    return head == NULL;
}
// Function to access an element at a specific index (0-based)
StackElement get(Node* head, int index) {
    int count = 0;
    Node* temp = head;

    // If the list is empty
    if (head == NULL) {
        StackElement emptyElement = {NULL, ""};
        return emptyElement; // Return empty element if the list is empty
    }

    // Traverse the list
    do {
        if (count == index) {
            return temp->element;  // Found the element at the specified index
        }
        count++;
        temp = temp->next;
    } while (temp != head);  // Stop when we loop back to the head node

    // If the index is out of range
    StackElement emptyElement = {NULL, ""};
    return emptyElement;
}
// Function to set an element at a specific index (0-based)
void set(Node* head, int index, StackElement element) {
    Node* current = head;
    int count = 0;

    // If the list is empty
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }

    // Traverse the list
    do {
        if (count == index) {
            current->element = element;  // Update the node's value
            return;  // Exit after updating
        }
        count++;
        current = current->next;
    } while (current != head);  // Stop when we loop back to the head node

    printf("Index out of range\n");  // Handle case where index exceeds list length
}
// Function to find the middle of a circular singly linked list
void middle(Node** mid, Node* head) {
    if (head == NULL || head->next == head) {
        *mid = head;
        return;
    }

    Node* slow = head;
    Node* fast = head;

    // Move fast two steps and slow one step
    while (fast->next != head && fast->next->next != head) {
        fast = fast->next->next;
        slow = slow->next;
    }

    *mid = slow;
}

// Function to merge two circular linked lists
void merge(Node** headRef, Node* head1, Node* head2) {
    Node* tempHead = NULL, *last = NULL;
    Node* first1 = head1, *first2 = head2;
    
    printf("Starting merge...\n");

    if (head1 == NULL) {
        printf("First list is empty. Returning a new node from the second list.\n");
        Node* newNode = createNode(head2->element); // Create a new node with the data of the first node of head2
        *headRef = newNode; // Set the new node as the head
        head2 = head2->next;
        if (head2 == first2) head2 = NULL; // Handle circular structure
        return;
    }
    if (head2 == NULL) {
        printf("Second list is empty. Returning a new node from the first list.\n");
        Node* newNode = createNode(head1->element); // Create a new node with the data of the first node of head1
        *headRef = newNode; // Set the new node as the head
        head1 = head1->next;
        if (head1 == first1) head1 = NULL; // Handle circular structure
        return;
    }

    printf("Both lists are non-empty. Merging...\n");

    do {
        Node* newNode;
        if (head1 && (head2 == NULL || strcmp(head1->element.toString, head2->element.toString) <= 0)) {
            printf("Adding node from List 1: %s\n", head1->element.toString);
            newNode = createNode(head1->element);
            head1 = head1->next;
            if (head1 == first1) {
                printf("End of List 1 reached.\n");
                head1 = NULL;  // Stop merging this list
            }
        } else {
            printf("Adding node from List 2: %s\n", head2->element.toString);
            newNode = createNode(head2->element);
            head2 = head2->next;
            if (head2 == first2) {
                printf("End of List 2 reached.\n");
                head2 = NULL;
            }
        }

        if (!tempHead) {
            tempHead = newNode;
            printf("New head node created: %s\n", tempHead->element.toString);
        } else {
            last->next = newNode;
        }
        last = newNode;
    } while (head1 != NULL || head2 != NULL);

    // Make the list circular
    last->next = tempHead;
    *headRef = tempHead;
    printf("Merge completed. Circular list created with head: %s\n", (*headRef)->element.toString);
}

// Function to sort a circular singly linked list (Merge Sort)
void sort(Node** headRef) {
    if (*headRef == NULL || (*headRef)->next == *headRef)
        return;

    Node* head = *headRef;
    Node* mid = NULL;
    middle(&mid, head);

    Node* nextToMid = mid->next;
    mid->next = head; // Break circularity for first half
    Node* secondHalf = nextToMid;

    // Find last node of second half
    while (secondHalf->next != head)
        secondHalf = secondHalf->next;
    
    secondHalf->next = nextToMid; // Break circularity for second half

    // Sort both halves
    sort(&head);
    sort(&nextToMid);

    // Merge sorted halves
    merge(headRef, head, nextToMid);
}
// Function to clear the entire linked list and free memory
void clear(Node** head) {
    if (*head == NULL) return;

    Node* current = *head;
    Node* next = NULL;
    do {
        next = current->next;
        free(current);
        current = next;
    } while (current != *head);

    *head = NULL;
}
struct Person {
    char name[20];
    int age;
};
int main() {
    // Create People
    struct Person alice = {"Alice", 30};
    struct Person john = {"John", 19};
    struct Person albert = {"Albert", 28};
    struct Person robert = {"Robert", 20};

    // Create StackElement for people
    StackElement personElement1 = {&alice, "Person{name:\"Alice\", age:30}"};
    StackElement personElement2 = {&john, "Person{name:\"John\", age:19}"};
    StackElement personElement3 = {&albert, "Person{name:\"Albert\", age:28}"};
    StackElement personElement4 = {&robert, "Person{name:\"Robert\", age:20}"};

    // Initialize Linked List
    Node* personList = NULL;

    // 1. **Insert elements at the beginning**
    insertAtBeginning(&personList, personElement1);
    insertAtBeginning(&personList, personElement2);
	
	// 2. Insert elements at the end
    insertAtEnd(&personList, personElement3);
    insertAtEnd(&personList, personElement4);
    printf("\nList after inserting elements:\n");
    traverse(personList);

    // 3. **Insert at a specific position**
    StackElement newElement = {&alice, "Person{name:\"Eve\", age:22}"};
    insertAtPosition(&personList, newElement, 2);
    printf("\nList after inserting at position 2:\n");
    traverse(personList);

    // 4. **Insert before a node**
    insertBeforeNode(&personList, personList->next, newElement);
    printf("\nList after inserting before second node:\n");
    traverse(personList);

    // 5. **Insert after a node**
    insertAfterNode(personList->next, newElement);
    printf("\nList after inserting after second node:\n");
    traverse(personList);

    // 6. **Delete the first node**
    deleteAtBeginning(&personList);
    printf("\nList after deleting first node:\n");
    traverse(personList);

    // 7. **Delete the last node**
    deleteAtEnd(&personList);
    printf("\nList after deleting last node:\n");
    traverse(personList);

    // 8. **Delete at a specific position**
    deleteAtPosition(&personList, 1);
    printf("\nList after deleting node at position 1:\n");
    traverse(personList);

    // 9. **Search for an element**
    int found = search(personList, personElement3);
    printf("\nSearch result for 'Albert': %s\n", found ? "Found" : "Not Found");

    // 10. **Get size of list**
    printf("\nSize of the list: %d\n", size(personList));

    // 11. **Check if list is empty**
    printf("\nIs the list empty? %s\n", isEmpty(personList) ? "Yes" : "No");

    // 12. **Access an element by index**
    StackElement retrievedElement = get(personList, 1);
    printf("\nElement at index 1: %s\n", retrievedElement.toString);

    // 13. **Modify an element at an index**
    StackElement modifiedElement = {&john, "Person{name:\"Updated John\", age:25}"};
    set(personList, 1, modifiedElement);
    printf("\nList after updating element at index 1:\n");
    traverse(personList);

    // 14. **Sort the linked list**
    sort(&personList);
    printf("\nList after sorting:\n");
    traverse(personList);

    // 15. **Reverse the linked list**
    reverse(&personList);
    printf("\nList after reversing:\n");
    traverse(personList);

    // 16. **Clear the list**
    clear(&personList);
    printf("\nList after clearing:\n");
    traverse(personList);

    return 0;
}

Here is the Generic circular singly linked list implementation in C++:

#include <iostream>
#include <string>

using namespace std;

// Node structure for circular singly linked list template
template <typename T>
struct Node {
    T data;
    Node* next;

    // Constructor to create a new node
    Node(T data) : data(data), next(nullptr) {}
};

// Insert at the beginning
template <typename T>
void insertAtBeginning(Node<T>*& head, T data) {
    Node<T>* newNode = new Node<T>(data);
    if (!head) {
        head = newNode;
        newNode->next = head;
    } else {
        Node<T>* temp = head;
        while (temp->next != head)
            temp = temp->next;
        temp->next = newNode;
        newNode->next = head;
        head = newNode;
    }
}

// Insert at the end
template <typename T>
void insertAtEnd(Node<T>*& head, T data) {
    Node<T>* newNode = new Node<T>(data);
    if (!head) {
        head = newNode;
        newNode->next = head;
    } else {
        Node<T>* temp = head;
        while (temp->next != head)
            temp = temp->next;
        temp->next = newNode;
        newNode->next = head;
    }
}

// Function to insert a node after a given previous node
template <typename T>
void insertAfterNode(Node<T>* prevNode, T element) {
    if (prevNode == nullptr) {
        cout << "The given previous node cannot be NULL\n";
        return;
    }
    Node<T>* newNode = new Node<T>(element);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

// Function to insert a node before a given next node
template <typename T>
void insertBeforeNode(Node<T>*& head, Node<T>* nextNode, T element) {
    if (head == nullptr) {
        cout << "The list cannot be empty\n";
        return;
    }
    if (nextNode == nullptr) {
        cout << "The given next node cannot be NULL\n";
        return;
    }

    Node<T>* newNode = new Node<T>(element);
    if (head == nextNode) { // Insert before head
        Node<T>* temp = head;
        while (temp->next != head) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->next = head;
        head = newNode;
        return;
    }

    Node<T>* temp = head;
    do {
        if (temp->next == nextNode) {
            newNode->next = temp->next;
            temp->next = newNode;
            return;
        }
        temp = temp->next;
    } while (temp != head);
    
    cout << "The given next node is not found in the list\n";
    delete newNode;
}

// Insert at a specific position
template <typename T>
void insertAtPosition(Node<T>*& head, T data, int position) {
    Node<T>* newNode = new Node<T>(data);
    if (position == 0) {
        if (head == nullptr) {
            head = newNode;
            newNode->next = head; // Circular link
        } else {
            Node<T>* temp = head;
            while (temp->next != head) {
                temp = temp->next;
            }
            temp->next = newNode;
            newNode->next = head;
            head = newNode;
        }
        return;
    }
    
    Node<T>* temp = head;
    for (int i = 0; i < position - 1; i++) {
        temp = temp->next;
        if (temp == head) {
            cout << "Position out of bounds\n";
            delete newNode;
            return;
        }
    }
    newNode->next = temp->next;
    temp->next = newNode;
}

// Delete at the beginning
template <typename T>
void deleteAtBeginning(Node<T>*& head) {
    if (!head) return;
    if (head->next == head) {
        delete head;
        head = nullptr;
        return;
    }
    Node<T>* temp = head;
    Node<T>* last = head;
    while (last->next != head)
        last = last->next;
    head = head->next;
    last->next = head;
    delete temp;
}

// Delete at the end
template <typename T>
void deleteAtEnd(Node<T>*& head) {
    if (!head) return;
    if (head->next == head) {
        delete head;
        head = nullptr;
        return;
    }
    Node<T>* temp = head;
    while (temp->next->next != head)
        temp = temp->next;
    delete temp->next;
    temp->next = head;
}

// Delete at a specific position in a Circular Singly Linked List
template <typename T>
void deleteAtPosition(Node<T>*& head, int position) {
    if (head == nullptr) {
        cout << "List is empty\n";
        return;
    }

    Node<T>* temp = head;
    // If deleting the head node
    if (position == 0) {
        // If the list has only one node
        if (head->next == head) {
            delete head;
            head = nullptr;
            return;
        }

        // Find the last node to update its next pointer
        Node<T>* last = head;
        while (last->next != head) {
            last = last->next;
        }

        last->next = head->next;
        Node<T>* toDelete = head;
        head = head->next;
        delete toDelete;
        return;
    }

    // Traverse to the node before the one to be deleted
    Node<T>* prev = head;
    for (int i = 0; i < position - 1 && prev->next != head; i++) {
        prev = prev->next;
    }

    if (prev->next == head) {
        cout << "Position out of bounds\n";
        return;
    }

    // Delete the node
    Node<T>* toDelete = prev->next;
    prev->next = toDelete->next;
    delete toDelete;
}

// check if the list is empty
template <typename T>
bool isEmpty(Node<T>* head) {
    return head == nullptr;
}

// Traverse the list
template <typename T>
void traverse(Node<T>* head) {
    if (!head) {
        cout << "NULL\n";
        return;
    }
    Node<T>* temp = head;
    do {
        cout << (temp->data).toString() << " -> ";
        temp = temp->next;
    } while (temp != head);
    cout << "(head)\n";
}

// Search for an element in a Circular Singly Linked List
template <typename T>
bool search(Node<T>* head, T key) {
    if (head == nullptr) return false; // Empty list

    Node<T>* temp = head;
    do {
        if (temp->data == key)
            return true;
        temp = temp->next;
    } while (temp != head); // Loop until we reach the head again

    return false;
}

// Reverse a Circular Singly Linked List
template <typename T>
void reverse(Node<T>*& head) {
    if (head == nullptr || head->next == head) return; // Empty list or single node

    Node<T>* prev = nullptr;
    Node<T>* current = head;
    Node<T>* next = nullptr;
    Node<T>* tail = head; // Keep track of the last node

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

    // Fix head and tail pointers
    head->next = prev;  // Make original head's next point to new head
    head = prev;        // Update head to new first element
}

// Get the size of a Circular Singly Linked List
template <typename T>
int size(Node<T>* head) {
    if (head == nullptr) return 0; // Empty list

    int count = 0;
    Node<T>* temp = head;
    do {
        count++;
        temp = temp->next;
    } while (temp != head);

    return count;
}

// Get an element at a specific index in a Circular Singly Linked List
template <typename T>
T get(Node<T>* head, int index) {
    if (head == nullptr) throw out_of_range("Index out of range");

    Node<T>* temp = head;
    int count = 0;

    do {
        if (count == index)
            return temp->data;
        count++;
        temp = temp->next;
    } while (temp != head);

    throw out_of_range("Index out of range");
}


// Set an element at a specific index in a Circular Singly Linked List
template <typename T>
void set(Node<T>* head, int index, T element) {
    if (head == nullptr) throw out_of_range("Index out of range");

    Node<T>* temp = head;
    int count = 0;

    do {
        if (count == index) {
            temp->data = element;
            return;
        }
        count++;
        temp = temp->next;
    } while (temp != head);

    throw out_of_range("Index out of range");
}

// Clear the list
template <typename T>
void clear(Node<T>*& head) {
    if (!head) return;
    Node<T>* temp = head;
    Node<T>* nextNode;
    do {
        nextNode = temp->next;
        delete temp;
        temp = nextNode;
    } while (temp != head);
    head = nullptr;
}

// Function to merge two sorted circular linked lists
template <typename T>
void merge(Node<T>*& headRef, Node<T>* head1, Node<T>* head2) {
    Node<T>* tempHead = nullptr, *last = nullptr;
    Node<T>* first1 = head1, *first2 = head2;

    //std::cout << "Starting merge...\n";

    if (head1 == nullptr) {
        //std::cout << "First list is empty. Returning a new node from the second list.\n";
        Node<T>* newNode = new Node<T>(head2->data);
        headRef = newNode;
        head2 = head2->next;
        if (head2 == first2) head2 = nullptr;
        return;
    }
    if (head2 == nullptr) {
        //std::cout << "Second list is empty. Returning a new node from the first list.\n";
        Node<T>* newNode = new Node<T>(head1->data);
        headRef = newNode;
        head1 = head1->next;
        if (head1 == first1) head1 = nullptr;
        return;
    }

    //std::cout << "Both lists are non-empty. Merging...\n";

    do {
        Node<T>* newNode;
        if (head1 && (head2 == nullptr || head1->data <= head2->data)) {
            //std::cout << "Adding node from List 1: " << (head1->data).toString() << "\n";
            newNode = new Node<T>(head1->data);
            head1 = head1->next;
            if (head1 == first1) {
                head1 = nullptr;
            }
        } else {
            //std::cout << "Adding node from List 2: " << (head2->data).toString() << "\n";
            newNode = new Node<T>(head2->data);
            head2 = head2->next;
            if (head2 == first2) {
                head2 = nullptr;
            }
        }

        if (!tempHead) {
            tempHead = newNode;
            //std::cout << "New head node created: " << (tempHead->data).toString() << "\n";
        } else {
            last->next = newNode;
        }
        last = newNode;
    } while (head1 != nullptr || head2 != nullptr);

    // Make the list circular
    last->next = tempHead;
    headRef = tempHead;
    //std::cout << "Merge completed. Circular list created with head: " << (headRef->data).toString() << "\n";
}
// Function to find the middle of a circular linked list
template <typename T>
void middle(Node<T>*& mid, Node<T>* head) {
    if (head == nullptr || head->next == head) {  // Check if list is empty or contains one node
        mid = head;
        return;
    }

    Node<T>* slow = head;
    Node<T>* fast = head;

    // Move fast two steps and slow one step
    while (fast->next != head && fast->next->next != head) {
        fast = fast->next->next;
        slow = slow->next;
    }

    mid = slow;  // Assign the slow pointer to mid (middle node)
}

template <typename T>
void sort(Node<T>*& headRef) {
    // If the list is empty or contains a single node, no need to sort
    if (headRef == nullptr || headRef->next == headRef) {
        //std::cout << "List is empty or has only one node. No sorting needed.\n";
        return;
    }

    //std::cout << "Starting sort...\n";

    Node<T>* head = headRef;
    Node<T>* mid = nullptr;

    // Find the middle node
    //std::cout << "Finding middle node...\n";
    middle(mid, head);
    //std::cout << "Middle node found: " << mid->data.toString() << "\n";

    Node<T>* nextToMid = mid->next;
    mid->next = head;  // Break circularity for first half
    Node<T>* secondHalf = nextToMid;

    // Find the last node of the second half
    Node<T>* last = secondHalf;
    while (last->next != head)
        last = last->next;

    last->next = nextToMid;  // Break circularity for second half

    //std::cout << "Splitting list into two halves:\n";
    //std::cout << "First half starts with: " << head->data.toString() << "\n";
    //std::cout << "Second half starts with: " << secondHalf->data.toString() << "\n";

    // Sort both halves recursively
    //std::cout << "Sorting first half...\n";
    sort(head);
    //std::cout << "Sorting second half...\n";
    sort(nextToMid);

    // Merge the sorted halves
    //std::cout << "Merging sorted halves...\n";
    merge(headRef, head, nextToMid);
    //std::cout << "Merge completed. Circular list created with head: " << headRef->data.toString() << "\n";
}

// Person class to demonstrate
class Person {
public:
    string name;
    int age;

    Person(string name, int age) : name(name), age(age) {}

    // Define < operator for sorting purposes (sort by name, then by age)
    bool operator<=(const Person& other) const {
        if (name == other.name) {
            return age <= other.age;  // If names are the same, sort by age
        }
        return name <= other.name;  // Otherwise, sort by name
    }
    
    // Overload the equality operator to compare Person objects
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
    
    string toString() const {
        return "Person{name: " + name + ", age: " + to_string(age) + "}";
    }
};
// Main function for testing
int main() {
    // Create Person objects
    Person alice("Alice", 30);
    Person john("John", 19);
    Person albert("Albert", 28);
    Person robert("Robert", 20);

    // Initialize the linked list
    Node<Person>* head = nullptr;

    // 1. Insert elements at the beginning
    insertAtBeginning(head, alice);
    insertAtBeginning(head, john);
	
	// 2. Insert elements at the beginning
    insertAtEnd(head, albert);
    insertAtEnd(head, robert);

    cout << "\nList after inserting elements:\n";
    traverse(head);

    // 3. Insert at a specific position
    Person eve("Eve", 22);
    insertAtPosition(head, eve, 2);
    cout << "\nList after inserting at position 2:\n";
    traverse(head);

    // 4. Insert before a node (insert before the second node)
    Node<Person>* secondNode = head->next; // Find the second node
    Person george("George", 32);
    insertBeforeNode(head, secondNode, george);
    cout << "\nList after inserting before second node:\n";
    traverse(head);

    // 5. Insert after a node (insert after the second node)
    Person joyce("Joyce", 27);
    insertAfterNode(secondNode, joyce);  // Insert after the second node
    cout << "\nList after inserting after second node:\n";
    traverse(head);

    // 6. Delete the first node
    deleteAtBeginning(head);
    cout << "\nList after deleting first node:\n";
    traverse(head);

    // 7. Delete the last node
    deleteAtEnd(head);
    cout << "\nList after deleting last node:\n";
    traverse(head);
	
	// 8. Delete at a specific position
	deleteAtPosition(head, 2);
    cout << "\nList after deleting node at position 2:\n";
    traverse(head);
	
    // 9. Search for an element
    bool found = search(head, albert);
    cout << "\nSearch result for 'Albert': " << (found ? "Found" : "Not Found") << endl;

    // 10. Get size of the list
    cout << "\nSize of the list: " << size(head) << endl;
	
	// 11. Check if list is empty
	if (isEmpty(head)) {
		cout << "The linked list is empty.\n";
	} else {
		cout << "The linked list is not empty.\n";
	}

    // 12. Get an element
    try {
        Person p = get(head, 2);
        cout << "\nElement at index 2: " << p.toString() << endl;
    } catch (const exception& e) {
        cout << e.what() << endl;
    }

    // 13. Set (modify) an element
    try {
        Person updatedJohn("John", 25);
        set(head, 1, updatedJohn);
        cout << "\nList after modifying index 1:\n";
        traverse(head);
    } catch (const exception& e) {
        cout << e.what() << endl;
    }

    // 14. Sort the linked list (by name first, then by age)
    sort(head);
    cout << "\nList after sorting:" << endl;
    traverse(head);
	
	// 15. Reverse the list
    reverse(head);

    cout << "\nReversed List:" << endl;
    traverse(head);


	// 16. Clear the list
    clear(head);

    cout << "\nList after clearing:" << endl;
    traverse(head);  // Should print NULL, as the list is cleared
	
    return 0;
}

Here is the Generic circular singly linked list implementation in Java:

class CircularLinkedList<T> {

    // Node structure for circular singly linked list
    static class Node<T> {
        T data;
        Node<T> next;

        // Constructor to create a new node
        Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    // Insert at the beginning
    public static <T> Node<T> insertAtBeginning(Node<T> tail, T data) {
        Node<T> newNode = new Node<>(data);
        if (tail == null) {
            newNode.next = newNode; // Point to itself
            return newNode;
        }
        newNode.next = tail.next;
        tail.next = newNode;
        return tail;
    }

    // Insert at the end
    public static <T> Node<T> insertAtEnd(Node<T> tail, T data) {
        Node<T> newNode = new Node<>(data);
        if (tail == null) {
            newNode.next = newNode;
            return newNode;
        }
        newNode.next = tail.next;
        tail.next = newNode;
        return newNode; // New tail
    }

    // Insert at a specific position
    public static <T> Node<T> insertAtPosition(Node<T> tail, T data, int position) {
        if (tail == null || position == 0) {
            return insertAtBeginning(tail, data);
        }

        Node<T> newNode = new Node<>(data);
        Node<T> temp = tail.next;
        for (int i = 0; i < position - 1 && temp != tail; i++) {
            temp = temp.next;
        }
        newNode.next = temp.next;
        temp.next = newNode;

        if (temp == tail) {
            return newNode; // New tail
        }
        return tail;
    }

    // Function to insert a new node after a given previous node
    public static <T> void insertAfterNode(Node<T> prevNode, T data) {
        if (prevNode == null) {
            System.out.println("The given previous node cannot be NULL.");
            return;
        }

        Node<T> newNode = new Node<>(data);
        newNode.next = prevNode.next;
        prevNode.next = newNode;
    }

    // Function to insert a new node before a given next node
    public static <T> Node<T> insertBeforeNode(Node<T> head, Node<T> nextNode, T data) {
        if (head == null) {
            System.out.println("The list cannot be empty.");
            return null;
        }

        if (nextNode == null) {
            System.out.println("The given next node cannot be NULL.");
            return head;
        }

        Node<T> newNode = new Node<>(data);

        // If inserting before the head, update head reference
        if (head == nextNode) {
            Node<T> temp = head;
            while (temp.next != head) {
                temp = temp.next;
            }

            temp.next = newNode;  // Update last node's next pointer
            newNode.next = head;
            return newNode; // New node becomes the head
        }

        // Find the node just before nextNode
        Node<T> temp = head;
        while (temp.next != head && temp.next != nextNode) {
            temp = temp.next;
        }

        if (temp.next != nextNode) {
            System.out.println("The given next node is not found in the list.");
            return head;
        }

        newNode.next = temp.next;
        temp.next = newNode;
        return head;
    }

    // Delete at the beginning
    public static <T> Node<T> deleteAtBeginning(Node<T> tail) {
        if (tail == null) {
            System.out.println("List is empty");
            return null;
        }
        if (tail.next == tail) { // Single node case
            return null;
        }
        tail.next = tail.next.next;
        return tail;
    }

    // Delete at the end
    public static <T> Node<T> deleteAtEnd(Node<T> tail) {
        if (tail == null) {
            System.out.println("List is empty");
            return null;
        }
        if (tail.next == tail) { // Single node case
            return null;
        }

        Node<T> temp = tail.next;
        while (temp.next != tail) {
            temp = temp.next;
        }
        temp.next = tail.next; // Skip tail node
        return temp; // New tail
    }
    
    // Delete at a specific position (Generic)
    public static <T> Node<T> deleteAtPosition(Node<T> tail, int position) {
        if (tail == null) {
            return null;
        }
    
        if (position == 0) {
            return deleteAtBeginning(tail);
        }
    
        Node<T> temp = tail.next;
        for (int i = 0; i < position - 1 && temp.next != tail.next; i++) {
            temp = temp.next;
        }
    
        if (temp.next == tail.next) {
            return tail; // Position out of bounds, return unchanged tail
        }
    
        // If deleting the tail node, update tail reference
        if (temp.next == tail) {
            tail = temp;
        }
    
        temp.next = temp.next.next;
        return tail;
    }
    
    // Function to get an element at a specific index (0-based)
    public static <T> T get(Node<T> head, int index) {
        if (head == null) {
            System.out.println("List is empty");
            return null;
        }
    
        Node<T> temp = head;
        int count = 0;
    
        do {
            if (count == index) {
                return temp.data;
            }
            count++;
            temp = temp.next;
        } while (temp != head);
    
        System.out.println("Index out of range");
        return null;
    }
    
    // Function to set an element at a specific index (0-based)
    public static <T> void set(Node<T> head, int index, T newValue) {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }
    
        Node<T> temp = head;
        int count = 0;
    
        do {
            if (count == index) {
                temp.data = newValue;
                return;
            }
            count++;
            temp = temp.next;
        } while (temp != head);
    
        System.out.println("Index out of range");
    }
	
	// check if the list is empty
	public static <T> boolean isEmpty(Node<T> head) {
		return head == null;
	}
	
    // Search for an element
    public static <T> boolean search(Node<T> tail, T key) {
        if (tail == null) return false;

        Node<T> temp = tail.next;
        do {
            if (temp.data.equals(key)) {
                return true;
            }
            temp = temp.next;
        } while (temp != tail.next);

        return false;
    }

    // Get the size of the list
    public static <T> int size(Node<T> tail) {
        if (tail == null) return 0;

        int count = 0;
        Node<T> temp = tail.next;
        do {
            count++;
            temp = temp.next;
        } while (temp != tail.next);
        return count;
    }

    // Traverse the list
    public static <T> void traverse(Node<T> tail) {
        if (tail == null) {
            System.out.println("NULL");
            return;
        }

        Node<T> temp = tail.next;
        do {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        } while (temp != tail.next);
        System.out.println("(back to head)");
    }
    
	public static <T> Node<T> reverse(Node<T> head) {
		if (head == null || head.next == head)
			return head; // Empty list or single node remains the same

		Node<T> prev = null;
		Node<T> current = head;
		Node<T> next = null;
		Node<T> last = head;

		// Find the last node
		while (last.next != head)
			last = last.next;

		do {
			next = current.next; // Store next node
			current.next = prev; // Reverse pointer
			prev = current;      // Move prev forward
			current = next;      // Move current forward
		} while (current != head);

		// Adjust pointers to maintain circular nature
		head.next = prev;  // Original head now points to the new last node
		last.next = prev;  // Last node points to the new head
		return prev;       // New head of the reversed circular list
	}

    // Function to find the middle node of a circular linked list
	public static <T> Node<T> middle(Node<T> head) {
		if (head == null || head.next == head) return head;

		Node<T> slow = head, fast = head;
		while (fast.next != head && fast.next.next != head) {
			fast = fast.next.next;
			slow = slow.next;
		}
		return slow;
	}

	// Function to sort a circular linked list using merge sort (requires Comparable<T>)
	public static <T extends Comparable<T>> Node<T> sort(Node<T> head) {
		if (head == null || head.next == head) return head;

		Node<T> mid = middle(head);
		Node<T> secondHalf = mid.next;
		mid.next = head;  // Break circularity for the first half

		// Find last node of second half and break circularity
		Node<T> temp = secondHalf;
		while (temp.next != head) temp = temp.next;
		temp.next = secondHalf;

		// Recursively sort both halves
		Node<T> firstSorted = sort(head);
		Node<T> secondSorted = sort(secondHalf);

		// Merge both halves
		return merge(firstSorted, secondSorted);
	}

	public static <T extends Comparable<T>> Node<T> merge(Node<T> head1, Node<T> head2) {
		if (head1 == null) return head2;
		if (head2 == null) return head1;

		Node<T> tempHead = null, last = null;
		Node<T> first1 = head1, first2 = head2;

		do {
			Node<T> newNode;
			if (head1 != null && (head2 == null || head1.data.compareTo(head2.data) <= 0)) {
				newNode = new Node<>(head1.data);
				head1 = head1.next;
				if (head1 == first1) head1 = null;
			} else {
				newNode = new Node<>(head2.data);
				head2 = head2.next;
				if (head2 == first2) head2 = null;
			}

			if (tempHead == null) {
				tempHead = newNode;
			} else {
				last.next = newNode;
			}
			last = newNode;
		} while (head1 != null || head2 != null);

		// Make the list circular
		last.next = tempHead;
		return tempHead;
	}


	// Clear the list
	public static <T> Node<T> clear(Node<T> head) {
		if (head == null) return null;  // If the list is already empty, return null
    
		Node<T> current = head;
		do {
			Node<T> next = current.next; // Save reference to next node
			current.next = null;            // Break the link to the next node
			current = next;                   // Move to the next node
		} while (current != head);            // Stop when we've looped back to the head
		
		return null;  // Return null to indicate the list is empty
	}

    // Person class
    static class Person implements Comparable<Person> {
        String name;
        int age;

        public Person(String name, int age) {
            this.name = name;
            this.age = age;
        }

        @Override
        public String toString() {
            return "Person{name: " + name + ", age: " + age + "}";
        }

        @Override
        public int compareTo(Person other) {
            // Compare by name first, then by age
            int nameComparison = this.name.compareTo(other.name);
            if (nameComparison != 0) {
                return nameComparison;
            }
            return Integer.compare(this.age, other.age);
        }
    }

    // Main method for testing
    public static void main(String[] args) {
        // Create Person objects
        Person alice = new Person("Alice", 30);
        Person john = new Person("John", 19);
        Person albert = new Person("Albert", 28);
        Person robert = new Person("Robert", 20);

        // Initialize the linked list
        Node<Person> head = null;

        // 1. Insert elements at the beginning
        head = insertAtBeginning(head, alice);
        head = insertAtBeginning(head, john);
		
		// 2. Insert elements at the end
        head = insertAtEnd(head, albert);
        head = insertAtEnd(head, robert);

        System.out.println("\nList after inserting elements:");
        traverse(head);

        // 3. Insert at a specific position
        Person eve = new Person("Eve", 22);
        head = insertAtPosition(head, eve, 2);
        System.out.println("\nList after inserting at position 2:");
        traverse(head);

        // 4. Insert before a node (insert before the second node)
        Node<Person> secondNode = head.next; // Find the second node
        head = insertBeforeNode(head, secondNode, eve);
        System.out.println("\nList after inserting before second node:");
        traverse(head);

        // 5. Insert after a node (insert after the second node)
        insertAfterNode(secondNode, eve);  // Insert after the second node
        System.out.println("\nList after inserting after second node:");
        traverse(head);

        // 6. Delete the first node
        head = deleteAtBeginning(head);
        System.out.println("\nList after deleting first node:");
        traverse(head);

        // 7. Delete the last node
        head = deleteAtEnd(head);
        System.out.println("\nList after deleting last node:");
        traverse(head);
		
		// 8. Delete at a specific position
		head = deleteAtPosition(head, 2);
		System.out.println("\nList after deleting node at position 2:");
		traverse(head);

        // 9. Search for an element
        boolean found = search(head, albert);
        System.out.println("\nSearch result for 'Albert': " + (found ? "Found" : "Not Found"));

        // 10. Get size of the list
        System.out.println("\nSize of the list: " + size(head));
		
		// 11. Check if list is empty
		if (isEmpty(head)) {
			System.out.println("The list is empty.");
		} else {
			System.out.println("The list is not empty.");
		}


        // 12. Get an element
        try {
            Person p = get(head, 2);
            System.out.println("\nElement at index 2: " + p.toString());
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }

        // 13. Set (modify) an element
        try {
            Person updatedJohn = new Person("John", 25);
            set(head, 1, updatedJohn);
            System.out.println("\nList after modifying index 1:");
            traverse(head);
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }

        // 14. Sort the linked list (by name first, then by age)
        head = sort(head);
        System.out.println("\nList after sorting:");
        traverse(head);
		
		// 15. Reverse the list
		head = reverse(head);

		System.out.println("\nList after reversing:");
		traverse(head);

		// 16. Clear the list
        head = clear(head);
        System.out.println("After clearing the list:");
        traverse(head);  // This should print "NULL" as the list is now empty
    }
}

Here is the Generic circular singly linked list implementation in C#:

using System;

class Node<T>
{
    public T Data;
    public Node<T> Next;

    public Node(T data)
    {
        Data = data;
        Next = null;
    }
}

class Program
{
    // Insert at beginning
    static Node<T> InsertAtBeginning<T>(Node<T> head, T data)
    {
        Node<T> newNode = new Node<T>(data);
        if (head == null)
        {
            newNode.Next = newNode; // Point to itself in a circular list
            return newNode;
        }

        Node<T> temp = head;
        while (temp.Next != head) temp = temp.Next; // Find the last node
        temp.Next = newNode;
        newNode.Next = head;
        return newNode;
    }

    // Insert at end
    static Node<T> InsertAtEnd<T>(Node<T> head, T data)
    {
        Node<T> newNode = new Node<T>(data);
        if (head == null)
        {
            newNode.Next = newNode;
            return newNode;
        }

        Node<T> temp = head;
        while (temp.Next != head) temp = temp.Next; // Find the last node
        temp.Next = newNode;
        newNode.Next = head;
        return head;
    }

    // Insert at position
    static Node<T> InsertAtPosition<T>(Node<T> head, T data, int position)
    {
        if (position == 0) return InsertAtBeginning(head, data);
        
        Node<T> newNode = new Node<T>(data);
        Node<T> temp = head;
        for (int i = 0; i < position - 1 && temp.Next != head; i++) temp = temp.Next;

        newNode.Next = temp.Next;
        temp.Next = newNode;
        return head;
    }
    
    // Insert before node
    static Node<T> InsertBeforeNode<T>(Node<T> head, Node<T> targetNode, T data)
    {
        if (head == null || targetNode == null) return head;
        if (head == targetNode) return InsertAtBeginning(head, data);
    
        Node<T> temp = head;
        do
        {
            if (temp.Next == targetNode)
            {
                Node<T> newNode = new Node<T>(data) { Next = targetNode };
                temp.Next = newNode;
                return head;
            }
            temp = temp.Next;
        } while (temp != head);
    
        return head; // Target node not found
    }
    
    // Insert after node
    static void InsertAfterNode<T>(Node<T> node, T data)
    {
        if (node == null) return;
    
        Node<T> newNode = new Node<T>(data) { Next = node.Next };
        node.Next = newNode;
    }


    // Delete at beginning
    static Node<T> DeleteAtBeginning<T>(Node<T> head)
    {
        if (head == null) return null;
        if (head.Next == head) return null; // Only one node

        Node<T> temp = head;
        while (temp.Next != head) temp = temp.Next; // Find last node
        temp.Next = head.Next;
        return head.Next;
    }

    // Delete at end
    static Node<T> DeleteAtEnd<T>(Node<T> head)
    {
        if (head == null) return null;
        if (head.Next == head) return null; // Only one node

        Node<T> temp = head;
        while (temp.Next.Next != head) temp = temp.Next; // Find second last node
        temp.Next = head;
        return head;
    }
    
    // Delete at a specific position
    static Node<T> DeleteAtPosition<T>(Node<T> head, int position)
    {
        if (head == null) return null; // Empty list
    
        Node<T> temp = head, prev = null;
    
        // If deleting the head node
        if (position == 0)
        {
            if (head.Next == head) // Only one node in the list
                return null;
    
            // Find the last node to update its `Next` pointer
            while (temp.Next != head)
                temp = temp.Next;
    
            temp.Next = head.Next; // Point last node to the new head
            return head.Next;
        }
    
        // Traverse to the position
        int count = 0;
        do
        {
            prev = temp;
            temp = temp.Next;
            count++;
        } while (temp != head && count < position);
    
        // If position is out of bounds
        if (count != position)
        {
            Console.WriteLine("Position out of bounds");
            return head;
        }
    
        prev.Next = temp.Next; // Remove node by updating pointer
        return head;
    }

    // Search for an element in a circular singly linked list
    static bool Search<T>(Node<T> head, T key)
    {
        if (head == null) return false; // Handle case of empty list
    
        Node<T> temp = head;
        do
        {
            if (temp.Data.Equals(key)) return true;
            temp = temp.Next;
        } while (temp != head); // Stop when we've looped back to the head
    
        return false;
    }
    
    // Get size of a circular singly linked list
    static int Size<T>(Node<T> head)
    {
        if (head == null) return 0; // Handle case of empty list
    
        int count = 0;
        Node<T> temp = head;
        do
        {
            count++;
            temp = temp.Next;
        } while (temp != head); // Stop when we've looped back to the head
    
        return count;
    }

    // Check if the circular singly linked list is empty
    static bool IsEmpty<T>(Node<T> head)
    {
        return head == null;
    }

    // Get an element at a specific index in a circular singly linked list
    static T Get<T>(Node<T> head, int index)
    {
        if (head == null) throw new Exception("List is empty");
    
        int count = 0;
        Node<T> temp = head;
        do
        {
            if (count == index) return temp.Data;
            count++;
            temp = temp.Next;
        } while (temp != head); // Stop when we've looped back to the head
    
        throw new Exception("Index out of range");
    }
    
    // Set (modify) an element at a specific index in a circular singly linked list
    static void Set<T>(Node<T> head, int index, T newValue)
    {
        if (head == null) throw new Exception("List is empty");
    
        int count = 0;
        Node<T> temp = head;
        do
        {
            if (count == index)
            {
                temp.Data = newValue;
                return;
            }
            count++;
            temp = temp.Next;
        } while (temp != head); // Stop when we've looped back to the head
    
        throw new Exception("Index out of range");
    }


    // Traverse the circular list
    static void Traverse<T>(Node<T> head)
    {
        if (head == null)
        {
            Console.WriteLine("List is empty.");
            return;
        }

        Node<T> temp = head;
        do
        {
            Console.Write(temp.Data + " -> ");
            temp = temp.Next;
        } while (temp != head);

        Console.WriteLine("(back to head)");
    }
    
    // Reverse a circular singly linked list
    static Node<T> Reverse<T>(Node<T> head)
	{
		if (head == null || head.Next == head) return head; // Handle empty or single-element list
		
		Node<T> prev = null;
		Node<T> current = head;
		Node<T> next = null;
		
		// Traverse the list and reverse the links
		do
		{
			next = current.Next; // Save the next node
			current.Next = prev; // Reverse the current node's link
			prev = current;      // Move prev to the current node
			current = next;      // Move to the next node
		} while (current != head); // Stop when we've looped back to the head
		
		// After the loop, `prev` is pointing to the new head
		head = prev; // Update the head reference to the new first node
		
		// The last node's `Next` should point to the new head
		current.Next = head; // The previous tail should point to the new head
		
		return head; // Return the new head
	}
    
    public static Node<T> Merge<T>(Node<T> head1, Node<T> head2) where T : IComparable<T>
    {
        if (head1 == null) return head2;
        if (head2 == null) return head1;
    
        Node<T> dummy = new Node<T>(default(T)); // Temporary dummy node
        Node<T> tail = dummy;
        Node<T> first1 = head1, first2 = head2;
    
        do
        {
            Node<T> newNode;
            if (head1 != null && (head2 == null || head1.Data.CompareTo(head2.Data) <= 0))
            {
                newNode = new Node<T>(head1.Data);
                head1 = head1.Next;
                if (head1 == first1) head1 = null;
            }
            else
            {
                newNode = new Node<T>(head2.Data);
                head2 = head2.Next;
                if (head2 == first2) head2 = null;
            }
    
            tail.Next = newNode;
            tail = newNode;
    
        } while (head1 != null || head2 != null);
    
        // Make the merged list circular
        tail.Next = dummy.Next;
        return dummy.Next;
    }

    
    public static Node<T> Middle<T>(Node<T> head) where T : IComparable<T>
    {
        if (head == null || head.Next == head) return head;
    
        Node<T> slow = head, fast = head;
        while (fast.Next != head && fast.Next.Next != head)
        {
            fast = fast.Next.Next;
            slow = slow.Next;
        }
        return slow;
    }

    public static Node<T> Sort<T>(Node<T> head) where T : IComparable<T>
    {
        if (head == null || head.Next == head) return head;
    
        Node<T> mid = Middle(head);
        Node<T> secondHalf = mid.Next;
        mid.Next = head;  // Break circularity for the first half
    
        // Find last node of second half and break circularity
        Node<T> temp = secondHalf;
        while (temp.Next != head) temp = temp.Next;
        temp.Next = secondHalf;
    
        // Recursively sort both halves
        Node<T> firstSorted = Sort(head);
        Node<T> secondSorted = Sort(secondHalf);
    
        // Merge both halves
        return Merge(firstSorted, secondSorted);
    }
    
    public static Node<T> Clear<T>(Node<T> head)
    {
        if (head == null) return null;  // If the list is already empty, return null
        
        Node<T> current = head;
        do
        {
            Node<T> next = current.Next; // Save reference to next node
            current.Next = null;         // Break the link to the next node
            current = next;              // Move to the next node
        } while (current != head);       // Stop when we've looped back to the head
        
        return null;  // Return null to indicate the list is empty
    }



    static void Main()
    {
        // Create Person objects
        Person alice = new Person("Alice", 30);
        Person john = new Person("John", 19);
        Person albert = new Person("Albert", 28);
        Person robert = new Person("Robert", 20);
        
        // Initialize the linked list
        Node<Person> head = null;
        
        // 1. Insert elements at the beginning
        head = InsertAtBeginning(head, alice);
        head = InsertAtBeginning(head, john);
        
        // 2. Insert elements at the end
        head = InsertAtEnd(head, albert);
        head = InsertAtEnd(head, robert);
        
        Console.WriteLine("\nList after inserting elements:");
        Traverse(head);
        
        // 3. Insert at a specific position
        Person eve = new Person("Eve", 22);
        head = InsertAtPosition(head, eve, 2);
        Console.WriteLine("\nList after inserting at position 2:");
        Traverse(head);
        
        // 4. Insert before a node (insert before the second node)
        Node<Person> secondNode = head.Next; // Find the second node
        Person jack = new Person("Jack", 29);
        head = InsertBeforeNode(head, secondNode, jack);
        Console.WriteLine("\nList after inserting before second node:");
        Traverse(head);
        
        // 5. Insert after a node (insert after the second node)
        InsertAfterNode(secondNode, eve);  // Insert after the second node
        Console.WriteLine("\nList after inserting after second node:");
        Traverse(head);
        
        // 6. Delete the first node
        head = DeleteAtBeginning(head);
        Console.WriteLine("\nList after deleting first node:");
        Traverse(head);
        
        // 7. Delete the last node
        head = DeleteAtEnd(head);
        Console.WriteLine("\nList after deleting last node:");
        Traverse(head);
        
        // 8. Delete node at position 2
        head = DeleteAtPosition(head, 2);
        Console.WriteLine("\nList after deleting at position 2:");
        Traverse(head);

        // 9. Search for an element
        bool found = Search(head, albert);
        Console.WriteLine("\nSearch result for 'Albert': " + (found ? "Found" : "Not Found"));
        
        // 10. Get size of the list
        Console.WriteLine("\nSize of the list: " + Size(head));
        
        // 11. Check if the list is empty
        if (IsEmpty(head))
        {
            Console.WriteLine("The list is empty.");
        }
        else
        {
            Console.WriteLine("The list is not empty.");
        }
    
        // 12. Get an element
        try
        {
            Person p = Get(head, 2);
            Console.WriteLine("\nElement at index 2: " + p.ToString());
        }
        catch (Exception e)
        {
            Console.WriteLine(e.Message);
        }
        
        // 13. Set (modify) an element
        try
        {
            Person updatedJohn = new Person("John", 25);
            Set(head, 1, updatedJohn);
            Console.WriteLine("\nList after modifying index 1:");
            Traverse(head);
        }
        catch (Exception e)
        {
            Console.WriteLine(e.Message);
        }
        
        // 14. Sort the linked list (by name first, then by age)
        head = Sort(head);
        Console.WriteLine("\nList after sorting:");
        Traverse(head);
        
        // 15. Reverse the list
        head = Reverse(head);
    
        Console.WriteLine("\nList after reversing:");
        Traverse(head);
    
        // 16. Clear the list
        head = Clear(head);
        Console.WriteLine("\nList after clearing:");
        Traverse(head);

    }
}

class Person : IComparable<Person>
{
    public string Name;
    public int Age;
    public Person(string name, int age) { Name = name; Age = age; }
    public int CompareTo(Person other)
    {
        // Sort by Name, then Age
        return Name.CompareTo(other.Name) != 0 ? Name.CompareTo(other.Name) : Age.CompareTo(other.Age);
    }
    public override string ToString() => $"Person{{name: {Name}, age: {Age}}}";
}