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.
• 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`.

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.
• `[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).
• `[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);
} else {
newNode->prev = last;
}
}

// 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 (position == 1) {
} 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
} else {
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;
} 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
printf("The list is empty.\n");
return;
}
do {
printf("%d ", temp->data);
temp = temp->next;
printf("\n");
}

// Main function
int main() {
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);
} else {
newNode->prev = last;
}
}``````

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 (position == 1) {
} 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
} else {
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;
} 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
printf("The list is empty.\n");
return;
}
do {
printf("%d ", temp->data);
temp = temp->next;
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() {
• Initially creates an empty list (`head` is `NULL`).
• Prints the final state of the list using `printDoublyCircularLinkedList`.