# 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) 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:

• Next
• Prev

### JAVA Programming Implementation of merge sort for doubly linked list:

Java
``````

static class Node {

int data;
Node next, prev;

Node(int d) {
data = d;
next = prev = null;
}
}

void print(Node node) {
Node temp = node;
System.out.println("Forward Traversal using next pointer");
while (node != null) {
System.out.print(node.data + " ");
temp = node;
node = node.next;
}
System.out.println("\nBackward Traversal using prev pointer");
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.prev;
}
}

while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
Node temp = slow.next;
slow.next = null;
return temp;
}

Node mergeSort(Node node) {
if (node == null || node.next == null) {
return node;
}
Node second = split(node);

node = mergeSort(node);
second = mergeSort(second);

return merge(node, second);
}

Node merge(Node first, Node second) {

if (first == null) {
return second;
}

if (second == null) {
return first;
}

if (first.data < second.data) {
first.next = merge(first.next, second);
first.next.prev = first;
first.prev = null;
return first;
} else {
second.next = merge(first, second.next);
second.next.prev = second;
second.prev = null;
return second;
}
}

public static void main(String[] args) {

Node node = null;
list.print(node);

}
}
``````

### 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. #### Venkatesan Prabu

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

X