Merge Sort for Doubly Linked List

Given a doubly linked list, write a function to sort the doubly linked list in increasing order using merge sort.

For example, the following doubly linked list should be changed to 2<->4<->8<->10

The important change here is to modify the previous pointers also when merging two lists.

Doubly Linked List (DLL):

Doubly Linked List (DLL) is a list of elements and it varies from Linked List. It allows navigation, either forward or backward when compared to Single Linked List. It has two pointers: previous pointer and next pointer. Every element points to next of the list and previous element in list.

Terms used in doubly linked list:

• Link
• Next
• Prev
• Linked list

JAVA Programming Implementation of merge sort for doubly linked list:

[pastacode lang=”java” manual=”%0A%0Aclass%20LinkedList%20%7B%0A%20%0A%20%20%20%20static%20Node%20head%3B%20%20%0A%20%0A%20%20%0A%20%20%20%20static%20class%20Node%20%7B%0A%20%0A%20%20%20%20%20%20%20%20int%20data%3B%0A%20%20%20%20%20%20%20%20Node%20next%2C%20prev%3B%0A%20%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20Node(int%20d)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20data%20%3D%20d%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20next%20%3D%20prev%20%3D%20null%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20void%20print(Node%20node)%20%7B%0A%20%20%20%20%20%20%20%20Node%20temp%20%3D%20node%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22Forward%20Traversal%20using%20next%20pointer%22)%3B%0A%20%20%20%20%20%20%20%20while%20(node%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(node.data%20%2B%20%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20node%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20node%20%3D%20node.next%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20System.out.println(%22%5CnBackward%20Traversal%20using%20prev%20pointer%22)%3B%0A%20%20%20%20%20%20%20%20while%20(temp%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(temp.data%20%2B%20%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20temp.prev%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%0A%20%20%20%20Node%20split(Node%20head)%20%7B%0A%20%20%20%20%20%20%20%20Node%20fast%20%3D%20head%2C%20slow%20%3D%20head%3B%0A%20%20%20%20%20%20%20%20while%20(fast.next%20!%3D%20null%20%26%26%20fast.next.next%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20fast%20%3D%20fast.next.next%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20slow%20%3D%20slow.next%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20Node%20temp%20%3D%20slow.next%3B%0A%20%20%20%20%20%20%20%20slow.next%20%3D%20null%3B%0A%20%20%20%20%20%20%20%20return%20temp%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20Node%20mergeSort(Node%20node)%20%7B%0A%20%20%20%20%20%20%20%20if%20(node%20%3D%3D%20null%20%7C%7C%20node.next%20%3D%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20node%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20Node%20second%20%3D%20split(node)%3B%0A%20%0A%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20node%20%3D%20mergeSort(node)%3B%0A%20%20%20%20%20%20%20%20second%20%3D%20mergeSort(second)%3B%0A%20%0A%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20return%20merge(node%2C%20second)%3B%0A%20%20%20%20%7D%0A%20%0A%20%0A%20%20%20%20Node%20merge(Node%20first%2C%20Node%20second)%20%7B%0A%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20if%20(first%20%3D%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20second%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20if%20(second%20%3D%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20first%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20if%20(first.data%20%3C%20second.data)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20first.next%20%3D%20merge(first.next%2C%20second)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20first.next.prev%20%3D%20first%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20first.prev%20%3D%20null%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20first%3B%0A%20%20%20%20%20%20%20%20%7D%20else%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20second.next%20%3D%20merge(first%2C%20second.next)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20second.next.prev%20%3D%20second%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20second.prev%20%3D%20null%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20second%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%0A%20%20%20%20public%20static%20void%20main(String%5B%5D%20args)%20%7B%0A%20%0A%20%20%20%20%20%20%20%20LinkedList%20list%20%3D%20new%20LinkedList()%3B%0A%20%20%20%20%20%20%20%20list.head%20%3D%20new%20Node(10)%3B%0A%20%20%20%20%20%20%20%20list.head.next%20%3D%20new%20Node(30)%3B%0A%20%20%20%20%20%20%20%20list.head.next.next%20%3D%20new%20Node(3)%3B%0A%20%20%20%20%20%20%20%20list.head.next.next.next%20%3D%20new%20Node(4)%3B%0A%20%20%20%20%20%20%20%20list.head.next.next.next.next%20%3D%20new%20Node(20)%3B%0A%20%20%20%20%20%20%20%20list.head.next.next.next.next.next%20%3D%20new%20Node(5)%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20Node%20node%20%3D%20null%3B%0A%20%20%20%20%20%20%20%20node%20%3D%20list.mergeSort(head)%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22Linked%20list%20after%20sorting%20%3A%22)%3B%0A%20%20%20%20%20%20%20%20list.print(node)%3B%0A%20%0A%20%20%20%20%7D%0A%7D%0A%20″ message=”Java” highlight=”” provider=”manual”/]

Output:

Linked List after sorting
Forward Traversal using next pointer
3 4 5 10 20 30
Backward Traversal using prev pointer
30 20 10 5 4 3

Time Complexity: Time complexity of the above implementation is same as time complexity of MergeSort for arrays. It takes Θ(nLogn) time.

[ad type=”banner”]