{"id":25422,"date":"2017-10-15T18:18:36","date_gmt":"2017-10-15T12:48:36","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25422"},"modified":"2018-10-27T15:11:08","modified_gmt":"2018-10-27T09:41:08","slug":"insertion-sort-singly-linked-list","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/insertion-sort-singly-linked-list\/","title":{"rendered":"Insertion Sort for Singly Linked List"},"content":{"rendered":"<p>We have discussed <a href=\"https:\/\/www.wikitechy.com\/technology\/insertion-sort\/\" target=\"_blank\" rel=\"noopener\">Insertion Sort<\/a> for arrays.\u00a0 In this article we discuss about <a href=\"https:\/\/www.wikitechy.com\/technology\/write-function-get-nth-node-linked-list\/\" target=\"_blank\" rel=\"noopener\">linked list<\/a>.<\/p>\n<h3 id=\"singly-linked-list\"><span style=\"color: #333300;\">Singly Linked List:<\/span><\/h3>\n<p>Singly Linked List is a collection of ordered set of elements. A Node in singly linked list has two parts \u2013 data part and link part. Data part of the node contains the actual information which is represented as node. Link part of the node contains address of next node linked to it.<\/p>\n<p>It can be traversed in only one direction because the node stores only next pointer. So, it can\u2019t <a href=\"https:\/\/www.wikitechy.com\/technology\/c-algorithm-write-function-reverse-linked-list\/\" target=\"_blank\" rel=\"noopener\">reverse linked list<\/a>.<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-31575 size-full\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/10\/singly-linked-list.png\" alt=\"insertion sort for singly linked list\" width=\"759\" height=\"169\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/10\/singly-linked-list.png 759w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/10\/singly-linked-list-300x67.png 300w\" sizes=\"(max-width: 759px) 100vw, 759px\" \/><\/p>\n<h3 id=\"algorithm-for-insertion-sort-for-singly-linked-list\"><span style=\"color: #003366;\">Algorithm for Insertion Sort for Singly Linked List :<\/span><\/h3>\n<ul>\n<li>\u00a0Create an <strong>empty sorted<\/strong> (or result) list<\/li>\n<li><strong>\u00a0Traverse<\/strong> the given list, do following for every node.<\/li>\n<li>\u00a0<strong>Insert<\/strong> current node in sorted way in sorted or result list.<\/li>\n<li><strong>\u00a0Change head<\/strong> of given linked list to head of sorted (or result) list.<\/li>\n<\/ul>\n<h3 id=\"insertion-sort-for-singly-linked-list\"><span style=\"color: #000080;\">Insertion Sort for Singly Linked List:<\/span><\/h3>\n<p>In <a href=\"https:\/\/www.wikitechy.com\/tutorials\/c-programming\/\" target=\"_blank\" rel=\"noopener\">C language<\/a>, program is given below:<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F*%20C%20program%20for%20insertion%20sort%20on%20a%20linked%20list%20*%2F%0A%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%20%0A%2F*%20Link%20list%20node%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node*%20next%3B%0A%7D%3B%0A%20%0A%2F%2F%20Function%20to%20insert%20a%20given%20node%20in%20a%20sorted%20linked%20list%0Avoid%20sortedInsert(struct%20node**%2C%20struct%20node*)%3B%0A%20%0A%2F%2F%20function%20to%20sort%20a%20singly%20linked%20list%20using%20insertion%20sort%0Avoid%20insertionSort(struct%20node%20**head_ref)%0A%7B%0A%20%20%20%20%2F%2F%20Initialize%20sorted%20linked%20list%0A%20%20%20%20struct%20node%20*sorted%20%3D%20NULL%3B%0A%20%0A%20%20%20%20%2F%2F%20Traverse%20the%20given%20linked%20list%20and%20insert%20every%0A%20%20%20%20%2F%2F%20node%20to%20sorted%0A%20%20%20%20struct%20node%20*current%20%3D%20*head_ref%3B%0A%20%20%20%20while%20(current%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Store%20next%20for%20next%20iteration%0A%20%20%20%20%20%20%20%20struct%20node%20*next%20%3D%20current-%3Enext%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20insert%20current%20in%20sorted%20linked%20list%0A%20%20%20%20%20%20%20%20sortedInsert(%26sorted%2C%20current)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Update%20current%0A%20%20%20%20%20%20%20%20current%20%3D%20next%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Update%20head_ref%20to%20point%20to%20sorted%20linked%20list%0A%20%20%20%20*head_ref%20%3D%20sorted%3B%0A%7D%0A%20%0A%20%0A%2F*%20function%20to%20insert%20a%20new_node%20in%20a%20list.%20Note%20that%20this%0A%20%20function%20expects%20a%20pointer%20to%20head_ref%20as%20this%20can%20modify%20the%0A%20%20head%20of%20the%20input%20linked%20list%20(similar%20to%20push())*%2F%0Avoid%20sortedInsert(struct%20node**%20head_ref%2C%20struct%20node*%20new_node)%0A%7B%0A%20%20%20%20struct%20node*%20current%3B%0A%20%20%20%20%2F*%20Special%20case%20for%20the%20head%20end%20*%2F%0A%20%20%20%20if%20(*head_ref%20%3D%3D%20NULL%20%7C%7C%20(*head_ref)-%3Edata%20%3E%3D%20new_node-%3Edata)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20new_node-%3Enext%20%3D%20*head_ref%3B%0A%20%20%20%20%20%20%20%20*head_ref%20%3D%20new_node%3B%0A%20%20%20%20%7D%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%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%20current%20%3D%20*head_ref%3B%0A%20%20%20%20%20%20%20%20while%20(current-%3Enext!%3DNULL%20%26%26%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20current-%3Enext-%3Edata%20%3C%20new_node-%3Edata)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20current%20%3D%20current-%3Enext%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20new_node-%3Enext%20%3D%20current-%3Enext%3B%0A%20%20%20%20%20%20%20%20current-%3Enext%20%3D%20new_node%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20BELOW%20FUNCTIONS%20ARE%20JUST%20UTILITY%20TO%20TEST%20sortedInsert%20*%2F%0A%20%0A%2F*%20Function%20to%20print%20linked%20list%20*%2F%0Avoid%20printList(struct%20node%20*head)%0A%7B%0A%20%20%20%20struct%20node%20*temp%20%3D%20head%3B%0A%20%20%20%20while(temp%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%20%22%2C%20temp-%3Edata)%3B%0A%20%20%20%20%20%20%20%20temp%20%3D%20temp-%3Enext%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20A%20utility%20function%20to%20insert%20a%20node%20at%20the%20beginning%20of%20linked%20list%20*%2F%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_data)%0A%7B%0A%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20struct%20node*%20new_node%20%3D%20new%20node%3B%0A%20%0A%20%20%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%0A%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20struct%20node%20*a%20%3D%20NULL%3B%0A%20%20%20%20push(%26a%2C%205)%3B%0A%20%20%20%20push(%26a%2C%2020)%3B%0A%20%20%20%20push(%26a%2C%204)%3B%0A%20%20%20%20push(%26a%2C%203)%3B%0A%20%20%20%20push(%26a%2C%2030)%3B%0A%20%0A%20%20%20%20printf(%22Linked%20List%20before%20sorting%20%5Cn%22)%3B%0A%20%20%20%20printList(a)%3B%0A%20%0A%20%20%20%20insertionSort(%26a)%3B%0A%20%0A%20%20%20%20printf(%22%5CnLinked%20List%20after%20sorting%20%5Cn%22)%3B%0A%20%20%20%20printList(a)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dc\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h3 id=\"output\"><span style=\"color: #333399;\"><strong>OUTPUT:<\/strong><\/span><\/h3>\n<pre>Linked List before sorting\r\n30  3  4  20  5\r\nLinked List after sorting\r\n3  4  5  20  30<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Insertion Sort for Singly Linked List &#8211; Searching and sorting &#8211; We have discussed Insertion Sort for arrays.In this article linked list is also discussed.<\/p>\n","protected":false},"author":1,"featured_media":31573,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,83477,79476,71670],"tags":[71222,72497,71224,70263,70461,71121,71130,72501,72394,70465,70886,70256,73253,70233,73254,70271,71216,70017,70881,70976,73244,71218,73252,72494,73247,71228,73246,72482,73250,72480,72405,73248,72500,72398,73249,70262,72408,72496,71120,70016,71299,73251,72491,73245,71676,70020,71149,71219,71142],"class_list":["post-25422","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm","category-insertion-sort","category-linked-list","category-searching-and-sorting","tag-algorithm-for-insertion-sort","tag-algorithm-for-linked-list","tag-algorithm-of-insertion-sort","tag-binary-search-tree","tag-bubble-sort","tag-bubble-sort-algorithm","tag-bubble-sort-in-data-structure","tag-bubble-sort-linked-list","tag-bubble-sort-linked-list-c","tag-bucket-sort","tag-complexity-of-insertion-sort","tag-data-structure-algorithms","tag-data-structures-and-algorithm","tag-data-structures-and-algorithms","tag-dynamic-memory-allocation","tag-heap-sort","tag-insertion-sort","tag-insertion-sort-algorithm","tag-insertion-sort-complexity","tag-insertion-sort-example","tag-insertion-sort-for-singly-linked-list","tag-insertion-sort-in-c","tag-insertion-sort-in-linked-list","tag-insertion-sort-linked-list","tag-insertion-sort-linked-list-java","tag-insertion-sort-pseudocode","tag-java-insertion-sort","tag-java-list-sort","tag-java-sort-linked-list","tag-java-sort-list","tag-linked-list-algorithm","tag-linked-list-insertion-sort","tag-linked-list-merge-sort","tag-linked-list-sort","tag-list-of-algorithms","tag-merge-sort","tag-merge-sort-linked-list-java","tag-merge-sort-using-linked-list","tag-selection-sort","tag-selection-sort-algorithm","tag-sort-linked-list","tag-sort-linked-list-c","tag-sort-linked-list-java","tag-sorted-calculator","tag-sorting-a-linked-list","tag-sorting-algorithms","tag-sorting-algorithms-in-data-structures","tag-sorting-in-c","tag-sorting-in-data-structure"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25422","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=25422"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25422\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31573"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25422"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25422"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25422"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}