{"id":25419,"date":"2017-10-15T18:29:06","date_gmt":"2017-10-15T12:59:06","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25419"},"modified":"2018-10-29T13:39:28","modified_gmt":"2018-10-29T08:09:28","slug":"java-programming-merge-sort-doubly-linked-list","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-merge-sort-doubly-linked-list\/","title":{"rendered":"Merge Sort for Doubly Linked List"},"content":{"rendered":"<p>Given a <a href=\"https:\/\/www.wikitechy.com\/technology\/merge-sort-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\/technology\/merge-sort-linked-lists-2\/\" target=\"_blank\" rel=\"noopener\">merge sort<\/a>.<\/p>\n<p><strong>For example<\/strong>, the following doubly linked list should be changed to 2&lt;-&gt;4&lt;-&gt;8&lt;-&gt;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-dll\"><span style=\"color: #000080;\">Doubly Linked List (DLL):<\/span><\/h2>\n<p>Doubly Linked List (DLL) is a list of elements and it varies from <a href=\"https:\/\/www.wikitechy.com\/technology\/java-programming-union-intersection-two-linked-lists\/\" target=\"_blank\" rel=\"noopener\">Linked List<\/a>. It allows navigation, <strong>either forward or backward<\/strong> when compared to <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> previous 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<figure id=\"attachment_31642\" aria-describedby=\"caption-attachment-31642\" style=\"width: 626px\" class=\"wp-caption aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\" wp-image-31642\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/10\/doubly-linked-list.gif\" alt=\"Doubly Linked List\" width=\"626\" height=\"142\" \/><figcaption id=\"caption-attachment-31642\" class=\"wp-caption-text\">Doubly Linked List<\/figcaption><\/figure>\n<h3 id=\"java-programming-implementation-of-merge-sort-for-doubly-linked-list\"><span style=\"color: #993300;\"><strong>JAVA Programming Implementation of merge sort for doubly linked list:<\/strong><\/span><\/h3>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">Java<\/span> <\/div> <pre class=\"language-java code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-java code-embed-code\"><br\/><br\/>class LinkedList {<br\/> <br\/>    static Node head;  <br\/> <br\/>  <br\/>    static class Node {<br\/> <br\/>        int data;<br\/>        Node next, prev;<br\/> <br\/>      <br\/>        Node(int d) {<br\/>            data = d;<br\/>            next = prev = null;<br\/>        }<br\/>    }<br\/> <br\/>    void print(Node node) {<br\/>        Node temp = node;<br\/>        System.out.println(&quot;Forward Traversal using next pointer&quot;);<br\/>        while (node != null) {<br\/>            System.out.print(node.data + &quot; &quot;);<br\/>            temp = node;<br\/>            node = node.next;<br\/>        }<br\/>        System.out.println(&quot;\\nBackward Traversal using prev pointer&quot;);<br\/>        while (temp != null) {<br\/>            System.out.print(temp.data + &quot; &quot;);<br\/>            temp = temp.prev;<br\/>        }<br\/>    }<br\/> <br\/>  <br\/>    Node split(Node head) {<br\/>        Node fast = head, slow = head;<br\/>        while (fast.next != null &amp;&amp; fast.next.next != null) {<br\/>            fast = fast.next.next;<br\/>            slow = slow.next;<br\/>        }<br\/>        Node temp = slow.next;<br\/>        slow.next = null;<br\/>        return temp;<br\/>    }<br\/> <br\/>    Node mergeSort(Node node) {<br\/>        if (node == null || node.next == null) {<br\/>            return node;<br\/>        }<br\/>        Node second = split(node);<br\/> <br\/>        <br\/>        node = mergeSort(node);<br\/>        second = mergeSort(second);<br\/> <br\/>        <br\/>        return merge(node, second);<br\/>    }<br\/> <br\/> <br\/>    Node merge(Node first, Node second) {<br\/>       <br\/>        if (first == null) {<br\/>            return second;<br\/>        }<br\/> <br\/>       <br\/>        if (second == null) {<br\/>            return first;<br\/>        }<br\/> <br\/>       <br\/>        if (first.data &lt; second.data) {<br\/>            first.next = merge(first.next, second);<br\/>            first.next.prev = first;<br\/>            first.prev = null;<br\/>            return first;<br\/>        } else {<br\/>            second.next = merge(first, second.next);<br\/>            second.next.prev = second;<br\/>            second.prev = null;<br\/>            return second;<br\/>        }<br\/>    }<br\/> <br\/>   <br\/>    public static void main(String[] args) {<br\/> <br\/>        LinkedList list = new LinkedList();<br\/>        list.head = new Node(10);<br\/>        list.head.next = new Node(30);<br\/>        list.head.next.next = new Node(3);<br\/>        list.head.next.next.next = new Node(4);<br\/>        list.head.next.next.next.next = new Node(20);<br\/>        list.head.next.next.next.next.next = new Node(5);<br\/>         <br\/>         <br\/>        Node node = null;<br\/>        node = list.mergeSort(head);<br\/>        System.out.println(&quot;Linked list after sorting :&quot;);<br\/>        list.print(node);<br\/> <br\/>    }<br\/>}<br\/> <\/code><\/pre> <\/div>\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><span style=\"color: #3366ff;\"><strong>Time Complexity: <\/strong><\/span>Time complexity of the above implementation is same as time complexity of MergeSort for <a href=\"https:\/\/www.wikitechy.com\/tutorials\/java\/arrays-in-java-example\" target=\"_blank\" rel=\"noopener\">arrays<\/a>. It takes<strong> \u0398(nLogn)<\/strong> time.<\/p>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>JAVA 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":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,2139,79476,83481,71670],"tags":[70250,72497,71272,70238,73367,70027,70028,70306,70233,73336,71386,70487,73368,70929,70889,70923,70877,71164,73326,70049,72405,72479,70262,71289,71268,71263,71714,71870,73340,70072,72489,73345,70652,71142,73338,70317,70022,70026,70544],"class_list":["post-25419","post","type-post","status-publish","format-standard","hentry","category-coding","category-java","category-linked-list","category-merge-sort","category-searching-and-sorting","tag-algorithm-complexity","tag-algorithm-for-linked-list","tag-algorithm-for-merge-sort","tag-algorithms-and-data-structures","tag-application-of-linked-list","tag-complexity-of-algorithm","tag-complexity-of-binary-search","tag-complexity-of-binary-search-algorithm","tag-data-structures-and-algorithms","tag-data-structures-and-algorithms-in-java","tag-data-structures-and-algorithms-in-java-tutorial","tag-doubly-linked-list","tag-doubly-linked-list-program-in-c","tag-heap-data-structure","tag-heap-in-data-structure","tag-heap-sort-algorithm-in-c","tag-heap-sort-time-complexity","tag-insertion-sort-algorithm-in-data-structure","tag-java-data-structures-and-algorithms","tag-linked-list","tag-linked-list-algorithm","tag-linked-list-in-data-structure","tag-merge-sort","tag-merge-sort-algorithm-in-c","tag-merge-sort-in-java","tag-merge-sort-java","tag-quicksort-algorithm-in-data-structure","tag-radix-sort-algorithm-in-data-structure","tag-reverse-a-linked-list","tag-searching-in-data-structure","tag-singly-linked-list-algorithm","tag-singly-linked-list-in-data-structure","tag-sorting-algorithms-in-c","tag-sorting-in-data-structure","tag-stack-in-data-structure","tag-the-complexity-of-binary-search-algorithm-is","tag-time-complexity","tag-time-complexity-of-binary-search","tag-time-complexity-of-merge-sort"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25419","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=25419"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25419\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25419"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25419"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25419"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}