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

1.  Create a Linked list and get the position and data from the user.
2. Create a new node with that value.
3. Increment the head pointer till position-1.
4. Connect the new node and next node from the given position. Ex: 8->4
5. Connect the head node with new node Ex: 2->8.
6. Return the starting node of the list.

Program

#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
     }

 }

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