Insertion in Doubly Circular Linked List at Given Location

Insertion in a Doubly Circular Linked List (DCLL) at a given location means adding a new node at a specific position in the list. In a DCLL, each node has pointers to both the next and previous nodes, and the last node connects back to the first node, forming a circle. By inserting at a given location, we can place the new node anywhere in the list at the beginning, in the middle, or at the end while keeping the circular and doubly-linked structure intact. This makes the list flexible for applications where we need to insert data at a precise position instead of only at the start or end.

Algorithm to Insert a Node at Specific Location in Doubly Circular Linked List

Step 1: Create a New Node

• Allocate memory for a new node.
• Assign the value to the node’s data field.
• Initialize the node’s next and prev pointers to point to itself. This is important for handling cases where the node might be the only node in the list.

Step 2: Check for an Empty List

• If the head pointer is NULL, it means the list is empty.
• If inserting at position 1 in an empty list, set head to the new node and make next and prev of the new node point to itself, forming a circular structure.

Step 3: Insert the Node at the Specific Position

• If inserting not at the start, traverse the list to find the node after which the new node is to be inserted.
• Adjust pointers:
  • Set newNode->next to the next of the found node.
  • Set newNode->prev to the found node.
  • Update next of the found node to newNode.
  • Update prev of the newNode->next to newNode.

Step 4: Handle Special Cases

• If inserting at the start (position 1), additionally update the head to the new node.
• If inserting at the end, ensure that the last node’s next points to the new node, and the new node’s next points back to head.

Example

Initial Setup

• Start with an Empty List: Initially, our list is empty. So, head is NULL.

Task To Perform

Insert nodes with values 10, 20, 30 in the list. Then, insert 15 at position 2.

Steps

Step 1: Create a New Node (10)

• Allocate Memory: Create a node with data 10.
• Initialize Pointers: next and prev point to the node itself.
• Node State: [Prev: 10 | Data: 10 | Next: 10]

Step 2: Check for an Empty List

• List is Empty: head is NULL.
• Insert at Position 1: Set head to this new node.
• List State: head -> [10], with both next and prev of [10] pointing to itself.

Insert Node (20)

• Create Node 20: Similar to 10.
• List Not Empty: Insert at end.
• Adjust Pointers:
  • [10]->next points to [20].
  • [20]->prev points to [10].
  • [20]->next points to head ([10]).
  • [10]->prev points to [20].
• List State: head -> [10] <-> [20] (circularly connected)

Insert Node (30)

• Create Node 30: Similar process.
• Insert at End: Adjust pointers accordingly.
• List State: head -> [10] <-> [20] <-> [30] (circularly connected)

Step 3: Insert Node (15) at Position 2

• Create Node 15: [Prev: 15 | Data: 15 | Next: 15]
• Traverse: Find the node after which to insert ([10] in this case).
• Adjust Pointers:
  • [15]->next points to [20].
  • [15]->prev points to [10].
  • [10]->next points to [15].
  • [20]->prev points to [15].
• List State After Insertion: head -> [10] <-> [15] <-> [20] <-> [30]

Step 4: Handle Special Cases

• Special Case: If inserted at the start, update head to new node. Not applicable in our example.
• If Inserted at End: Adjust head‘s prev to point to new node. Not applicable in our example.

Step 5

• Final List: The doubly circular linked list now contains nodes 10, 15, 20, and 30 in a circular fashion.
• Traversal: We can traverse this list from head in both directions indefinitely, illustrating its circular nature.

Program in C to Insert Node at Specific Location

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

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

// Create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = newNode; 
    newNode->prev = newNode; 
    return newNode;
}

// Insert at the End of the Doubly Circular Linked List
void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* last = (*head)->prev;
        newNode->next = *head;
        newNode->prev = last;
        last->next = (*head)->prev = newNode;
    }
}

// Print the Doubly Circular Linked List
void insertAtSpecificPosition(Node** head, int data, int position) {
    int i=0;
    if (position < 1) {
        printf("Invalid position.\n");
        return;
    }
    Node* newNode = createNode(data);
    if (*head == NULL) {
        if (position == 1) {
            *head = newNode;
        } else {
            printf("List is empty, cannot insert at position %d.\n", position);
            free(newNode);
        }
        return;
    }
    if (position == 1) {
        insertAtEnd(head, data); // Reuse insertAtEnd to handle circular nature
        *head = newNode; // Update head
    } else {
        Node *temp = *head;
        for (int i = 1; i < position - 1 && temp->next != *head; i++) {
            temp = temp->next;
        }
        if (temp->next == *head && position != 1) {
            temp->next = newNode;
            newNode->prev = temp;
            newNode->next = *head;
            (*head)->prev = newNode;
        } else if (temp->next != *head) {
            newNode->next = temp->next;
            newNode->prev = temp;
            temp->next->prev = newNode;
            temp->next = newNode;
        } else {
            printf("Invalid position - beyond list length.\n");
            free(newNode);
        }
    }
}

// Print the Doubly Circular Linked List
void printDoublyCircularLinkedList(Node* head) {
    if (!head) {
        printf("The list is empty.\n");
        return;
    }
    Node* temp = head;
    printf("Doubly Circular Linked List: ");
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("\n");
}

