Insertion at Specific Location in CSLL

Insertion of any node at any specific position in circular singly linked list(CSLL), is something complex stuff,but we have to play with arrangement of node.

• First we have to create one Temp Variable and one flag.
• Traverse the node as per position value and update the flag and also Temp.
• When we got the exact position ,so apply the node arrangement.

Working Process

Code Implementation

#include <stdio.h>
#include<iostream>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
struct CreateNode   // Node Structure Initialization
{
	int  data;          // for data element
	struct CreateNode* nextNode;   //for storing the address of next element
};
struct CreateNode *HeadPointer = NULL;    // Initialization of HeadPointer

void insertNodeAtLocationCSLL(int DataElement, int Position)   // Method of Random Addition
{
	int flag = 1;
	struct CreateNode* NewNode = (struct CreateNode *)malloc(sizeof(struct CreateNode *));// For NewNode
	struct CreateNode* Temp = NULL; //Temp Node
	Temp = HeadPointer;
	while (flag < Position)
	{
		Temp = Temp->nextNode;
		flag++;
	}
	NewNode->data = DataElement;
	NewNode->nextNode = Temp->nextNode;
	Temp->nextNode = NewNode;
	std::cout << "DataElement " << DataElement << " has been inserted after Node-" << Position;

}
int main()
{
	int Position, DataElement;
	//Create 5 node statically and Initialize manually
	struct CreateNode* Node1 = (struct CreateNode *)malloc(sizeof(struct CreateNode *));
	struct CreateNode* Node2 = (struct CreateNode *)malloc(sizeof(struct CreateNode *));
	struct CreateNode* Node3 = (struct CreateNode *)malloc(sizeof(struct CreateNode *));
	struct CreateNode* Node4 = (struct CreateNode *)malloc(sizeof(struct CreateNode *));
	struct CreateNode* Node5 = (struct CreateNode *)malloc(sizeof(struct CreateNode *));
	Node1->data = 90;
	Node2->data = 100;
	Node3->data = 200;
	Node4->data = 300;
	Node5->data = 400;

	Node1->nextNode = Node2;
	Node2->nextNode = Node3;
	Node3->nextNode = Node4;
	Node4->nextNode = Node5;
	Node5->nextNode = Node1;

	struct CreateNode* Temp = NULL;
	HeadPointer = Node1;  // HeadPointer pointing to the Node1

	printf("Node Before Insertion : ");
	Temp = HeadPointer;
	while (Temp->nextNode != HeadPointer)
	{
		std::cout << Temp->data << " ";
		Temp = Temp->nextNode;
	}
	std::cout << Temp->data << " ";
	printf("\nEnter the DataElement and  Position for insertion :");
	std::cin >> DataElement >> Position;
	insertNodeAtLocationCSLL(DataElement, Position);
	printf("\nNode data after insertion process :\n");
	Temp = HeadPointer;
	while (Temp->nextNode != HeadPointer)
	{
		printf("%d ", Temp->data);
		Temp = Temp->nextNode;
	}
	printf("%d ", Temp->data);
	_getch();
	return 0;
}

Time & Space Complexity

• Worst Case : Time Complexity will be O(n).
• Best Case : Time Complexity will be O(1).
• Average Case : Time Complexity will be O(n).
• Worst Case Space Complexity will be O(1).