{"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 &#8211; 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&#8217;t <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<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">c<\/span> <\/div> <pre class=\"language-c code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-c code-embed-code\">\/* C program for insertion sort on a linked list *\/<br\/>#include&lt;stdio.h&gt;<br\/>#include&lt;stdlib.h&gt;<br\/> <br\/>\/* Link list node *\/<br\/>struct node<br\/>{<br\/>    int data;<br\/>    struct node* next;<br\/>};<br\/> <br\/>\/\/ Function to insert a given node in a sorted linked list<br\/>void sortedInsert(struct node**, struct node*);<br\/> <br\/>\/\/ function to sort a singly linked list using insertion sort<br\/>void insertionSort(struct node **head_ref)<br\/>{<br\/>    \/\/ Initialize sorted linked list<br\/>    struct node *sorted = NULL;<br\/> <br\/>    \/\/ Traverse the given linked list and insert every<br\/>    \/\/ node to sorted<br\/>    struct node *current = *head_ref;<br\/>    while (current != NULL)<br\/>    {<br\/>        \/\/ Store next for next iteration<br\/>        struct node *next = current-&gt;next;<br\/> <br\/>        \/\/ insert current in sorted linked list<br\/>        sortedInsert(&amp;sorted, current);<br\/> <br\/>        \/\/ Update current<br\/>        current = next;<br\/>    }<br\/> <br\/>    \/\/ Update head_ref to point to sorted linked list<br\/>    *head_ref = sorted;<br\/>}<br\/> <br\/> <br\/>\/* function to insert a new_node in a list. Note that this<br\/>  function expects a pointer to head_ref as this can modify the<br\/>  head of the input linked list (similar to push())*\/<br\/>void sortedInsert(struct node** head_ref, struct node* new_node)<br\/>{<br\/>    struct node* current;<br\/>    \/* Special case for the head end *\/<br\/>    if (*head_ref == NULL || (*head_ref)-&gt;data &gt;= new_node-&gt;data)<br\/>    {<br\/>        new_node-&gt;next = *head_ref;<br\/>        *head_ref = new_node;<br\/>    }<br\/>    else<br\/>    {<br\/>        \/* Locate the node before the point of insertion *\/<br\/>        current = *head_ref;<br\/>        while (current-&gt;next!=NULL &amp;&amp;<br\/>               current-&gt;next-&gt;data &lt; new_node-&gt;data)<br\/>        {<br\/>            current = current-&gt;next;<br\/>        }<br\/>        new_node-&gt;next = current-&gt;next;<br\/>        current-&gt;next = new_node;<br\/>    }<br\/>}<br\/> <br\/>\/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert *\/<br\/> <br\/>\/* Function to print linked list *\/<br\/>void printList(struct node *head)<br\/>{<br\/>    struct node *temp = head;<br\/>    while(temp != NULL)<br\/>    {<br\/>        printf(&quot;%d  &quot;, temp-&gt;data);<br\/>        temp = temp-&gt;next;<br\/>    }<br\/>}<br\/> <br\/>\/* A utility function to insert a node at the beginning of linked list *\/<br\/>void push(struct node** head_ref, int new_data)<br\/>{<br\/>    \/* allocate node *\/<br\/>    struct node* new_node = new node;<br\/> <br\/>    \/* put in the data  *\/<br\/>    new_node-&gt;data  = new_data;<br\/> <br\/>    \/* link the old list off the new node *\/<br\/>    new_node-&gt;next = (*head_ref);<br\/> <br\/>    \/* move the head to point to the new node *\/<br\/>    (*head_ref)    = new_node;<br\/>}<br\/> <br\/> <br\/>\/\/ Driver program to test above functions<br\/>int main()<br\/>{<br\/>    struct node *a = NULL;<br\/>    push(&amp;a, 5);<br\/>    push(&amp;a, 20);<br\/>    push(&amp;a, 4);<br\/>    push(&amp;a, 3);<br\/>    push(&amp;a, 30);<br\/> <br\/>    printf(&quot;Linked List before sorting \\n&quot;);<br\/>    printList(a);<br\/> <br\/>    insertionSort(&amp;a);<br\/> <br\/>    printf(&quot;\\nLinked List after sorting \\n&quot;);<br\/>    printList(a);<br\/> <br\/>    return 0;<br\/>}<\/code><\/pre> <\/div>\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=&#8221;banner&#8221;]\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}]}}