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