Insertion of node at specific location in DLL

Insertion of any node at any specific position in Doubly linked list(DLL), 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 as well as 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* prevNode;  // for storing the address of previuos element
};
struct CreateNode *HeadPointer = NULL;    // Initialization of HeadPointer

void insertNodeAtLocationDLL(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;
	Temp->nextNode->prevNode = NewNode;
	NewNode->nextNode = Temp->nextNode;
	NewNode->prevNode = Temp;
	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 *));
	//Data Initialization
	Node1->data = 90;
	Node2->data = 100;
	Node3->data = 200;
	Node4->data = 300;
	Node5->data = 400;
	//Address Initialization
	Node1->prevNode = NULL;
	Node1->nextNode = Node2;

	Node2->prevNode = Node1;
	Node2->nextNode = Node3;

	Node3->prevNode = Node2;
	Node3->nextNode = Node4;

	Node4->prevNode = Node3;
	Node4->nextNode = Node5;

	Node5->prevNode = Node4;
	Node5->nextNode = NULL;

	HeadPointer = Node1;  // HeadPointer pointing to the Node1

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

Time & Space Complexity

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