Write a C function to insert a new value in a sorted Circular Linked List (CLL). For example, if the input CLL is following:
After insertion of 7, the above CLL should be changed to following
Algorithm:
Allocate 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.
1) Linked List is empty:
a) since new_node is the only node in CLL, make a self loop.
new_node->next = new_node;
b) change the head pointer to point to new node.
*head_ref = new_node;
2) New node is to be inserted just before the head node:
(a) Find out the last node using a loop.
while(current->next != *head_ref)
current = current->next;
(b) Change the next of last node.
current->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;
3) New node is to be inserted somewhere after the head:
(a) Locate the node after which new node is to be inserted.
while ( current->next!= *head_ref &&
current->next->data < new_node->data)
{ current = current->next; }
(b) Make next of new_node as next of the located pointer
new_node->next = current->next;
(c) Change the next of the located pointer
current->next = new_node;
[ad type=”banner”]
Java Programming:
[pastacode lang=”java” manual=”%2F%2F%20Java%20program%20for%20sorted%20insert%20in%20circular%20linked%20list%0A%20%0Aclass%20Node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20Node%20next%3B%0A%20%0A%20%20%20%20Node(int%20d)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20data%20%3D%20d%3B%0A%20%20%20%20%20%20%20%20next%20%3D%20null%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0Aclass%20LinkedList%0A%7B%0A%20%20%20%20Node%20head%3B%0A%20%0A%20%20%20%20%2F%2F%20Constructor%0A%20%20%20%20LinkedList()%20%20%20%7B%20head%20%3D%20null%3B%20%7D%0A%20%0A%20%20%20%20%2F*%20function%20to%20insert%20a%20new_node%20in%20a%20list%20in%20sorted%20way.%0A%20%20%20%20%20Note%20that%20this%20function%20expects%20a%20pointer%20to%20head%20node%0A%20%20%20%20%20as%20this%20can%20modify%20the%20head%20of%20the%20input%20linked%20list%20*%2F%0A%20%20%20%20void%20sortedInsert(Node%20new_node)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Node%20current%20%3D%20head%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Case%201%20of%20the%20above%20algo%0A%20%20%20%20%20%20%20%20if%20(current%20%3D%3D%20null)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20new_node.next%20%3D%20new_node%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20head%20%3D%20new_node%3B%0A%20%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Case%202%20of%20the%20above%20algo%0A%20%20%20%20%20%20%20%20else%20if%20(current.data%20%3E%3D%20new_node.data)%0A%20%20%20%20%20%20%20%20%7B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20If%20value%20is%20smaller%20than%20head’s%20value%20then%0A%20%20%20%20%20%20%20%20%20%20%20%20%20we%20need%20to%20change%20next%20of%20last%20node%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20(current.next%20!%3D%20head)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20current%20%3D%20current.next%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20current.next%20%3D%20new_node%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20new_node.next%20%3D%20head%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20head%20%3D%20new_node%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Case%203%20of%20the%20above%20algo%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%7B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20Locate%20the%20node%20before%20the%20point%20of%20insertion%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20(current.next%20!%3D%20head%20%26%26%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20current.next.data%20%3C%20new_node.data)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20current%20%3D%20current.next%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20new_node.next%20%3D%20current.next%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20current.next%20%3D%20new_node%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Utility%20method%20to%20print%20a%20linked%20list%0A%20%20%20%20void%20printList()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(head%20!%3D%20null)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20Node%20temp%20%3D%20head%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20do%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(temp.data%20%2B%20%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20temp.next%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%20%20while%20(temp%20!%3D%20head)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Driver%20code%20to%20test%20above%0A%20%20%20%20public%20static%20void%20main(String%5B%5D%20args)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20LinkedList%20list%20%3D%20new%20LinkedList()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Creating%20the%20linkedlist%0A%20%20%20%20%20%20%20%20int%20arr%5B%5D%20%3D%20new%20int%5B%5D%20%7B12%2C%2056%2C%202%2C%2011%2C%201%2C%2090%7D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20start%20with%20empty%20linked%20list%20*%2F%0A%20%20%20%20%20%20%20%20Node%20temp%20%3D%20null%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Create%20linked%20list%20from%20the%20array%20arr%5B%5D.%0A%20%20%20%20%20%20%20%20%20Created%20linked%20list%20will%20be%201-%3E2-%3E11-%3E12-%3E56-%3E90*%2F%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%206%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20new%20Node(arr%5Bi%5D)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20list.sortedInsert(temp)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20list.printList()%3B%0A%20%20%20%20%7D%0A%7D” message=”” highlight=”” provider=”manual”/]Output:
1 2 11 12 56 90
Time Complexity: O(n) where n is the number of nodes in the given linked list.
[ad type=”banner”]Case 2 of the above algorithm/code can be optimized. Please see this comment from Pavan. To implement the suggested change we need to modify the case 2 to following.
[pastacode lang=”c” manual=”%2F%2F%20Case%202%20of%20the%20above%20algo%0Aelse%20if%20(current-%3Edata%20%3E%3D%20new_node-%3Edata)%0A%7B%0A%20%20%2F%2F%20swap%20the%20data%20part%20of%20head%20node%20and%20new%20node%0A%20%20%2F%2F%20assuming%20that%20we%20have%20a%20function%20swap(int%20*%2C%20int%20*)%0A%20%20swap(%26(current-%3Edata)%2C%20%26(new_node-%3Edata))%3B%20%0A%20%0A%20%20new_node-%3Enext%20%3D%20(*head_ref)-%3Enext%3B%0A%20%20(*head_ref)-%3Enext%20%3D%20new_node%3B%0A%7D” message=”” highlight=”” provider=”manual”/] [ad type=”banner”]