Inserting a Node Into a Sorted Doubly Linked List

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