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

|

1076 Discussions

|

  • mdsanz
     + 0 comments

    My Java 8 Solution

    public static DoublyLinkedListNode sortedInsert(DoublyLinkedListNode llist, int data) {
        DoublyLinkedListNode newNode = new DoublyLinkedListNode(data);
        
        if (llist == null) {
            return newNode;
        }
        
        DoublyLinkedListNode current = llist;
        
        while (current != null ) {
            if (current.data >= data) {
                if (current.prev == null) {
                    newNode.next = current;
                    current.prev = newNode;
                    return newNode;
                }
                
                DoublyLinkedListNode prev = current.prev;
                current.prev = newNode;
                prev.next = newNode;
                newNode.next = current;
                newNode.prev = prev;
                return llist;
            }
            
            if (current.next == null) {
                current.next = newNode;
                newNode.prev = current;
                return llist;
            }
            
            current = current.next;
        }
        return llist;
    }

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