{"id":26978,"date":"2018-01-02T20:28:15","date_gmt":"2018-01-02T14:58:15","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26978"},"modified":"2018-01-02T20:28:15","modified_gmt":"2018-01-02T14:58:15","slug":"python-algorithm-sorted-insert-circular-linked-list","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-algorithm-sorted-insert-circular-linked-list\/","title":{"rendered":"python Algorithm-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=\u201dbanner\u201d]\n
Python Programming:<\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Node%20class%20%0Aclass%20Node%3A%0A%20%0A%20%20%20%20%23%20Constructor%20to%20initialize%20the%20node%20object%0A%20%20%20%20def%20__init__(self%2C%20data)%3A%0A%20%20%20%20%20%20%20%20self.data%20%3D%20data%0A%20%20%20%20%20%20%20%20self.next%20%3D%20None%0A%20%0Aclass%20LinkedList%3A%0A%20%0A%20%20%20%20%23%20Function%20to%20initialize%20head%0A%20%20%20%20def%20__init__(self)%3A%0A%20%20%20%20%20%20%20%20self.head%20%3D%20None%0A%20%0A%20%20%20%20%23%20Function%20to%20insert%20a%20new%20node%20at%20the%20beginning%0A%20%20%20%20def%20push(self%2C%20new_data)%3A%0A%20%20%20%20%20%20%20%20new_node%20%3D%20Node(new_data)%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20self.head%0A%20%20%20%20%20%20%20%20self.head%20%3D%20new_node%0A%20%0A%20%20%20%20%23%20Utility%20function%20to%20print%20the%20linked%20LinkedList%0A%20%20%20%20def%20printList(self)%3A%0A%20%20%20%20%20%20%20%20temp%20%3D%20self.head%0A%20%20%20%20%20%20%20%20print%20temp.data%2C%0A%20%20%20%20%20%20%20%20temp%20%3D%20temp.next%0A%20%20%20%20%20%20%20%20while(temp%20!%3D%20self.head)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print%20temp.data%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20temp.next%0A%20%0A%20%20%20%20%22%22%22%20function%20to%20insert%20a%20new_node%20in%20a%20list%20in%20sorted%20way.%0A%20%20%20%20%20%20%20Note%20that%20this%20function%20expects%20a%20pointer%20to%20head%20node%0A%20%20%20%20%20%20%20as%20this%20can%20modify%20the%20head%20of%20the%20input%20linked%20list%20%22%22%22%0A%20%20%20%20def%20sortedInsert(self%2C%20new_node)%3A%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20current%20%3D%20self.head%0A%20%0A%20%20%20%20%20%20%20%20%23%20Case%201%20of%20the%20above%20algo%0A%20%20%20%20%20%20%20%20if%20current%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20new_node.next%20%3D%20new_node%20%0A%20%20%20%20%20%20%20%20%20%20%20%20self.head%20%3D%20new_node%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Case%202%20of%20the%20above%20algo%0A%20%20%20%20%20%20%20%20elif%20(current.data%20%3E%3D%20new_node.data)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20If%20value%20is%20smaller%20than%20head\u2019s%20value%20then%20we%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20need%20to%20change%20next%20of%20last%20node%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20current.next%20!%3D%20self.head%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20current%20%3D%20current.next%0A%20%20%20%20%20%20%20%20%20%20%20%20current.next%20%3D%20new_node%0A%20%20%20%20%20%20%20%20%20%20%20%20new_node.next%20%3D%20self.head%0A%20%20%20%20%20%20%20%20%20%20%20%20self.head%20%3D%20new_node%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Case%203%20of%20the%20above%20algo%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Locate%20the%20node%20before%20the%20point%20of%20insertion%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20(current.next%20!%3D%20self.head%20%20and%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)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20current%20%3D%20current.next%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20new_node.next%20%3D%20current.next%0A%20%20%20%20%20%20%20%20%20%20%20%20current.next%20%3D%20new_node%0A%20%0A%20%0A%23%20Driver%20program%20to%20test%20the%20above%20function%0A%23llist%20%3D%20LinkedList()%0Aarr%20%3D%20%5B12%2C%2056%2C%202%2C%2011%2C%201%2C%2090%5D%0A%20%0Alist_size%20%3D%20len(arr)%0A%20%0A%23%20start%20with%20empty%20linked%20list%0Astart%20%3D%20LinkedList()%0A%20%0A%23%20Create%20linked%20list%20from%20the%20array%20arr%5B%5D%0A%23%20Created%20linked%20list%20will%20be%201-%3E2-%3E11-%3E12-%3E56-%3E90%0Afor%20i%20in%20range(list_size)%3A%0A%20%20%20%20temp%20%3D%20Node(arr%5Bi%5D)%0A%20%20%20%20start.sortedInsert(temp)%0A%20%0Astart.printList()\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
\u00a0<\/p>\n
Output:<\/strong><\/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 comment from Pavan. To implement the suggested change we need to modify the case 2 to following.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%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\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\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":[80096,80433,80434,80115,80432,80436,80435,80437],"class_list":["post-26978","post","type-post","status-publish","format-standard","hentry","category-circular-linked-list","category-linked-list","tag-circular-linked-list-algorithm-pdf","tag-circular-linked-list-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-sorted-linked-list-java","tag-insertion-sort-linked-list-c-code"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26978","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=26978"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26978\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26978"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26978"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26978"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}