插入到排序的双向链表中

Question

我知道这并不复杂，但由于某种原因我无法弄清楚。

我试图将一个元素插入到双向链表中，并保持所有内容排序。我查找了几个与此类似的不同问题，但似乎没有一个是完全相同的。

简单地说，如果我有一个双向链表：3 <-> 4 <-> 5 <-> 7 <-> 8

插入中（6）：3 <-> 4 <-> 5 <-> 6 <-> 7 <-> 8

public void insert(IndexRecord newRec){
    Node newNode = new Node(newRec);
    Node curNode = front;
    if (isEmpty()){                             //Empty list
        front = newNode;
    }else if (front.getNext() == null){         //One element in list
        newNode.setPrev(front);
        front.setNext(newNode);
        back = newNode;
        back.setPrev(front);    
    }else if (back.compareTo(newNode) < 0){     //New node is greater than back
        back.setNext(newNode);
        newNode.setPrev(back);
        back.getPrev().setNext(newNode);
        back = newNode;
    }else{                                      //New node is in between two others
        while (curNode != null){
            if (newNode.compareTo(curNode) < 0){
                curNode = curNode.getNext();
            }else{
                break;
            }
        }
        newNode.setNext(curNode);
        newNode.setPrev(curNode.getPrev());
        curNode.getPrev().setNext(newNode);
        curNode.setPrev(newNode);
    }
}

它只是在curNode.getNext（）.setPrev（newNode（））行上给了我一个NPE;但是如果我在我的while循环编码中检查它，这怎么会发生呢？

Answer 1

两个问题：

1. 您在curNode == newNode上中断（在值中）：

   curNode.getData().getKey().compareTo(newRec.getKey()) == 0

   但是在您给出 6 ！= 5 和 6 ！= 7 的示例中，实际上，只要当前节点的值小于新节点，您就应该"前进"

2. 您正在执行两个相互矛盾的操作：
   • newNode.setNext(curNode);
   • curNode.setNext(newNode);

考虑你给出的示例，你应该使用新节点 6 运行，直到达到 7。到达第一个较大的节点后，您应该执行以下操作 4 个操作：

- update 6's next to point to 7
- update 6's prev to point to 5
- update 5's next to point to 6
- update 7's prev to point to 6

请记住，根据此算法，"current"应该指向7（newNode 是6），所以你应该这样做：

newNode.setNext(curNode);
newNode.setPrev(curNode.getPrev());
curNode.getPrev().setnext(newNode);
curNode.setPrev(newNode);

重要：
新节点最小/最大的情况呢？您也应该处理这两个边缘情况 - 否则您将获得 NPE！