{"id":25420,"date":"2017-10-15T18:31:26","date_gmt":"2017-10-15T13:01:26","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25420"},"modified":"2018-10-29T16:17:57","modified_gmt":"2018-10-29T10:47:57","slug":"merge-sort-doubly-linked-list-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/merge-sort-doubly-linked-list-2\/","title":{"rendered":"Merge Sort for Doubly Linked List"},"content":{"rendered":"<p>Given a <a href=\"https:\/\/www.wikitechy.com\/technology\/reverse-doubly-linked-list-2\/\" target=\"_blank\" rel=\"noopener\">doubly linked list<\/a>, write a function to sort the doubly linked list in increasing order using <a href=\"https:\/\/www.wikitechy.com\/tutorials\/c-programming\/merge-sort-in-c\" target=\"_blank\" rel=\"noopener\">merge sort.<\/a><\/p>\n<p><strong>For example,<\/strong> the following doubly linked list should be changed to 2<->4<->8<->10<\/p>\n<p>The important change here is to modify the previous pointers also when merging two lists.<\/p>\n<h2 id=\"doubly-linked-list\"><span style=\"color: #333300;\">Doubly Linked List:<\/span><\/h2>\n<p>Doubly Linked List (DLL) is a list of elements and it varies from\u00a0<a href=\"https:\/\/www.wikitechy.com\/technology\/write-function-get-nth-node-linked-list\/\" target=\"_blank\" rel=\"noopener\">Linked List<\/a>. It allows navigation,\u00a0<strong>either forward or backward<\/strong>\u00a0when compared to\u00a0<a href=\"https:\/\/www.wikitechy.com\/technology\/insertion-sort-singly-linked-list\/\" target=\"_blank\" rel=\"noopener\">Single Linked List<\/a>.\u00a0It has two pointers:<strong>\u00a0previous pointer and next pointer<\/strong>.\u00a0Every element points to next of the list and previous element in list.<\/p>\n<p><strong>Terms used in doubly linked list:<\/strong><\/p>\n<ul>\n<li>Link<\/li>\n<li>Next<\/li>\n<li>Prev<\/li>\n<li>Linked list<\/li>\n<\/ul>\n<h3 id=\"c-programming-to-implement-of-merge-sort-for-doubly-linked-list\"><span style=\"color: #003300;\"><strong>C Programming to\u00a0implement of merge sort for doubly linked list:<\/strong><\/span><\/h3>\n[pastacode lang=\u201dc\u201d manual=\u201d%0A%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node%20*next%2C%20*prev%3B%0A%7D%3B%0A%20%0Astruct%20node%20*split(struct%20node%20*head)%3B%0A%20%0A%0Astruct%20node%20*merge(struct%20node%20*first%2C%20struct%20node%20*second)%0A%7B%0A%0A%20%20%20%20if%20(!first)%0A%20%20%20%20%20%20%20%20return%20second%3B%0A%20%0A%0A%20%20%20%20if%20(!second)%0A%20%20%20%20%20%20%20%20return%20first%3B%0A%20%0A%20%20%20%20%0A%20%20%20%20if%20(first-%3Edata%20%3C%20second-%3Edata)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20first-%3Enext%20%3D%20merge(first-%3Enext%2Csecond)%3B%0A%20%20%20%20%20%20%20%20first-%3Enext-%3Eprev%20%3D%20first%3B%0A%20%20%20%20%20%20%20%20first-%3Eprev%20%3D%20NULL%3B%0A%20%20%20%20%20%20%20%20return%20first%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%20second-%3Enext%20%3D%20merge(first%2Csecond-%3Enext)%3B%0A%20%20%20%20%20%20%20%20second-%3Enext-%3Eprev%20%3D%20second%3B%0A%20%20%20%20%20%20%20%20second-%3Eprev%20%3D%20NULL%3B%0A%20%20%20%20%20%20%20%20return%20second%3B%0A%20%20%20%20%7D%0A%7D%0A%0Astruct%20node%20*mergeSort(struct%20node%20*head)%0A%7B%0A%20%20%20%20if%20(!head%20%7C%7C%20!head-%3Enext)%0A%20%20%20%20%20%20%20%20return%20head%3B%0A%20%20%20%20struct%20node%20*second%20%3D%20split(head)%3B%0A%20%0A%0A%20%20%20%20head%20%3D%20mergeSort(head)%3B%0A%20%20%20%20second%20%3D%20mergeSort(second)%3B%0A%20%0A%0A%20%20%20%20return%20merge(head%2Csecond)%3B%0A%7D%0A%20%0A%0Avoid%20insert(struct%20node%20**head%2C%20int%20data)%0A%7B%0A%20%20%20%20struct%20node%20*temp%20%3D%0A%20%20%20%20%20%20%20%20(struct%20node%20*)malloc(sizeof(struct%20node))%3B%0A%20%20%20%20temp-%3Edata%20%3D%20data%3B%0A%20%20%20%20temp-%3Enext%20%3D%20temp-%3Eprev%20%3D%20NULL%3B%0A%20%20%20%20if%20(!(*head))%0A%20%20%20%20%20%20%20%20(*head)%20%3D%20temp%3B%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20temp-%3Enext%20%3D%20*head%3B%0A%20%20%20%20%20%20%20%20(*head)-%3Eprev%20%3D%20temp%3B%0A%20%20%20%20%20%20%20%20(*head)%20%3D%20temp%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%0Avoid%20print(struct%20node%20*head)%0A%7B%0A%20%20%20%20struct%20node%20*temp%20%3D%20head%3B%0A%20%20%20%20printf(%22Forward%20Traversal%20using%20next%20poitner%5Cn%22)%3B%0A%20%20%20%20while%20(head)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2Chead-%3Edata)%3B%0A%20%20%20%20%20%20%20%20temp%20%3D%20head%3B%0A%20%20%20%20%20%20%20%20head%20%3D%20head-%3Enext%3B%0A%20%20%20%20%7D%0A%20%20%20%20printf(%22%5CnBackward%20Traversal%20using%20prev%20pointer%5Cn%22)%3B%0A%20%20%20%20while%20(temp)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2C%20temp-%3Edata)%3B%0A%20%20%20%20%20%20%20%20temp%20%3D%20temp-%3Eprev%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%0Avoid%20swap(int%20*A%2C%20int%20*B)%0A%7B%0A%20%20%20%20int%20temp%20%3D%20*A%3B%0A%20%20%20%20*A%20%3D%20*B%3B%0A%20%20%20%20*B%20%3D%20temp%3B%0A%7D%0A%20%0A%0Astruct%20node%20*split(struct%20node%20*head)%0A%7B%0A%20%20%20%20struct%20node%20*fast%20%3D%20head%2C*slow%20%3D%20head%3B%0A%20%20%20%20while%20(fast-%3Enext%20%26%26%20fast-%3Enext-%3Enext)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20fast%20%3D%20fast-%3Enext-%3Enext%3B%0A%20%20%20%20%20%20%20%20slow%20%3D%20slow-%3Enext%3B%0A%20%20%20%20%7D%0A%20%20%20%20struct%20node%20*temp%20%3D%20slow-%3Enext%3B%0A%20%20%20%20slow-%3Enext%20%3D%20NULL%3B%0A%20%20%20%20return%20temp%3B%0A%7D%0A%20%0A%0Aint%20main(void)%0A%7B%0A%20%20%20%20struct%20node%20*head%20%3D%20NULL%3B%0A%20%20%20%20insert(%26head%2C5)%3B%0A%20%20%20%20insert(%26head%2C20)%3B%0A%20%20%20%20insert(%26head%2C4)%3B%0A%20%20%20%20insert(%26head%2C3)%3B%0A%20%20%20%20insert(%26head%2C30)%3B%0A%20%20%20%20insert(%26head%2C10)%3B%0A%20%20%20%20head%20%3D%20mergeSort(head)%3B%0A%20%20%20%20printf(%22%5Cn%5CnLinked%20List%20after%20sorting%5Cn%22)%3B%0A%20%20%20%20print(head)%3B%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: #008000;\"><strong>Output:<\/strong><\/span><\/h3>\n<pre>Linked List after sorting\r\nForward Traversal using next pointer\r\n3 4 5 10 20 30\r\nBackward Traversal using prev pointer\r\n30 20 10 5 4 3<\/pre>\n<p>\u00a0<\/p>\n<p><strong><span style=\"color: #008080;\">Time Complexity:<\/span> <\/strong>Time complexity of the above implementation is same as time complexity of MergeSort for arrays. It takes <strong>\u0398(nLogn)<\/strong> time.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>C Programming-Merge Sort for Doubly Linked List &#8211; Searching and Sorting &#8211; Merge sort for singly linked list is already discussed. The important change here is to modify the previous pointers also when merging two lists<\/p>\n","protected":false},"author":1,"featured_media":31264,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[82927,1,79476,83481,71670],"tags":[70238,73330,72394,73335,73327,73339,73325,70256,73253,70233,73336,73331,73328,73329,73332,73341,70929,70271,70928,70874,73334,73326,72333,72405,72487,72479,72500,73337,72398,72308,70262,71262,71165,71280,71306,73343,72496,73333,73340,73342,73345,71299,73251,72395,71676,70020,71142,73338,70026,73344],"class_list":["post-25420","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-c-programming-2","category-coding","category-linked-list","category-merge-sort","category-searching-and-sorting","tag-algorithms-and-data-structures","tag-algorithms-and-data-structures-in-java","tag-bubble-sort-linked-list-c","tag-c-list","tag-c-list-remove","tag-c-list-sort","tag-c-programming-merge-sort-for-doubly-linked-list","tag-data-structure-algorithms","tag-data-structures-and-algorithm","tag-data-structures-and-algorithms","tag-data-structures-and-algorithms-in-java","tag-data-structures-and-algorithms-made-easy-in-java-pdf","tag-data-structures-and-algorithms-made-easy-pdf","tag-data-structures-and-algorithms-pdf","tag-data-structures-in-c-pdf","tag-elements-of-programming-interviews-in-java","tag-heap-data-structure","tag-heap-sort","tag-heap-sort-algorithm","tag-heapify","tag-java-algorithms-and-data-structures","tag-java-data-structures-and-algorithms","tag-lg-n","tag-linked-list-algorithm","tag-linked-list-data-structure","tag-linked-list-in-data-structure","tag-linked-list-merge-sort","tag-linked-list-program-in-c","tag-linked-list-sort","tag-list-of-sorting-algorithms","tag-merge-sort","tag-merge-sort-algorithm","tag-merge-sort-c","tag-merge-sort-c-code","tag-merge-sort-linked-list","tag-merge-sort-on-linked-list","tag-merge-sort-using-linked-list","tag-n-number-lookup","tag-reverse-a-linked-list","tag-single-linked-list","tag-singly-linked-list-in-data-structure","tag-sort-linked-list","tag-sort-linked-list-c","tag-sort-list-java","tag-sorting-a-linked-list","tag-sorting-algorithms","tag-sorting-in-data-structure","tag-stack-in-data-structure","tag-time-complexity-of-binary-search","tag-what-is-tree-in-data-structure"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25420","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=25420"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25420\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31264"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25420"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25420"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25420"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}