DoublyLinkedListNode* sortedInsert(DoublyLinkedListNode* llist, int data) {
    DoublyLinkedListNode** cur = &llist;
    DoublyLinkedListNode * new_node = calloc(sizeof(DoublyLinkedListNode), 1);
    new_node->data = data;
    
    while(*cur && ((*cur)->data < data)) {
        cur = &(*cur)->next;
    }
    
    new_node->next = (*cur);
    if(*cur) {
        new_node->prev = (*cur)->prev;
    }
    (*cur) = new_node;
    return llist;
}

def sortedInsert(llist, data):
    # q - new node 
    q = DoublyLinkedListNode(data)
    # p - pointer to linked list
    p = llist
    
    # llist is empty
    if(not p):
        return q
        
    # insert at the beginning    
    if(p and data < p.data):
        q.next = p
        p.prev = q
        p = q
        return p
    # while traversing pointer p   
    while(p):
        
        p = p.next
        
        # In-Between 2 nodes
        if(p.data > q.data):
            
            p = p.prev            
            q.next = p.next
            q.prev = p
            if(p.next):
                p.next.prev = q
            p.next = q
            return llist
            
        else:
            # inserting at the end of the linked list
            if(not p.next):
                
                p.next = q
                q.next = None
                q.prev = p
                return llist
                
            else:
                continue
   

def sortedInsert(llist, data):
    dummy=DoublyLinkedListNode(float('-inf'))
    dummy.next=llist
    llist.prev=dummy
    y=dummy
    while (dummy):
        previous=dummy
        if(dummy.next and dummy.next.data>=data and dummy.data<=data):
            x=DoublyLinkedListNode(data)
            dummy.next,x.next=x,dummy.next
            x.prev=dummy
            x=x.next.prev
            return y.next
        dummy=dummy.next
            
            
      
    x=DoublyLinkedListNode(data)
    x.prev=previous
    previous.next=x
        
            
    return y.next