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:
- Linked list
JAVA Programming Implementation of merge sort for doubly linked list:
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.