Sorted Insert In Circular Linked List

July 30, 2019

Sorted insert in circular linked list

In this topic we will discuss about the how to insert the node in the sorted circular linked list.

first of all we will do allocated the memory for newly inserted node and put data in the newly allocated node.Let the pointer to the new node to be new_node.

After memory allocation we have three ways for insert the data is following-

First one is if linked list is empty then since new_node is only node in circular linked list, make a self loop.and change the head pointer to the new_node pointer.

Second case is new node insert in starting or before the head node.

A- Find out the last node using a loop .
     While(present->!=*head_ref)
     present=present->next;
B- Change the next of last node;
     present->next=new-node;
C- Change next of new node to point to head.
     new_node->next=*head_ref;
D- Change the head pointer to point to new node.
     *head_ref=new_node;

Third case is when we insert the new node after the head in any position,then

A- Locate the node after which new node is to be inserted.
    while(present->next!= *head_ref &&
    present->next->data data)
     { present = present->next; }
B- Make next of new_node as next of the located pointer
      new_node->next = present->next;
C- Change the next of the located pointer
     present->next = new_node;

Code for sorted insert in circular linked list


   #include<stdio.h> //haeder files
  #include<stdlib.h> //library files

   // create node
    struct Node 
{ 
    int data; 
    struct Node *next; 
}; 

     // this function for insert the new node in linked list 
     void sortedInsert(struct Node** head_ref, struct Node* new_node) 
{ 
    struct Node* present = *head_ref; 

    // Case 1 when list is empty
    if (present == NULL) 
{ 
    new_node->next = new_node; 
   *head_ref = new_node; 
} 

   // Case 2 when the node insert before the head
      else if (present->data >= new_node->data) 
{ 
   //when value is smaller than head's value

    while( present->next != *head_ref) 
    present = present->next; 
    present->next = new_node; 
   new_node->next = *head_ref; 
   *head_ref = new_node; 
} 

  // Case 3 when node insert in after head in somewhere
    else
{ 
    //Locate the node before the point of insertion 
     while ( present->next!= *head_ref && 
    present->next->data < new_node->data) 
    present = present->next; 
 
   new_node->next =present->next; 
   present->next = new_node; 
} 
} 

   //this Function to print nodes in a given linked list
   void printList(struct Node *start) 
{ 
   struct Node *temp; 

   if(start != NULL) 
{ 
   temp = start; 
   printf("\n"); 
  do { 
  printf("%d ", temp->data); 
  temp = temp->next; 
} while(temp != start); 
} 
} 
   // main method start
   int main() 
{ 
   int arr[] = {12, 56, 2, 11, 1, 90}; 
   int list_size, i; 

   // start with empty linked list 
       struct Node *start = NULL; 
       struct Node *temp; 

    // Create linked list from the array arr[]. 
   // Created linked list will be 1->2->11->12->56->90 
   for (i = 0; i< 6; i++) 
{ 
    temp = (struct Node *)malloc(sizeof(struct Node)); 
    temp->data = arr[i]; 
    sortedInsert(&start, temp); 
} 

    printList(start); 

    return 0; 
}

Output

1 2 11 12 56 90