在双链表中按字母顺序插入节点时出现的问题

Question

我试图为双链表编写一个插入方法，当我将节点放入列表时，它是按字母顺序插入的。这个想法是，我将使用curnode遍历列表，如果newNode位于curnode之前，我将简单地将newNode放在curnode之前。到目前为止，我编写的代码用于将1个节点插入列表，但我在第二部分遇到了问题，这需要检查顺序和放置之前。我应该如何更改程序以使其正常工作？使用代码，我现在只插入1个元素（head）。

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

Answer 1

您的实现中缺少一些东西。将其与此工作解决方案进行比较：

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