{"id":25438,"date":"2017-10-15T18:27:28","date_gmt":"2017-10-15T12:57:28","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25438"},"modified":"2017-10-15T18:27:28","modified_gmt":"2017-10-15T12:57:28","slug":"python-programming-merge-sort-doubly-linked-list","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-programming-merge-sort-doubly-linked-list\/","title":{"rendered":"PYTHON Programming-Merge Sort for Doubly Linked List"},"content":{"rendered":"<p>Given a doubly linked list, write a function to sort the doubly linked list in increasing order using merge sort.<\/p>\n<p>For example, the following doubly linked list should be changed to 2&lt;-&gt;4&lt;-&gt;8&lt;-&gt;10<\/p>\n<p><strong>We strongly recommend to minimize your browser and try this yourself first.<\/strong><br \/>\nMerge 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<p>Below is the implementation of merge sort for doubly linked list.<\/p>\n<p><strong>Python Programming<\/strong><\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">Python<\/span> <\/div> <pre class=\"language-python code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-python code-embed-code\"># Program for merge sort on doubly linked list<br\/> <br\/># A node of the doublly linked list<br\/>class Node:<br\/>     <br\/>    # Constructor to create a new node<br\/>    def __init__(self, data):<br\/>        self.data = data <br\/>        self.next = None<br\/>        self.prev = None<br\/> <br\/>class DoublyLinkedList:<br\/> <br\/>     # Constructor for empty Doubly Linked List<br\/>    def __init__(self):<br\/>        self.head = None<br\/> <br\/>    # Function to merge two linked list<br\/>    def merge(self, first, second):<br\/>         <br\/>        # If first linked list is empty<br\/>        if first is None:<br\/>            return second <br\/>         <br\/>        # If secon linked list is empty <br\/>        if second is None:<br\/>            return first<br\/> <br\/>        # Pick the smaller value<br\/>        if first.data &lt; second.data:<br\/>            first.next = self.merge(first.next, second)<br\/>            first.next.prev = first<br\/>            first.prev = None  <br\/>            return first<br\/>        else:<br\/>            second.next = self.merge(first, second.next)<br\/>            second.next.prev = second<br\/>            second.prev = None<br\/>            return second<br\/> <br\/>    # Function to do merge sort<br\/>    def mergeSort(self, tempHead):<br\/>        if tempHead is None: <br\/>            return tempHead<br\/>        if tempHead.next is None:<br\/>            return tempHead<br\/>         <br\/>        second = self.split(tempHead)<br\/>         <br\/>        # Recur for left and righ halves<br\/>        tempHead = self.mergeSort(tempHead)<br\/>        second = self.mergeSort(second)<br\/> <br\/>        # Merge the two sorted halves<br\/>        return self.merge(tempHead, second)<br\/> <br\/>    # Split the doubly linked list (DLL) into two DLLs<br\/>    # of half sizes<br\/>    def split(self, tempHead):<br\/>        fast = slow =  tempHead<br\/>        while(True):<br\/>            if fast.next is None:<br\/>                break<br\/>            if fast.next.next is None:<br\/>                break<br\/>            fast = fast.next.next<br\/>            slow = slow.next<br\/>             <br\/>        temp = slow.next<br\/>        slow.next = None<br\/>        return temp<br\/>         <br\/>             <br\/>    # Given a reference to the head of a list and an<br\/>    # integer,inserts a new node on the front of list<br\/>    def push(self, new_data):<br\/>  <br\/>        # 1. Allocates node<br\/>        # 2. Put the data in it<br\/>        new_node = Node(new_data)<br\/>  <br\/>        # 3. Make next of new node as head and<br\/>        # previous as None (already None)<br\/>        new_node.next = self.head<br\/>  <br\/>        # 4. change prev of head node to new_node<br\/>        if self.head is not None:<br\/>            self.head.prev = new_node<br\/>  <br\/>        # 5. move the head to point to the new node<br\/>        self.head = new_node<br\/> <br\/> <br\/>    def printList(self, node):<br\/>        temp = node<br\/>        print &quot;Forward Traversal using next poitner&quot;<br\/>        while(node is not None):<br\/>            print node.data,<br\/>            temp = node<br\/>            node = node.next<br\/>        print &quot;\\nBackward Traversal using prev pointer&quot;<br\/>        while(temp):<br\/>            print temp.data,<br\/>            temp = temp.prev<br\/> <br\/># Driver program to test the above functions<br\/>dll = DoublyLinkedList()<br\/>dll.push(5)<br\/>dll.push(20);<br\/>dll.push(4);<br\/>dll.push(3);<br\/>dll.push(30)<br\/>dll.push(10);<br\/>dll.head = dll.mergeSort(dll.head)   <br\/>print &quot;Linked List after sorting&quot;<br\/>dll.printList(dll.head)<\/code><\/pre> <\/div>\n<p><strong>Output:<\/strong><\/p>\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><strong>Time Complexity: <\/strong>Time complexity of the above implementation is same as time complexity of MergeSort for arrays. It takes \u0398(nLogn) time.<\/p>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>PYTHON 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":[69969,1,79476,83481,83517,71670],"tags":[73379,73375,73376,72497,71272,70238,73367,70284,71140,71129,71152,73380,70306,70048,70233,73329,73369,70889,70928,70923,70875,70877,71164,73326,73377,72405,73374,73373,73337,73378,71262,71872,71289,71280,71288,70938,71290,73370,71714,71870,70072,72489,73381,73345,73372,70020,71142,73371,70026,70544],"class_list":["post-25438","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-coding","category-linked-list","category-merge-sort","category-python-programming","category-searching-and-sorting","tag-algorithm-data-structure","tag-algorithm-for-doubly-linked-list-in-data-structure","tag-algorithm-for-insertion-and-deletion-in-doubly-linked-list","tag-algorithm-for-linked-list","tag-algorithm-for-merge-sort","tag-algorithms-and-data-structures","tag-application-of-linked-list","tag-binary-search-tree-in-data-structure","tag-bubble-sort-in-c-program","tag-bubble-sort-program","tag-c-program-for-bubble-sort","tag-c-programming-interview-questions-pdf","tag-complexity-of-binary-search-algorithm","tag-data-structures","tag-data-structures-and-algorithms","tag-data-structures-and-algorithms-pdf","tag-data-structures-and-algorithms-tutorial","tag-heap-in-data-structure","tag-heap-sort-algorithm","tag-heap-sort-algorithm-in-c","tag-heap-sort-algorithm-with-example","tag-heap-sort-time-complexity","tag-insertion-sort-algorithm-in-data-structure","tag-java-data-structures-and-algorithms","tag-java-solutions","tag-linked-list-algorithm","tag-linked-list-algorithm-in-c","tag-linked-list-in-cpp","tag-linked-list-program-in-c","tag-linkedin","tag-merge-sort-algorithm","tag-merge-sort-algorithm-c-code","tag-merge-sort-algorithm-in-c","tag-merge-sort-c-code","tag-merge-sort-c-program","tag-merge-sort-in-c","tag-merge-sort-in-c-program","tag-merge-two-sorted-linked-list-in-c","tag-quicksort-algorithm-in-data-structure","tag-radix-sort-algorithm-in-data-structure","tag-searching-in-data-structure","tag-singly-linked-list-algorithm","tag-singly-linked-list-in-c-program","tag-singly-linked-list-in-data-structure","tag-singly-linked-list-program-in-c","tag-sorting-algorithms","tag-sorting-in-data-structure","tag-the-worst-case-occur-in-linear-search-algorithm-when","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\/25438","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=25438"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25438\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25438"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25438"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25438"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}