Merge sort on doubly linked list
Merge sort is a sorting algorithm that works by dividing the input array or linked list into smaller arrays or linked lists, sorting them recursively, and then merging them back together into a single, sorted output.
When applied to a doubly linked list, Merge sort works by dividing the list into two halves and recursively sorting each half. This is done by using a divide-and-conquer approach, where the list is repeatedly divided into smaller sub-lists until each sub-list contains only one element (which is already sorted).
After each sub-list is sorted, the two halves are merged back together by comparing the first element of each half and selecting the smaller one to be added to the sorted output list. This process is repeated until all elements have been merged back together into a single, sorted doubly linked list.
One advantage of using Merge sort on a doubly linked list is that it is relatively easy to implement because the links between the nodes can be easily adjusted during the merge process. Additionally, Merge sort has a time complexity of O(nlogn) in the worst case, which makes it efficient for large lists.
Program Solution
/*
C Program
Merge sort for doubly linked list
*/
#include <stdio.h>
#include <stdlib.h>
// Linked List LinkNode
struct LinkNode
{
int element;
struct LinkNode *next;
struct LinkNode *prev;
};
struct DoublyLL
{
struct LinkNode *front;
struct LinkNode *rear;
};
// Returns the new linked list
struct DoublyLL *newLinkedList()
{
struct DoublyLL *dll = (struct DoublyLL *) malloc(sizeof(struct DoublyLL));
if (dll == NULL)
{
printf("Memory overflow\n");
}
else
{
dll->front = NULL;
dll->rear = NULL;
}
return dll;
}
// Add node at end of Doubly linked list
void addNode(struct DoublyLL *dll, int element)
{
// Make a new node
struct LinkNode *node = (struct LinkNode *) malloc(sizeof(struct LinkNode));
if (node != NULL)
{
// Set node values
node->element = element;
node->next = NULL;
node->prev = NULL;
if (dll->front == NULL)
{
// When inserting a first node of doubly linked list
dll->front = node;
dll->rear = node;
}
else
{
// Add node at end position
dll->rear->next = node;
node->prev = dll->rear;
dll->rear = node;
}
}
else
{
printf("\n Memory Overflow, when creating a new doubly linked list Node\n");
}
}
// Display element
void printData(struct DoublyLL *dll)
{
struct LinkNode *node = dll->front;
printf("\n Linked List of from front to rear \n");
// Display node of from front to rear
while (node != NULL)
{
printf(" %d →", node->element);
node = node->next;
}
printf(" NULL ");
printf("\n Linked List of from rear to front \n");
node = dll->rear;
// Display node of from rear to front
while (node != NULL)
{
printf(" %d →", node->element);
node = node->prev;
}
printf(" NULL \n");
}
//This are returning middle node of given linked list
struct LinkNode *middleNode(struct LinkNode *head, struct LinkNode *tail)
{
if (head->next == NULL || head == tail)
{
return head;
}
else
{
//Auxiliary variables
struct LinkNode *low = head;
struct LinkNode *high = head;
while (high != NULL && high->next != NULL && high->next->next != NULL && high->next != tail && head->next->next != tail)
{
//visit to next node
low = low->next;
//visit to second next node
high = high->next->next;
}
//This is middle element
return low;
}
}
// Merge two sorted list and return its result
struct LinkNode *mergeList(struct LinkNode *list1, struct LinkNode *list2)
{
if (list1 == NULL)
{
//When list1 is empty
return list2;
}
else if (list2 == NULL)
{
return list1;
}
else
{
// Some auxiliary variables
struct LinkNode *result = NULL;
struct LinkNode *tail = NULL;
struct LinkNode *node = NULL;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != NULL || list2 != NULL)
{
if (list1 != NULL && list2 != NULL)
{
//When both list contain nodes
if (list1->element < list2->element)
{
//When first list element are smallest
node = list1;
list1 = list1->next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2->next;
}
}
else if (list1 != NULL)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = NULL;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = NULL;
}
if (result == NULL)
{
//When get first node of resultant list
result = node;
node->next = NULL;
node->prev = NULL;
}
else
{
//Add node at end of resultant list
tail->next = node;
node->prev = tail;
}
tail = node;
}
return result;
}
}
// Perform merge sort
struct LinkNode *mergeSort(struct LinkNode *head, struct LinkNode *tail)
{
if (head == NULL || head == tail || head->next == NULL)
{
// When have zero or one node
return head;
}
// Find the relative middle node
struct LinkNode *middle = middleNode(head, tail);
// Get the right sublist
struct LinkNode *right = mergeSort(middle->next, tail);
// Separating sublist
if (middle->next != NULL)
{
middle->next->prev = NULL;
}
middle->next = NULL;
//Get the left sublist
struct LinkNode *left = mergeSort(head, middle);
// Sorted merge in two list
return mergeList(left, right);
}
// Handles the request to perform merge sort operation
void sortList(struct DoublyLL *dll)
{
dll->front = mergeSort(dll->front, dll->rear);
struct LinkNode *node = dll->front;
// First last node
while (node->next != NULL)
{
node = node->next;
}
// Set new rear node
dll->rear = node;
}
int main(int argc, char
const *argv[])
{
struct DoublyLL *dll = newLinkedList();
addNode(dll, 5);
addNode(dll, 3);
addNode(dll, 7);
addNode(dll, 1);
addNode(dll, 9);
addNode(dll, 6);
addNode(dll, 2);
addNode(dll, 8);
addNode(dll, -2);
addNode(dll, 0);
printf("\n Before Sort ");
// 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
printData(dll);
sortList(dll);
printf("\n After Sort ");
//-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
printData(dll);
return 0;
}Output
Before Sort
Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL
After Sort
Linked List of from front to rear
-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
Linked List of from rear to front
9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL/*
Java Program
Merge sort for doubly linked list
*/
class LinkNode
{
public int element;
public LinkNode next;
public LinkNode prev;
public LinkNode(int element)
{
this.element = element;
this.next = null;
this.prev = null;
}
}
class DoublyLL
{
public LinkNode front;
public LinkNode rear;
public DoublyLL()
{
this.front = null;
this.rear = null;
}
// Add node at end of Doubly linked list
public void addNode(int element)
{
// Make a new node
LinkNode node = new LinkNode(element);
if (this.front == null)
{
// When inserting a first node of doubly linked list
this.front = node;
this.rear = node;
}
else
{
// Add node at end position
this.rear.next = node;
node.prev = this.rear;
this.rear = node;
}
}
// Display element
public void printData()
{
LinkNode node = this.front;
System.out.print("\n Linked List of from front to rear \n");
// Display node of from front to rear
while (node != null)
{
System.out.print(" " + node.element + " →");
node = node.next;
}
System.out.print(" NULL ");
System.out.print("\n Linked List of from rear to front \n");
node = this.rear;
// Display node of from rear to front
while (node != null)
{
System.out.print(" " + node.element + " →");
node = node.prev;
}
System.out.print(" NULL \n");
}
}
public class Sorting
{
//This are returning middle node of given linked list
public LinkNode middleNode(LinkNode head, LinkNode tail)
{
if (head.next == null || head == tail)
{
return head;
}
else
{
//Auxiliary variables
LinkNode low = head;
LinkNode high = head;
while (high != null && high.next != null && high.next.next != null && high.next != tail && head.next.next != tail)
{
//visit to next node
low = low.next;
//visit to second next node
high = high.next.next;
}
//This is middle element
return low;
}
}
// Merge two sorted list and return its result
public LinkNode mergeList(LinkNode list1, LinkNode list2)
{
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
// Some auxiliary variables
LinkNode result = null;
LinkNode tail = null;
LinkNode node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
//When both list contain nodes
if (list1.element < list2.element)
{
//When first list element are smallest
node = list1;
list1 = list1.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = null;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = null;
}
if (result == null)
{
//When get first node of resultant list
result = node;
node.next = null;
node.prev = null;
}
else
{
//Add node at end of resultant list
tail.next = node;
node.prev = tail;
}
tail = node;
}
return result;
}
}
// Perform merge sort
public LinkNode mergeSort(LinkNode head, LinkNode tail)
{
if (head == null || head == tail || head.next == null)
{
// When have zero or one node
return head;
}
// Find the relative middle node
LinkNode middle = middleNode(head, tail);
// Get the right sublist
LinkNode right = mergeSort(middle.next, tail);
// Separating sublist
if (middle.next != null)
{
middle.next.prev = null;
}
middle.next = null;
//Get the left sublist
LinkNode left = mergeSort(head, middle);
// Sorted merge in two list
return mergeList(left, right);
}
// Handles the request to perform merge sort operation
public void sortList(DoublyLL dll)
{
dll.front = mergeSort(dll.front, dll.rear);
LinkNode node = dll.front;
// First last node
while (node.next != null)
{
node = node.next;
}
// Set new rear node
dll.rear = node;
}
public static void main(String[] args)
{
DoublyLL dll = new DoublyLL();
Sorting task = new Sorting();
dll.addNode(5);
dll.addNode(3);
dll.addNode(7);
dll.addNode(1);
dll.addNode(9);
dll.addNode(6);
dll.addNode(2);
dll.addNode(8);
dll.addNode(-2);
dll.addNode(0);
System.out.print("\n Before Sort \n");
// 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
dll.printData();
task.sortList(dll);
System.out.print("\n After Sort \n");
//-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
dll.printData();
}
}Output
Before Sort
Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL
After Sort
Linked List of from front to rear
-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
Linked List of from rear to front
9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Merge sort for doubly linked list
*/
class LinkNode
{
public: int element;
LinkNode *next;
LinkNode *prev;
LinkNode(int element)
{
this->element = element;
this->next = NULL;
this->prev = NULL;
}
};
class DoublyLL
{
public: LinkNode *front;
LinkNode *rear;
DoublyLL()
{
this->front = NULL;
this->rear = NULL;
}
// Add node at end of Doubly linked list
void addNode(int element)
{
// Make a new node
LinkNode *node = new LinkNode(element);
if (this->front == NULL)
{
// When inserting a first node of doubly linked list
this->front = node;
this->rear = node;
}
else
{
// Add node at end position
this->rear->next = node;
node->prev = this->rear;
this->rear = node;
}
}
// Display element
void printData()
{
LinkNode *node = this->front;
cout << "\n Linked List of from front to rear \n";
// Display node of from front to rear
while (node != NULL)
{
cout << " " << node->element << " →";
node = node->next;
}
cout << " NULL ";
cout << "\n Linked List of from rear to front \n";
node = this->rear;
// Display node of from rear to front
while (node != NULL)
{
cout << " " << node->element << " →";
node = node->prev;
}
cout << " NULL \n";
}
};
class Sorting
{
public:
//This are returning middle node of given linked list
LinkNode *middleNode(LinkNode *head, LinkNode *tail)
{
if (head->next == NULL || head == tail)
{
return head;
}
else
{
//This is middle element
//Auxiliary variables
LinkNode *low = head;
LinkNode *high = head;
while (high != NULL && high->next != NULL && high->next->next != NULL && high->next != tail && head->next->next != tail)
{
//visit to next node
low = low->next;
//visit to second next node
high = high->next->next;
}
return low;
}
}
// Merge two sorted list and return its result
LinkNode *mergeList(LinkNode *list1, LinkNode *list2)
{
if (list1 == NULL)
{
//When list1 is empty
return list2;
}
else if (list2 == NULL)
{
return list1;
}
else
{
// Some auxiliary variables
LinkNode *result = NULL;
LinkNode *tail = NULL;
LinkNode *node = NULL;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != NULL || list2 != NULL)
{
if (list1 != NULL && list2 != NULL)
{
//When both list contain nodes
if (list1->element < list2->element)
{
//When first list element are smallest
node = list1;
list1 = list1->next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2->next;
}
}
else if (list1 != NULL)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = NULL;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = NULL;
}
if (result == NULL)
{
//When get first node of resultant list
result = node;
node->next = NULL;
node->prev = NULL;
}
else
{
//Add node at end of resultant list
tail->next = node;
node->prev = tail;
}
tail = node;
}
return result;
}
}
// Perform merge sort
LinkNode *mergeSort(LinkNode *head, LinkNode *tail)
{
if (head == NULL || head == tail || head->next == NULL)
{
// When have zero or one node
return head;
}
// Find the relative middle node
LinkNode *middle = this->middleNode(head, tail);
// Get the right sublist
LinkNode *right = this->mergeSort(middle->next, tail);
// Separating sublist
if (middle->next != NULL)
{
middle->next->prev = NULL;
}
middle->next = NULL;
//Get the left sublist
LinkNode *left = this->mergeSort(head, middle);
// Sorted merge in two list
return this->mergeList(left, right);
}
// Handles the request to perform merge sort operation
void sortList(DoublyLL *dll)
{
dll->front = this->mergeSort(dll->front, dll->rear);
LinkNode *node = dll->front;
// First last node
while (node->next != NULL)
{
node = node->next;
}
// Set new rear node
dll->rear = node;
}
};
int main()
{
DoublyLL dll = DoublyLL();
Sorting task = Sorting();
dll.addNode(5);
dll.addNode(3);
dll.addNode(7);
dll.addNode(1);
dll.addNode(9);
dll.addNode(6);
dll.addNode(2);
dll.addNode(8);
dll.addNode(-2);
dll.addNode(0);
cout << "\n Before Sort \n";
// 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
dll.printData();
task.sortList(&dll);
cout << "\n After Sort \n";
//-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
dll.printData();
return 0;
}Output
Before Sort
Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL
After Sort
Linked List of from front to rear
-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
Linked List of from rear to front
9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL// Include namespace system
using System;
/*
C# Program
Merge sort for doubly linked list
*/
public class LinkNode
{
public int element;
public LinkNode next;
public LinkNode prev;
public LinkNode(int element)
{
this.element = element;
this.next = null;
this.prev = null;
}
}
public class DoublyLL
{
public LinkNode front;
public LinkNode rear;
public DoublyLL()
{
this.front = null;
this.rear = null;
}
// Add node at end of Doubly linked list
public void addNode(int element)
{
// Make a new node
LinkNode node = new LinkNode(element);
if (this.front == null)
{
// When inserting a first node of doubly linked list
this.front = node;
this.rear = node;
}
else
{
// Add node at end position
this.rear.next = node;
node.prev = this.rear;
this.rear = node;
}
}
// Display element
public void printData()
{
LinkNode node = this.front;
Console.Write("\n Linked List of from front to rear \n");
// Display node of from front to rear
while (node != null)
{
Console.Write(" " + node.element + " →");
node = node.next;
}
Console.Write(" NULL ");
Console.Write("\n Linked List of from rear to front \n");
node = this.rear;
// Display node of from rear to front
while (node != null)
{
Console.Write(" " + node.element + " →");
node = node.prev;
}
Console.Write(" NULL \n");
}
}
public class Sorting
{
//This are returning middle node of given linked list
public LinkNode middleNode(LinkNode head, LinkNode tail)
{
if (head.next == null || head == tail)
{
return head;
}
else
{
//This is middle element
//Auxiliary variables
LinkNode low = head;
LinkNode high = head;
while (high != null && high.next != null && high.next.next != null && high.next != tail && head.next.next != tail)
{
//visit to next node
low = low.next;
//visit to second next node
high = high.next.next;
}
return low;
}
}
// Merge two sorted list and return its result
public LinkNode mergeList(LinkNode list1, LinkNode list2)
{
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
// Some auxiliary variables
LinkNode result = null;
LinkNode tail = null;
LinkNode node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
//When both list contain nodes
if (list1.element < list2.element)
{
//When first list element are smallest
node = list1;
list1 = list1.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = null;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = null;
}
if (result == null)
{
//When get first node of resultant list
result = node;
node.next = null;
node.prev = null;
}
else
{
//Add node at end of resultant list
tail.next = node;
node.prev = tail;
}
tail = node;
}
return result;
}
}
// Perform merge sort
public LinkNode mergeSort(LinkNode head, LinkNode tail)
{
if (head == null || head == tail || head.next == null)
{
// When have zero or one node
return head;
}
// Find the relative middle node
LinkNode middle = middleNode(head, tail);
// Get the right sublist
LinkNode right = mergeSort(middle.next, tail);
// Separating sublist
if (middle.next != null)
{
middle.next.prev = null;
}
middle.next = null;
//Get the left sublist
LinkNode left = mergeSort(head, middle);
// Sorted merge in two list
return mergeList(left, right);
}
// Handles the request to perform merge sort operation
public void sortList(DoublyLL dll)
{
dll.front = mergeSort(dll.front, dll.rear);
LinkNode node = dll.front;
// First last node
while (node.next != null)
{
node = node.next;
}
// Set new rear node
dll.rear = node;
}
public static void Main(String[] args)
{
DoublyLL dll = new DoublyLL();
Sorting task = new Sorting();
dll.addNode(5);
dll.addNode(3);
dll.addNode(7);
dll.addNode(1);
dll.addNode(9);
dll.addNode(6);
dll.addNode(2);
dll.addNode(8);
dll.addNode(-2);
dll.addNode(0);
Console.Write("\n Before Sort \n");
// 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
dll.printData();
task.sortList(dll);
Console.Write("\n After Sort \n");
//-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
dll.printData();
}
}Output
Before Sort
Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL
After Sort
Linked List of from front to rear
-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
Linked List of from rear to front
9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL<?php
/*
Php Program
Merge sort for doubly linked list
*/
class LinkNode
{
public $element;
public $next;
public $prev;
function __construct($element)
{
$this->element = $element;
$this->next = null;
$this->prev = null;
}
}
class DoublyLL
{
public $front;
public $rear;
function __construct()
{
$this->front = null;
$this->rear = null;
}
// Add node at end of Doubly linked list
public function addNode($element)
{
// Make a new node
$node = new LinkNode($element);
if ($this->front == null)
{
// When inserting a first node of doubly linked list
$this->front = $node;
$this->rear = $node;
}
else
{
// Add node at end position
$this->rear->next = $node;
$node->prev = $this->rear;
$this->rear = $node;
}
}
// Display element
public function printData()
{
$node = $this->front;
echo "\n Linked List of from front to rear \n";
// Display node of from front to rear
while ($node != null)
{
echo " ". $node->element ." →";
$node = $node->next;
}
echo " NULL ";
echo "\n Linked List of from rear to front \n";
$node = $this->rear;
// Display node of from rear to front
while ($node != null)
{
echo " ". $node->element ." →";
$node = $node->prev;
}
echo " NULL \n";
}
}
class Sorting
{
//This are returning middle node of given linked list
public function middleNode($head, $tail)
{
if ($head->next == null || $head == $tail)
{
return $head;
}
else
{
//This is middle element
//Auxiliary variables
$low = $head;
$high = $head;
while ($high != null && $high->next != null && $high->next->next != null && $high->next != $tail && $head->next->next != $tail)
{
//visit to next node
$low = $low->next;
//visit to second next node
$high = $high->next->next;
}
return $low;
}
}
// Merge two sorted list and return its result
public function mergeList($list1, $list2)
{
if ($list1 == null)
{
//When list1 is empty
return $list2;
}
else if ($list2 == null)
{
return $list1;
}
else
{
// Some auxiliary variables
$result = null;
$tail = null;
$node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while ($list1 != null || $list2 != null)
{
if ($list1 != null && $list2 != null)
{
//When both list contain nodes
if ($list1->element < $list2->element)
{
//When first list element are smallest
$node = $list1;
$list1 = $list1->next;
}
else
{
//When second list element are smallest
$node = $list2;
$list2 = $list2->next;
}
}
else if ($list1 != null)
{
//When first list contain element
//Get sublist
$node = $list1;
//Set that list1 empty
$list1 = null;
}
else
{
//When second list contain element
//get sublist
$node = $list2;
$list2 = null;
}
if ($result == null)
{
//When get first node of resultant list
$result = $node;
$node->next = null;
$node->prev = null;
}
else
{
//Add node at end of resultant list
$tail->next = $node;
$node->prev = $tail;
}
$tail = $node;
}
return $result;
}
}
// Perform merge sort
public function mergeSort($head, $tail)
{
if ($head == null || $head == $tail || $head->next == null)
{
// When have zero or one node
return $head;
}
// Find the relative middle node
$middle = $this->middleNode($head, $tail);
// Get the right sublist
$right = $this->mergeSort($middle->next, $tail);
// Separating sublist
if ($middle->next != null)
{
$middle->next->prev = null;
}
$middle->next = null;
//Get the left sublist
$left = $this->mergeSort($head, $middle);
// Sorted merge in two list
return $this->mergeList($left, $right);
}
// Handles the request to perform merge sort operation
public function sortList($dll)
{
$dll->front = $this->mergeSort($dll->front, $dll->rear);
$node = $dll->front;
// First last node
while ($node->next != null)
{
$node = $node->next;
}
// Set new rear node
$dll->rear = $node;
}
}
function main()
{
$dll = new DoublyLL();
$task = new Sorting();
$dll->addNode(5);
$dll->addNode(3);
$dll->addNode(7);
$dll->addNode(1);
$dll->addNode(9);
$dll->addNode(6);
$dll->addNode(2);
$dll->addNode(8);
$dll->addNode(-2);
$dll->addNode(0);
echo "\n Before Sort \n";
// 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
$dll->printData();
$task->sortList($dll);
echo "\n After Sort \n";
//-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
$dll->printData();
}
main();Output
Before Sort
Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL
After Sort
Linked List of from front to rear
-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
Linked List of from rear to front
9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL/*
Node Js Program
Merge sort for doubly linked list
*/
class LinkNode
{
constructor(element)
{
this.element = element;
this.next = null;
this.prev = null;
}
}
class DoublyLL
{
constructor()
{
this.front = null;
this.rear = null;
}
// Add node at end of Doubly linked list
addNode(element)
{
// Make a new node
var node = new LinkNode(element);
if (this.front == null)
{
// When inserting a first node of doubly linked list
this.front = node;
this.rear = node;
}
else
{
// Add node at end position
this.rear.next = node;
node.prev = this.rear;
this.rear = node;
}
}
// Display element
printData()
{
var node = this.front;
process.stdout.write("\n Linked List of from front to rear \n");
// Display node of from front to rear
while (node != null)
{
process.stdout.write(" " + node.element + " →");
node = node.next;
}
process.stdout.write(" NULL ");
process.stdout.write("\n Linked List of from rear to front \n");
node = this.rear;
// Display node of from rear to front
while (node != null)
{
process.stdout.write(" " + node.element + " →");
node = node.prev;
}
process.stdout.write(" NULL \n");
}
}
class Sorting
{
//This are returning middle node of given linked list
middleNode(head, tail)
{
if (head.next == null || head == tail)
{
return head;
}
else
{
//This is middle element
//Auxiliary variables
var low = head;
var high = head;
while (high != null && high.next != null && high.next.next != null && high.next != tail && head.next.next != tail)
{
//visit to next node
low = low.next;
//visit to second next node
high = high.next.next;
}
return low;
}
}
// Merge two sorted list and return its result
mergeList(list1, list2)
{
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
// Some auxiliary variables
var result = null;
var tail = null;
var node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
//When both list contain nodes
if (list1.element < list2.element)
{
//When first list element are smallest
node = list1;
list1 = list1.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = null;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = null;
}
if (result == null)
{
//When get first node of resultant list
result = node;
node.next = null;
node.prev = null;
}
else
{
//Add node at end of resultant list
tail.next = node;
node.prev = tail;
}
tail = node;
}
return result;
}
}
// Perform merge sort
mergeSort(head, tail)
{
if (head == null || head == tail || head.next == null)
{
// When have zero or one node
return head;
}
// Find the relative middle node
var middle = this.middleNode(head, tail);
// Get the right sublist
var right = this.mergeSort(middle.next, tail);
// Separating sublist
if (middle.next != null)
{
middle.next.prev = null;
}
middle.next = null;
//Get the left sublist
var left = this.mergeSort(head, middle);
// Sorted merge in two list
return this.mergeList(left, right);
}
// Handles the request to perform merge sort operation
sortList(dll)
{
dll.front = this.mergeSort(dll.front, dll.rear);
var node = dll.front;
// First last node
while (node.next != null)
{
node = node.next;
}
// Set new rear node
dll.rear = node;
}
}
function main()
{
var dll = new DoublyLL();
var task = new Sorting();
dll.addNode(5);
dll.addNode(3);
dll.addNode(7);
dll.addNode(1);
dll.addNode(9);
dll.addNode(6);
dll.addNode(2);
dll.addNode(8);
dll.addNode(-2);
dll.addNode(0);
process.stdout.write("\n Before Sort \n");
// 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
dll.printData();
task.sortList(dll);
process.stdout.write("\n After Sort \n");
//-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
dll.printData();
}
main();Output
Before Sort
Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL
After Sort
Linked List of from front to rear
-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
Linked List of from rear to front
9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL# Python 3 Program
# Merge sort for doubly linked list
class LinkNode :
def __init__(self, element) :
self.element = element
self.next = None
self.prev = None
class DoublyLL :
def __init__(self) :
self.front = None
self.rear = None
# Add node at end of Doubly linked list
def addNode(self, element) :
# Make a new node
node = LinkNode(element)
if (self.front == None) :
# When inserting a first node of doubly linked list
self.front = node
self.rear = node
else :
# Add node at end position
self.rear.next = node
node.prev = self.rear
self.rear = node
# Display element
def printData(self) :
node = self.front
print("\n Linked List of from front to rear ")
# Display node of from front to rear
while (node != None) :
print("", node.element ,"→", end = "")
node = node.next
print(" NULL ", end = "")
print("\n Linked List of from rear to front ")
node = self.rear
# Display node of from rear to front
while (node != None) :
print("", node.element ,"→", end = "")
node = node.prev
print(" NULL ")
class Sorting :
# This are returning middle node of given linked list
def middleNode(self, head, tail) :
if (head.next == None or head == tail) :
return head
else :
# Auxiliary variables
low = head
high = head
while (high != None and high.next != None and high.next.next != None and high.next != tail and head.next.next != tail) :
# visit to next node
low = low.next
# visit to second next node
high = high.next.next
# This is middle element
return low
# Merge two sorted list and return its result
def mergeList(self, list1, list2) :
if (list1 == None) :
# When list1 is empty
return list2
elif(list2 == None) :
return list1
else :
# Some auxiliary variables
result = None
tail = None
node = None
# Combine list elements in sorted order
# This process takes(m+n) time
# Here m is size of list1
# And n is size of list2
while (list1 != None or list2 != None) :
if (list1 != None and list2 != None) :
# When both list contain nodes
if (list1.element < list2.element) :
# When first list element are smallest
node = list1
list1 = list1.next
else :
# When second list element are smallest
node = list2
list2 = list2.next
elif(list1 != None) :
# When first list contain element
# Get sublist
node = list1
# Set that list1 empty
list1 = None
else :
# When second list contain element
# get sublist
node = list2
list2 = None
if (result == None) :
# When get first node of resultant list
result = node
node.next = None
node.prev = None
else :
# Add node at end of resultant list
tail.next = node
node.prev = tail
tail = node
return result
# Perform merge sort
def mergeSort(self, head, tail) :
if (head == None or head == tail or head.next == None) :
# When have zero or one node
return head
# Find the relative middle node
middle = self.middleNode(head, tail)
# Get the right sublist
right = self.mergeSort(middle.next, tail)
# Separating sublist
if (middle.next != None) :
middle.next.prev = None
middle.next = None
# Get the left sublist
left = self.mergeSort(head, middle)
# Sorted merge in two list
return self.mergeList(left, right)
# Handles the request to perform merge sort operation
def sortList(self, dll) :
dll.front = self.mergeSort(dll.front, dll.rear)
node = dll.front
# First last node
while (node.next != None) :
node = node.next
# Set new rear node
dll.rear = node
def main() :
dll = DoublyLL()
task = Sorting()
dll.addNode(5)
dll.addNode(3)
dll.addNode(7)
dll.addNode(1)
dll.addNode(9)
dll.addNode(6)
dll.addNode(2)
dll.addNode(8)
dll.addNode(-2)
dll.addNode(0)
print("\n Before Sort ")
# 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
dll.printData()
task.sortList(dll)
print("\n After Sort ")
# -2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
dll.printData()
if __name__ == "__main__": main()Output
Before Sort
Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL
After Sort
Linked List of from front to rear
-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
Linked List of from rear to front
9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL# Ruby Program
# Merge sort for doubly linked list
class LinkNode
# Define the accessor and reader of class LinkNode
attr_reader :element, :next, :prev
attr_accessor :element, :next, :prev
def initialize(element)
self.element = element
self.next = nil
self.prev = nil
end
end
class DoublyLL
# Define the accessor and reader of class DoublyLL
attr_reader :front, :rear
attr_accessor :front, :rear
def initialize()
self.front = nil
self.rear = nil
end
# Add node at end of Doubly linked list
def addNode(element)
# Make a new node
node = LinkNode.new(element)
if (self.front == nil)
# When inserting a first node of doubly linked list
self.front = node
self.rear = node
else
# Add node at end position
self.rear.next = node
node.prev = self.rear
self.rear = node
end
end
# Display element
def printData()
node = self.front
print("\n Linked List of from front to rear \n")
# Display node of from front to rear
while (node != nil)
print(" ", node.element ," →")
node = node.next
end
print(" NULL ")
print("\n Linked List of from rear to front \n")
node = self.rear
# Display node of from rear to front
while (node != nil)
print(" ", node.element ," →")
node = node.prev
end
print(" NULL \n")
end
end
class Sorting
# This are returning middle node of given linked list
def middleNode(head, tail)
if (head.next == nil || head == tail)
return head
else
# Auxiliary variables
low = head
high = head
while (high != nil && high.next != nil && high.next.next != nil && high.next != tail && head.next.next != tail)
# visit to next node
low = low.next
# visit to second next node
high = high.next.next
end
# This is middle element
return low
end
end
# Merge two sorted list and return its result
def mergeList(list1, list2)
if (list1 == nil)
# When list1 is empty
return list2
elsif(list2 == nil)
return list1
else
# Some auxiliary variables
result = nil
tail = nil
node = nil
# Combine list elements in sorted order
# This process takes(m+n) time
# Here m is size of list1
# And n is size of list2
while (list1 != nil || list2 != nil)
if (list1 != nil && list2 != nil)
# When both list contain nodes
if (list1.element < list2.element)
# When first list element are smallest
node = list1
list1 = list1.next
else
# When second list element are smallest
node = list2
list2 = list2.next
end
elsif(list1 != nil)
# When first list contain element
# Get sublist
node = list1
# Set that list1 empty
list1 = nil
else
# When second list contain element
# get sublist
node = list2
list2 = nil
end
if (result == nil)
# When get first node of resultant list
result = node
node.next = nil
node.prev = nil
else
# Add node at end of resultant list
tail.next = node
node.prev = tail
end
tail = node
end
return result
end
end
# Perform merge sort
def mergeSort(head, tail)
if (head == nil || head == tail || head.next == nil)
# When have zero or one node
return head
end
# Find the relative middle node
middle = self.middleNode(head, tail)
# Get the right sublist
right = self.mergeSort(middle.next, tail)
# Separating sublist
if (middle.next != nil)
middle.next.prev = nil
end
middle.next = nil
# Get the left sublist
left = self.mergeSort(head, middle)
# Sorted merge in two list
return self.mergeList(left, right)
end
# Handles the request to perform merge sort operation
def sortList(dll)
dll.front = self.mergeSort(dll.front, dll.rear)
node = dll.front
# First last node
while (node.next != nil)
node = node.next
end
# Set new rear node
dll.rear = node
end
end
def main()
dll = DoublyLL.new()
task = Sorting.new()
dll.addNode(5)
dll.addNode(3)
dll.addNode(7)
dll.addNode(1)
dll.addNode(9)
dll.addNode(6)
dll.addNode(2)
dll.addNode(8)
dll.addNode(-2)
dll.addNode(0)
print("\n Before Sort \n")
# 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
dll.printData()
task.sortList(dll)
print("\n After Sort \n")
# -2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
dll.printData()
end
main()Output
Before Sort
Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL
After Sort
Linked List of from front to rear
-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
Linked List of from rear to front
9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL
/*
Scala Program
Merge sort for doubly linked list
*/
class LinkNode(var element: Int , var next: LinkNode , var prev: LinkNode)
{
def this(element: Int)
{
this(element, null, null);
}
}
class DoublyLL(var front: LinkNode , var rear: LinkNode)
{
def this()
{
this(null, null);
}
// Add node at end of Doubly linked list
def addNode(element: Int): Unit = {
// Make a new node
var node: LinkNode = new LinkNode(element);
if (this.front == null)
{
// When inserting a first node of doubly linked list
this.front = node;
this.rear = node;
}
else
{
// Add node at end position
this.rear.next = node;
node.prev = this.rear;
this.rear = node;
}
}
// Display element
def printData(): Unit = {
var node: LinkNode = this.front;
print("\n Linked List of from front to rear \n");
// Display node of from front to rear
while (node != null)
{
print(" " + node.element + " →");
node = node.next;
}
print(" NULL ");
print("\n Linked List of from rear to front \n");
node = this.rear;
// Display node of from rear to front
while (node != null)
{
print(" " + node.element + " →");
node = node.prev;
}
print(" NULL \n");
}
}
class Sorting
{
//This are returning middle node of given linked list
def middleNode(head: LinkNode, tail: LinkNode): LinkNode = {
if (head.next == null || head == tail)
{
return head;
}
else
{
//This is middle element
//Auxiliary variables
var low: LinkNode = head;
var high: LinkNode = head;
while (high != null && high.next != null && high.next.next != null && high.next != tail && head.next.next != tail)
{
//visit to next node
low = low.next;
//visit to second next node
high = high.next.next;
}
return low;
}
}
// Merge two sorted list and return its result
def mergeList(l1: LinkNode, l2: LinkNode): LinkNode = {
var list1: LinkNode = l1;
var list2: LinkNode = l2;
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
// Some auxiliary variables
var result: LinkNode = null;
var tail: LinkNode = null;
var node: LinkNode = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
//When both list contain nodes
if (list1.element < list2.element)
{
//When first list element are smallest
node = list1;
list1 = list1.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = null;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = null;
}
if (result == null)
{
//When get first node of resultant list
result = node;
node.next = null;
node.prev = null;
}
else
{
//Add node at end of resultant list
tail.next = node;
node.prev = tail;
}
tail = node;
}
return result;
}
}
// Perform merge sort
def mergeSort(head: LinkNode, tail: LinkNode): LinkNode = {
if (head == null || head == tail || head.next == null)
{
// When have zero or one node
return head;
}
// Find the relative middle node
var middle: LinkNode = this.middleNode(head, tail);
// Get the right sublist
var right: LinkNode = this.mergeSort(middle.next, tail);
// Separating sublist
if (middle.next != null)
{
middle.next.prev = null;
}
middle.next = null;
//Get the left sublist
var left: LinkNode = this.mergeSort(head, middle);
// Sorted merge in two list
return this.mergeList(left, right);
}
// Handles the request to perform merge sort operation
def sortList(dll: DoublyLL): Unit = {
dll.front = this.mergeSort(dll.front, dll.rear);
var node: LinkNode = dll.front;
// First last node
while (node.next != null)
{
node = node.next;
}
// Set new rear node
dll.rear = node;
}
}
object Main
{
def main(args: Array[String]): Unit = {
var dll: DoublyLL = new DoublyLL();
var task: Sorting = new Sorting();
dll.addNode(5);
dll.addNode(3);
dll.addNode(7);
dll.addNode(1);
dll.addNode(9);
dll.addNode(6);
dll.addNode(2);
dll.addNode(8);
dll.addNode(-2);
dll.addNode(0);
print("\n Before Sort \n");
// 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
dll.printData();
task.sortList(dll);
print("\n After Sort \n");
//-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
dll.printData();
}
}Output
Before Sort
Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL
After Sort
Linked List of from front to rear
-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
Linked List of from rear to front
9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL/*
Swift 4 Program
Merge sort for doubly linked list
*/
class LinkNode
{
var element: Int;
var next: LinkNode? ;
var prev: LinkNode? ;
init(_ element: Int)
{
self.element = element;
self.next = nil;
self.prev = nil;
}
}
class DoublyLL
{
var front: LinkNode? ;
var rear: LinkNode? ;
init()
{
self.front = nil;
self.rear = nil;
}
// Add node at end of Doubly linked list
func addNode(_ element: Int)
{
// Make a new node
let node: LinkNode? = LinkNode(element);
if (self.front == nil)
{
// When inserting a first node of doubly linked list
self.front = node;
self.rear = node;
}
else
{
// Add node at end position
self.rear!.next = node;
node!.prev = self.rear;
self.rear = node;
}
}
// Display element
func printData()
{
var node: LinkNode? = self.front;
print("\n Linked List of from front to rear ");
// Display node of from front to rear
while (node != nil)
{
print("", node!.element ,"→", terminator: "");
node = node!.next;
}
print(" NULL ", terminator: "");
print("\n Linked List of from rear to front ");
node = self.rear;
// Display node of from rear to front
while (node != nil)
{
print("", node!.element ,"→", terminator: "");
node = node!.prev;
}
print(" NULL ");
}
}
class Sorting
{
//This are returning middle node of given linked list
func middleNode(_ head: LinkNode? , _ tail : LinkNode? )->LinkNode?
{
if (head!.next == nil || !(head === tail))
{
return head;
}
else
{
//This is middle element
//Auxiliary variables
var low: LinkNode? = head;
var high: LinkNode? = head;
while (high != nil && high!.next != nil
&& high!.next!.next != nil
&& !(high!.next === tail) && !(head!.next!.next === tail))
{
//visit to next node
low = low!.next;
//visit to second next node
high = high!.next!.next;
}
return low;
}
}
// Merge two sorted list and return its result
func mergeList(_ l1: LinkNode? , _ l2 : LinkNode? )->LinkNode?
{
var list1: LinkNode? = l1;
var list2: LinkNode? = l2;
if (list1 == nil)
{
//When list1 is empty
return list2;
}
else if (list2 == nil)
{
return list1;
}
else
{
// Some auxiliary variables
var result: LinkNode? = nil;
var tail: LinkNode? = nil;
var node: LinkNode? = nil;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != nil || list2 != nil)
{
if (list1 != nil && list2 != nil)
{
//When both list contain nodes
if (list1!.element < list2!.element)
{
//When first list element are smallest
node = list1;
list1 = list1!.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2!.next;
}
}
else if (list1 != nil)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = nil;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = nil;
}
if (result == nil)
{
//When get first node of resultant list
result = node;
node!.next = nil;
node!.prev = nil;
}
else
{
//Add node at end of resultant list
tail!.next = node;
node!.prev = tail;
}
tail = node;
}
return result;
}
}
// Perform merge sort
func mergeSort(_ head: LinkNode? , _ tail : LinkNode? )->LinkNode?
{
if (head == nil || !(head === tail) || head!.next == nil)
{
// When have zero or one node
return head;
}
// Find the relative middle node
let middle: LinkNode? = self.middleNode(head, tail);
// Get the right sublist
let right: LinkNode? = self.mergeSort(middle!.next, tail);
// Separating sublist
if (middle!.next != nil)
{
middle!.next!.prev = nil;
}
middle!.next = nil;
//Get the left sublist
let left: LinkNode? = self.mergeSort(head, middle);
// Sorted merge in two list
return self.mergeList(left, right);
}
// Handles the request to perform merge sort operation
func sortList(_ dll: DoublyLL? )
{
dll!.front = self.mergeSort(dll!.front, dll!.rear);
var node: LinkNode? = dll!.front;
// First last node
while (node!.next != nil)
{
node = node!.next;
}
// Set new rear node
dll!.rear = node;
}
}
func main()
{
let dll: DoublyLL = DoublyLL();
let task: Sorting = Sorting();
dll.addNode(5);
dll.addNode(3);
dll.addNode(7);
dll.addNode(1);
dll.addNode(9);
dll.addNode(6);
dll.addNode(2);
dll.addNode(8);
dll.addNode(-2);
dll.addNode(0);
print("\n Before Sort ");
// 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
dll.printData();
task.sortList(dll);
print("\n After Sort ");
//-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
dll.printData();
}
main();Output
Before Sort
Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL
After Sort
Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL/*
Kotlin Program
Merge sort for doubly linked list
*/
class LinkNode
{
var element: Int;
var next: LinkNode ? ;
var prev: LinkNode ? ;
constructor(element: Int)
{
this.element = element;
this.next = null;
this.prev = null;
}
}
class DoublyLL
{
var front: LinkNode ? ;
var rear: LinkNode ? ;
constructor()
{
this.front = null;
this.rear = null;
}
// Add node at end of Doubly linked list
fun addNode(element: Int): Unit
{
// Make a new node
var node: LinkNode ? = LinkNode(element);
if (this.front == null)
{
// When inserting a first node of doubly linked list
this.front = node;
this.rear = node;
}
else
{
// Add node at end position
this.rear?.next = node;
node?.prev = this.rear;
this.rear = node;
}
}
// Display element
fun printData(): Unit
{
var node: LinkNode ? = this.front;
print("\n Linked List of from front to rear \n");
// Display node of from front to rear
while (node != null)
{
print(" " + node.element + " →");
node = node.next;
}
print(" NULL ");
print("\n Linked List of from rear to front \n");
node = this.rear;
// Display node of from rear to front
while (node != null)
{
print(" " + node.element + " →");
node = node.prev;
}
print(" NULL \n");
}
}
class Sorting
{
//This are returning middle node of given linked list
fun middleNode(head: LinkNode ? , tail : LinkNode ? ): LinkNode ?
{
if (head?.next == null || head == tail)
{
return head;
}
else
{
//This is middle element
//Auxiliary variables
var low: LinkNode ? = head;
var high: LinkNode ? = head;
while (high != null
&& high.next != null
&& high.next?.next != null
&& high.next != tail
&& head.next?.next != tail)
{
//visit to next node
low = low?.next;
//visit to second next node
high = high.next?.next;
}
return low;
}
}
// Merge two sorted list and return its result
fun mergeList(l1: LinkNode ? , l2 : LinkNode ? ): LinkNode ?
{
var list1: LinkNode ? = l1;
var list2: LinkNode ? = l2;
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
// Some auxiliary variables
var result: LinkNode ? = null;
var tail: LinkNode ? = null;
var node: LinkNode?;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
//When both list contain nodes
if (list1.element < list2.element)
{
//When first list element are smallest
node = list1;
list1 = list1.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = null;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = null;
}
if (result == null)
{
//When get first node of resultant list
result = node;
node?.next = null;
node?.prev = null;
}
else
{
//Add node at end of resultant list
tail?.next = node;
node?.prev = tail;
}
tail = node;
}
return result;
}
}
// Perform merge sort
fun mergeSort(head: LinkNode ? , tail : LinkNode ? ): LinkNode ?
{
if (head == null || head == tail || head.next == null)
{
// When have zero or one node
return head;
}
// Find the relative middle node
var middle: LinkNode ? = this.middleNode(head, tail);
// Get the right sublist
var right: LinkNode ? = this.mergeSort(middle?.next, tail);
// Separating sublist
if (middle?.next != null)
{
middle.next?.prev = null;
}
middle?.next = null;
//Get the left sublist
var left: LinkNode ? = this.mergeSort(head, middle);
// Sorted merge in two list
return this.mergeList(left, right);
}
// Handles the request to perform merge sort operation
fun sortList(dll: DoublyLL ): Unit
{
dll.front = this.mergeSort(dll.front, dll.rear);
var node: LinkNode ? = dll.front;
// First last node
while (node?.next != null)
{
node = node.next;
}
// Set new rear node
dll.rear = node;
}
}
fun main(args: Array < String > ): Unit
{
var dll: DoublyLL = DoublyLL();
var task: Sorting = Sorting();
dll.addNode(5);
dll.addNode(3);
dll.addNode(7);
dll.addNode(1);
dll.addNode(9);
dll.addNode(6);
dll.addNode(2);
dll.addNode(8);
dll.addNode(-2);
dll.addNode(0);
print("\n Before Sort \n");
// 5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
dll.printData();
task.sortList(dll);
print("\n After Sort \n");
//-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
dll.printData();
}Output
Before Sort
Linked List of from front to rear
5 → 3 → 7 → 1 → 9 → 6 → 2 → 8 → -2 → 0 → NULL
Linked List of from rear to front
0 → -2 → 8 → 2 → 6 → 9 → 1 → 7 → 3 → 5 → NULL
After Sort
Linked List of from front to rear
-2 → 0 → 1 → 2 → 3 → 5 → 6 → 7 → 8 → 9 → NULL
Linked List of from rear to front
9 → 8 → 7 → 6 → 5 → 3 → 2 → 1 → 0 → -2 → NULL
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment