Inserting a Node Into a Sorted Doubly Linked List

                            Solution in C :

In C++ :


/*
    Insert Node in a doubly sorted linked list 
    After each insertion, the list should be sorted
   Node is defined as
   struct Node
   {
     int data;
     Node *next;
     Node *prev
   }
*/
Node* SortedInsert(Node *head,int data)
{
    // Complete this function
   // Do not write the main method. 
    Node *current = NULL;
    Node *new_node = (Node*)malloc(sizeof(Node));
    new_node->data=data;
    new_node->next=NULL;
    new_node->prev=NULL;
    
  if (head == NULL )
  {
    head = new_node; 
  }
  else if(head->data >= new_node->data)
  {
    new_node->next = head;
    head->prev=new_node;
    head = new_node; 
  }
  else
  {
    
    current = head;
    while (current->next!=NULL && current->next->data < new_node->data)
    {
      current = current->next;
    }
      
      if(current->next!=NULL)
      {
          new_node->next = current->next;
          current->next->prev=new_node;
      }     
      current->next = new_node;
      new_node->prev=current;
      
  }       
    return head;
}



In Java :


/*
  Insert Node at the end of a linked list 
  head pointer input could be NULL as well for empty list
  Node is defined as 
  class Node {
     int data;
     Node next;
     Node prev;
  }
*/

Node SortedInsert(Node head,int data) {
  
    Node n= new Node();
    n.data=data;
    n.next=null;
    n.prev=null;
    
    if(head==null)
        return n;
    if(head.data > data)
        {
        
        n.next=head;
        head.prev=n;
        return n;
    }
    
    Node temp=head;
    
    while(temp.next!=null)
        {
           
         if(temp.next.data > data)
             {
             
               n.next=temp.next;
               n.prev=temp.next.prev;
               temp.next=n;
               n.next.prev=n;
               return head;
         }
        temp=temp.next;
        
    }
    
    temp.next=n;
    n.prev=temp;
    return head;
    
}




In python3 :



"""
 Insert a node into a sorted doubly linked list
 head could be None as well for empty list
 Node is defined as
 
 class Node(object):
 
   def __init__(self, data=None, next_node=None, prev_node = None):
       self.data = data
       self.next = next_node
       self.prev = prev_node

 return the head node of the updated list 
"""
def SortedInsert(head, data):
    new = Node(data=data)
    tmp = head
    while tmp.data <= data and tmp.next != None and tmp.next.data <= data:
        tmp = tmp.next
    new.prev = tmp
    new.next = tmp.next
    tmp.next = new
    if new.next != None:
        new.next.prev = new
    return head
  





In C :



// Complete the sortedInsert function below.

/*
 * For your reference:
 *
 * DoublyLinkedListNode {
 *     int data;
 *     DoublyLinkedListNode* next;
 *     DoublyLinkedListNode* prev;
 * };
 *
 */
DoublyLinkedListNode* sortedInsert(DoublyLinkedListNode* head, int data) {
    
    DoublyLinkedListNode *New = create_doubly_linked_list_node(data);
    if (!head)
    {
        head = New;
        return head;
    }
    else if (data < (head->data))
    {
        New->next = head; 
        head->prev = New;
        New->prev = NULL;
        head = New;
        return head; 
    }
    else 
    {
        DoublyLinkedListNode *temp = head;
        while ( ((temp->next) != NULL) && ((temp->next->data) <= data))
            temp = temp->next;
        
        if (temp->next != NULL)
        {
            DoublyLinkedListNode *next = temp->next;
            next->prev = New;
            New->next = next;
        }
        else 
            New->next = NULL;
            
        temp->next = New;
        New->prev = temp;
    }
    return head; 
}