We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Linked Lists
  4. Inserting a Node Into a Sorted Doubly Linked List
  5. Discussions

Inserting a Node Into a Sorted Doubly Linked List

Sort by

recency

|

1075 Discussions

|

  • GlennaPeggy
     + 0 comments

    This function inserts a new node into a sorted doubly linked list while preserving the sorted order. It traverses the list to find the correct insertion point and carefully updates the prev and next pointers of the adjacent nodes to maintain the integrity of the doubly linked structure. Tigerexch247

  • emhhacker
     + 0 comments

    My Java solution with linear time complexity and constant space complexity:

    public static DoublyLinkedListNode sortedInsert(DoublyLinkedListNode llist, int data) {
        //if llist is null, set it to a new node w/ data
        if(llist == null) return llist = new DoublyLinkedListNode(data);
        
        //init a new node w/ data
        DoublyLinkedListNode newNode = new DoublyLinkedListNode(data);
        DoublyLinkedListNode curr = llist;
        
        //if the first node's data is >= than new node's data
        if(data <= llist.data){
            newNode.next = llist;
            llist.prev = newNode;
            return newNode;
        }
        
        //iterate thru llist
        while(curr != null){
            //if curr data is <= curr and next data is > curr or null, insert new node
            if(curr.data <= data && (curr.next == null || curr.next.data > data)){
                newNode.next = curr.next;
                newNode.prev = curr;
                if(curr.next != null) curr.next.prev = newNode;
                curr.next = newNode;
                break;
            }
            curr = curr.next;
        }
        //return llist
        return llist;
    }

  • JessieMarble3
     + 0 comments

    Ensure proper traversal to find the correct position, updating both forward and backward links. Maintain sorted order by adjusting pointers carefully to prevent breaking the list structure. Ekbet16 Com Login

  • kuro_ece
     + 0 comments

    in C:

    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;
}

  • sgakhar_be21
     + 0 comments

    Python 3 code

    Inserting a Node Into a Sorted Doubly Linked List

    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

    Do Upvote it if you found it helpful & Do Comment below for any suggestions⛳