// Main function
int main() {
    Node* head = NULL;
    insertAtEnd(&head, 10);        
    insertAtEnd(&head, 20); 
    insertAtEnd(&head, 30);
    insertAtEnd(&head, 40);
    insertAtSpecificPosition(&head, 25, 3);  
    printDoublyCircularLinkedList(head);
    return 0;
}

Output

Doubly Circular Linked List: 10 20 25 30 40

Explanation

Structure Definition: Node

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

The above code defines a structure Node that represents each element in a doubly circular linked list. Each node contains three parts: an integer data that stores the value of the node, a pointer next that points to the next node in the list, and a pointer prev that points to the previous node. These pointers allow the list to be traversed in both directions, and the circular linking ensures that the last node connects back to the first node, maintaining a continuous loop.

Function: createNode

// Create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = newNode; 
    newNode->prev = newNode; 
    return newNode;
}

The above code creates a new Node with the given data. It first allocates memory for the new node and sets its data field with the provided value. Then, it initializes the next and prev pointers to point to the node itself. This step is crucial because it ensures the circular nature of the list, especially when the node is the first one being added, allowing the list to maintain its bidirectional and continuous structure even with a single node

Function: insertAtEnd

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

The above code inserts a new node at the end of the doubly circular linked list. If the list is empty (*head == NULL), the new node is set as the head, and its next and prev pointers point to itself, forming a single-node circular list. If the list is not empty, the code first locates the last node (which is the prev of the head) and then inserts the new node between the last node and the head, updating the next and prev pointers of the involved nodes. This ensures that the list maintains its doubly-linked and circular structure, allowing seamless forward and backward traversal.

Function: insertAtSpecificPosition

// Insert a node at a specific position
void insertAtPosition(Node** head, int data, int position) {
    if (position < 1) {
        printf("Invalid position.\n");
        return;
    }
    Node* newNode = createNode(data);
    if (*head == NULL) {
        if (position == 1) {
            *head = newNode;
        } else {
            printf("List is empty, cannot insert at position %d.\n", position);
            free(newNode);
        }
        return;
    }
    if (position == 1) {
        insertAtEnd(head, data); // Reuse insertAtEnd to handle circular nature
        *head = newNode; // Update head
    } else {
        Node *temp = *head;
        for (int i = 1; i < position - 1 && temp->next != *head; i++) {
            temp = temp->next;
        }
        if (temp->next == *head && position != 1) {
            temp->next = newNode;
            newNode->prev = temp;
            newNode->next = *head;
            (*head)->prev = newNode;
        } else if (temp->next != *head) {
            newNode->next = temp->next;
            newNode->prev = temp;
            temp->next->prev = newNode;
            temp->next = newNode;
        } else {
            printf("Invalid position - beyond list length.\n");
            free(newNode);
        }
    }
}

The above code inserts a new node at a specified position in the doubly circular linked list. If the position is 1, it handles a special case: if the list is empty, the new node becomes the head; if the list is not empty, it uses the insertAtEnd function to add the node at the end and then updates the head to point to this new node. For positions other than 1, the code traverses the list to locate the correct insertion point and then adjusts the next and prev pointers of the surrounding nodes. This ensures that the new node is correctly linked while maintaining the doubly-linked and circular structure of the list.

Function: printDoublyCircularLinkedList

// Print the Doubly Circular Linked List
void printDoublyCircularLinkedList(Node* head) {
    if (!head) {
        printf("The list is empty.\n");
        return;
    }
    Node* temp = head;
    printf("Doubly Circular Linked List: ");
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("\n");
}

The above code prints the contents of the doubly circular linked list. It starts from the head node and traverses the list by following the next pointers, printing the data of each node as it goes. The traversal continues until it reaches back to the head, demonstrating the circular nature of the list and ensuring that all nodes are displayed in order.

Main Function

// Main function
int main() {
    Node* head = NULL;
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtPosition(&head, 15, 2);
    printDoublyCircularLinkedList(head);
    return 0;

The above code demonstrates the functionality of the doubly circular linked list. It starts by creating an empty list where the head is NULL. It then inserts nodes with values 10, 20, 30, and 40 at the end of the list, building the initial sequence. After that, it inserts a node with value 25 at position 3, showing how insertion at a specific position works. Finally, it prints the final state of the list using the printDoublyCircularLinkedList function, displaying all nodes in order and confirming that the doubly-linked and circular structure has been correctly maintained.

Time & Space Complexity

Time Complexity

Operation / Function	Best Case	Average Case	Worst Case
createNode()	O(1)	O(1)	O(1)
insertAtEnd()	O(1)	O(1)	O(1)
insertAtSpecificPosition()	O(1) (position = 1)	O(n/2) ≈ O(n)	O(n) (position = end)
printDoublyCircularLinkedList()	O(1) (empty list)	O(n)	O(n)
Overall Program	O(1) (empty list)	O(n)	O(n)

Space Complexity

Function / Operation	Space Complexity
createNode()	O(1)
insertAtEnd()	O(1)
insertAtSpecificPosition()	O(1)
printDoublyCircularLinkedList()	O(1)
Overall (for storing n nodes)	O(n)