Insertion in Doubly Circular Linked List at Given Location

In this tutorial we will learn writing Algorithm and Program to insert a node in doubly circular linked list at the given location.

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

• Defines a structure Node that represents each element (node) in the doubly circular linked list.
• Each Node contains:
  • int data: The value stored in the node.
  • struct Node* next: A pointer to the next node in the list.
  • struct Node* prev: A pointer to the previous node in the list.

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

Function: createNode

• Creates a new Node with the given data.
• Allocates memory for the new node and sets its data field.
• Initializes next and prev to point to the node itself. This is crucial for maintaining the circular nature of the list, especially when the first node is added.

// 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;
}

Function: insertAtEnd

• 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.
• If the list is not empty:
  • Locates the last node (which is the previous node of the head).
  • Inserts the new node between the last node and the head, updating the necessary next and prev pointers to maintain the circular nature.

// 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;
    }
}

Function: insertAtSpecificPosition

• Inserts a new node at a specified position in the list.
• Handles the special case where the position is 1. If the list is empty, the new node is set as the head. If the list is not empty, insertAtEnd is used to insert the node, and then head is updated to the new node.
• For other positions, it traverses the list to find the correct insertion point and adjusts the next and prev pointers of the surrounding nodes to insert the new node while maintaining the circular structure.

// 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);
        }
    }
}

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");
}

• Prints the contents of the doubly circular linked list.
• Starts from the head and traverses the list by following the next pointers, printing each node’s data until it cycles back to the head.

Main Function

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

• Demonstrates the functionality of the list.
• Initially creates an empty list (head is NULL).
• Inserts nodes with values 10, 20, 30, and 40 at the end of the list.
• Inserts a node with value 25 at position 3.
• Prints the final state of the list using printDoublyCircularLinkedList.