Insert a node at a specific position in LinkedList

Question
Write a program to insert a node at a specific position in Singly Linked list. You are given position and data to be inserted. In the list attach the data after that position. Position of the head is 1. As an example, if the initial list is 1->2->3 and given data is 8 and position is 2. Then the output is 1->2->8.
Logic
- Create a Linked list and get the position and data from the user.
- Create a new node with that value.
- Increment the head pointer till position-1.
- Connect the new node and next node from the given position. Ex: 8->4
- Connect the head node with new node Ex: 2->8.
- Return the starting node of the list.
Program
[code lang=”c”]
#include<stdio.h>
#include<stdlib.h>
/*Creating structure*/
struct node
{
int data;
struct node* next; //link to next node in list
};
/*Creating new node*/
struct node* create(int data)
{
struct node* temp = NULL;
temp = (struct node*)malloc(sizeof(struct node)); //intializing pointer
temp->data = data;
temp->next = NULL;
return temp; //passing the node address
}
struct node* InsertAtPos(struct node* head, int data, int position)
{
struct node* newNode = (struct node*)malloc(sizeof(struct node));
struct node* start = (struct node*)malloc(sizeof(struct node));
newNode = create(data); //Creating New Node with given data
start = head; //store in ‘start’ to keep track of the intial node of list
int j = 1;
while(j<position) //If position is atleast 2
{
if(head->next != NULL)
head = head->next;
else
exit(-1); //If Position exceeds the length of the list
j++;
}
newNode->next = head->next->next; //Step 4 in Logic
head->next = newNode; //Step 5 in Logic
return start; //Step 6 in Logic
}
int main()
{
int data,pos;
struct node* node = (struct node*)malloc(sizeof(struct node));
/*Creating linkedlist with values values 1,2,3,4,5*/
node = create(1);
node->next = create(2);
node->next->next = create(3);
node->next->next->next = create(4);
node->next->next->next->next = create(5);
printf("enter data :");
scanf("%d",&data);
printf("enter postion :");
scanf("%d",&pos);
struct node* N = (struct node*)malloc(sizeof(struct node));
N = InsertAtPos(node,data,pos);
/*Traversing through list and printing all the data*/
while(N !=NULL)
{
printf("%d ",N->data);
N = N->next; //Increment node pointer
}
}
[/code]
ANALYSIS
Time complexity – O(N), In worst case we may traverse till the end of the list to insert a node. So it is of order N.
Space complexity – O(N), here N is size of the list
You might also like…
To-find-nth-to-last-element-of-a-singly-linkedlist