java - 插入已排序的双向链表

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

重要:
newNode 是最小/最大的情况怎么样？你也应该处理这两种边缘情况 - 否则你会得到 NPE!