insertion sort doubly linked list java
// Java implementation for insertion Sort
// on a doubly linked list
class Solution
{
// Node of a doubly linked list
static class Node
{
int data;
Node prev, next;
};
// function to create and return a new node
// of a doubly linked list
static Node getNode(int data)
{
// allocate node
Node newNode = new Node();
// put in the data
newNode.data = data;
newNode.prev = newNode.next = null;
return newNode;
}
// function to insert a new node in sorted way in
// a sorted doubly linked list
static Node sortedInsert(Node head_ref, Node newNode)
{
Node current;
// if list is empty
if (head_ref == null)
head_ref = newNode;
// if the node is to be inserted at the beginning
// of the doubly linked list
else if ((head_ref).data >= newNode.data)
{
newNode.next = head_ref;
newNode.next.prev = newNode;
head_ref = newNode;
}
else
{
current = head_ref;
// locate the node after which the new node
// is to be inserted
while (current.next != null &&
current.next.data < newNode.data)
current = current.next;
//Make the appropriate links /
newNode.next = current.next;
// if the new node is not inserted
// at the end of the list
if (current.next != null)
newNode.next.prev = newNode;
current.next = newNode;
newNode.prev = current;
}
return head_ref;
}
// function to sort a doubly linked list using insertion sort
static Node insertionSort(Node head_ref)
{
// Initialize 'sorted' - a sorted doubly linked list
Node sorted = null;
// Traverse the given doubly linked list and
// insert every node to 'sorted'
Node current = head_ref;
while (current != null)
{
// Store next for next iteration
Node next = current.next;
// removing all the links so as to create 'current'
// as a new node for insertion
current.prev = current.next = null;
// insert current in 'sorted' doubly linked list
sorted=sortedInsert(sorted, current);
// Update current
current = next;
}
// Update head_ref to point to sorted doubly linked list
head_ref = sorted;
return head_ref;
}
// function to print the doubly linked list
static void printList(Node head)
{
while (head != null)
{
System.out.print(head.data + " ");
head = head.next;
}
}
// function to insert a node at the beginning of
// the doubly linked list
static Node push(Node head_ref, int new_data)
{
// allocate node /
Node new_node = new Node();
// put in the data /
new_node.data = new_data;
// Make next of new node as head and previous as null /
new_node.next = (head_ref);
new_node.prev = null;
// change prev of head node to new node /
if ((head_ref) != null)
(head_ref).prev = new_node;
// move the head to point to the new node /
(head_ref) = new_node;
return head_ref;
}
// Driver code
public static void main(String args[])
{
// start with the empty doubly linked list /
Node head = null;
// insert the following data
head=push(head, 9);
head=push(head, 3);
head=push(head, 5);
head=push(head, 10);
head=push(head, 12);
head=push(head, 8);
System.out.println( "Doubly Linked List Before Sorting\n");
printList(head);
head=insertionSort(head);
System.out.println("\nDoubly Linked List After Sorting\n");
printList(head);
}
}
// This code is contributed by Arnab Kundu