Merge Sort for Doubly Linked List

JAVA Programming-Merge Sort for Doubly Linked List – Searching and Sorting – Merge sort for singly linked list is already discussed. The important change here is to modify the previous pointers also when merging two lists.

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
Doubly Linked List
Doubly 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(!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(!!%3D%20null)″ message=”Java” highlight=”” provider=”manual”/]


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.

Leave a Reply

Your email address will not be published. Required fields are marked *

You May Also Like