Sorted insert in a doubly linked list with head and tail pointers | Linked List node ; Function to insetail new node ; If first node to be insetailed in doubly linked list ; If node to be insetailed has value less than first node ; If node to be insetailed has value more than last node ; Find the node before which we need to insert p . ; Insert new node before temp ; Function to print nodes in from left to right ; Driver program to test above functions
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . info = data NEW_LINE self . next = None NEW_LINE self . prev = None NEW_LINE DEDENT DEDENT head = None NEW_LINE tail = None NEW_LINE def nodeInsetail ( key ) : NEW_LINE INDENT global head NEW_LINE global tail NEW_LINE p = Node ( 0 ) NEW_LINE p . info = key NEW_LINE p . next = None NEW_LINE if ( ( head ) == None ) : NEW_LINE INDENT ( head ) = p NEW_LINE ( tail ) = p NEW_LINE ( head ) . prev = None NEW_LINE return NEW_LINE DEDENT if ( ( p . info ) < ( ( head ) . info ) ) : NEW_LINE INDENT p . prev = None NEW_LINE ( head ) . prev = p NEW_LINE p . next = ( head ) NEW_LINE ( head ) = p NEW_LINE return NEW_LINE DEDENT if ( ( p . info ) > ( ( tail ) . info ) ) : NEW_LINE INDENT p . prev = ( tail ) NEW_LINE ( tail ) . next = p NEW_LINE ( tail ) = p NEW_LINE return NEW_LINE DEDENT temp = ( head ) . next NEW_LINE while ( ( temp . info ) < ( p . info ) ) : NEW_LINE INDENT temp = temp . next NEW_LINE DEDENT ( temp . prev ) . next = p NEW_LINE p . prev = temp . prev NEW_LINE temp . prev = p NEW_LINE p . next = temp NEW_LINE DEDENT def printList ( temp ) : NEW_LINE INDENT while ( temp != None ) : NEW_LINE INDENT print ( temp . info , end = " ▁ " ) NEW_LINE temp = temp . next NEW_LINE DEDENT DEDENT nodeInsetail ( 30 ) NEW_LINE nodeInsetail ( 50 ) NEW_LINE nodeInsetail ( 90 ) NEW_LINE nodeInsetail ( 10 ) NEW_LINE nodeInsetail ( 40 ) NEW_LINE nodeInsetail ( 110 ) NEW_LINE nodeInsetail ( 60 ) NEW_LINE nodeInsetail ( 95 ) NEW_LINE nodeInsetail ( 23 ) NEW_LINE print ( " Doubly linked list on printing from left to right " ) NEW_LINE printList ( head ) NEW_LINE