{"id":26941,"date":"2017-12-28T21:43:00","date_gmt":"2017-12-28T16:13:00","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26941"},"modified":"2017-12-28T21:43:00","modified_gmt":"2017-12-28T16:13:00","slug":"sorted-insert-circular-linked-list-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/sorted-insert-circular-linked-list-2\/","title":{"rendered":"Sorted insert for circular linked list"},"content":{"rendered":"

Write a C function to insert a new value in a sorted Circular Linked List (CLL). For example, if the input CLL is following:<\/p>\n

\"Sorted<\/p>\n

After insertion of 7<\/strong>, the above CLL should be changed to following<\/p>\n

\"Sorted<\/p>\n

Algorithm:<\/strong>
\nAllocate memory for the newly inserted node and put data in the newly allocated node. Let the pointer to the new node be new_node. After memory allocation, following are the three cases that need to be handled.<\/p>\n

1) Linked List is empty:<\/em>  \r\n    a)  since new_node is the only node in CLL, make a self loop.      \r\n          new_node->next = new_node;  \r\n    b) change the head pointer to point to new node.\r\n          *head_ref = new_node;\r\n2) New node is to be inserted just before the head node:<\/em>    \r\n  (a) Find out the last node using a loop.\r\n         while(current->next != *head_ref)\r\n            current = current->next;\r\n  (b) Change the next of last node. \r\n         current->next = new_node;\r\n  (c) Change next of new node to point to head.\r\n         new_node->next = *head_ref;\r\n  (d) change the head pointer to point to new node.\r\n         *head_ref = new_node;\r\n3) New node is to be  inserted somewhere after the head: <\/em>\r\n   (a) Locate the node after which new node is to be inserted.\r\n         while ( current->next!= *head_ref && \r\n             current->next->data < new_node->data)\r\n         {   current = current->next;   }\r\n   (b) Make next of new_node as next of the located pointer\r\n         new_node->next = current->next;\r\n   (c) Change the next of the located pointer\r\n         current->next = new_node;<\/pre>\n[ad type=”banner”]\n
C Programming:<\/p>\n
 
 <\/div> 
#include<stdio.h>#include<stdlib.h> \/* structure for a node *\/struct node{  int data;  struct node *next;}; \/* function to insert a new_node in a list in sorted way.   Note that this function expects a pointer to head node   as this can modify the head of the input linked list *\/void sortedInsert(struct node** head_ref, struct node* new_node){  struct node* current = *head_ref;   \/\/ Case 1 of the above algo  if (current == NULL)  {     new_node->next = new_node;     *head_ref = new_node;  }   \/\/ Case 2 of the above algo  else if (current->data >= new_node->data)  {    \/* If value is smaller than head's value then      we need to change next of last node *\/    while(current->next != *head_ref)        current = current->next;    current->next = new_node;    new_node->next = *head_ref;    *head_ref = new_node;  }   \/\/ Case 3 of the above algo  else  {    \/* Locate the node before the point of insertion *\/    while (current->next!= *head_ref &&            current->next->data < new_node->data)      current = current->next;     new_node->next = current->next;    current->next = new_node;  }} \/* 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);  }} \/* Driver program to test above functions *\/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;}<\/code><\/pre> <\/div>\n
Output:<\/p>\n
1 2 11 12 56 90<\/pre>\n
Time Complexity: O(n) where n is the number of nodes in the given linked list.<\/p>\n
Case 2 of the above algorithm\/code can be optimized. Please see this <\/a>comment from Pavan. To implement the suggested change we need to modify the case 2 to following.<\/p>\n
 
 <\/div> 
\/\/ Case 2 of the above algoelse if (current->data >= new_node->data){  \/\/ swap the data part of head node and new node  \/\/ assuming that we have a function swap(int *, int *)  swap(&(current->data), &(new_node->data));    new_node->next = (*head_ref)->next;  (*head_ref)->next = new_node;}<\/code><\/pre> <\/div>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Sorted insert for circular linked list – Circular Linked List – Write a C function to insert a new value in a sorted Circular Linked List.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[79477,79476],"tags":[83775,80096,80433,83778,80434,80115,80432,80436,83773,83774,80435,83777,80437,83776,83779],"class_list":["post-26941","post","type-post","status-publish","format-standard","hentry","category-circular-linked-list","category-linked-list","tag-amcat-automata-questions-with-answers","tag-circular-linked-list-algorithm-pdf","tag-circular-linked-list-geeksforgeeks","tag-circular-linked-list-in-c-geeksforgeeks","tag-circular-linked-list-insert-at-beginning","tag-circular-linked-list-insertion-and-deletion-program","tag-deletion-in-circular-linked-list","tag-insert-a-node-in-a-sorted-linked-list-c","tag-insert-into-a-cyclic-sorted-list-leetcode","tag-insert-into-cycle-linked-list-leetcode","tag-insert-into-sorted-linked-list-java","tag-insert-sorted-list-amcat","tag-insertion-sort-linked-list-c-code","tag-mooshak-the-mouse-has-been-placed-in-a-maze-there-is-a-huge-chunk-of-cheese-somewhere-in-the-maze","tag-write-ac-function-to-insert-a-new-value-in-a-sorted-circular-linked-list-cll"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26941","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26941"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26941\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26941"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26941"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26941"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}