Problem when alphabetically inserting a node into a doubly linked list

Question

Im trying to write an insertion method for a doubly linked list where as i'm placing the node into the list it is being inserted in alphabetical order. This idea is I will traverse through the list with a curnode and if the newNode comes before the curnode, I will simply place the newNode before the curnode. The code I have written so far works for inserting 1 node into the list, but i'm having problems with the second part that requires checking the order and placing before. How should I change the program to make it work properly? With the code I have now only 1 element (head) will be inserted.

void insert(String x){
        node curnode = head;
        node newNode = new node(x);

        //list is empty so insert as normal - [works fine]
        if (head == null){
            head = newNode;
            head.prev = null;
            head.next = null;
            tail = newNode;
        }
        //Now insert node with respect to alphabetical order - [problem area]
        else {
           
            // while the list isn't empty 
            while (curnode != null){

                // if newNode alphabetically comes before the curnode then place before
                if (curnode.data.compareTo(newNode.data) > 0){
                    node temp = curnode.prev;
                    curnode.prev = newNode;
                    newNode.next = curnode;
                    newNode.prev = temp;
                    break;
                }
            }
           
        }
    }

FYI: Java naming convention states that class names should start with uppercase letter, so node should be Node. — Andreas
– Andreas, Commented Oct 5, 2020 at 23:16

aks7891 · Accepted Answer · 2020-10-05 23:06:37Z

1

There are a few things missing with your implementation. Compare it with this working solution:

void insert(String x){
    node curnode = head;
    node lastnode = null;
    node newNode = new node(x);
    
    //list is empty so insert as normal - [works fine]
    if (head == null){
        head = newNode;
        head.prev = null;
        head.next = null;
        tail = newNode;
    }
    //Now insert node with respect to alphabetical order - [problem area]
    else {
        // while the list isn't empty 
        while (curnode != null){
            // if newNode alphabetically comes before the curnode then place before
            if (curnode.data.compareTo(newNode.data) > 0){
                
                node temp = curnode.prev;
                curnode.prev = newNode;
                newNode.next = curnode;
                newNode.prev = temp;
                if(temp != null) {
                    temp.next = newNode;
                } else {
                    // If newnode gets inserted in the head
                    head = newNode;
                }
                break;
            }
            
            lastnode = curnode;
            curnode = curnode.next;
        }
        if (curnode == null) {
            // insert to the last
            lastnode.next = newNode;
            newNode.prev = lastnode;
            tail = newNode;
        }
       
    }
}

answered Oct 5, 2020 at 23:06

aks7891

222 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

aks7891 Over a year ago

If this answer solved all your questions/doubts then feel free to mark it as solved.

Collectives™ on Stack Overflow

Problem when alphabetically inserting a node into a doubly linked list

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related