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

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

简单来说,如果我有一个双向链表:
3 4 5 7 8

insertMid(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循环条件下检查它怎么办?

最佳答案

两个问题:


您在curNode == newNode上中断(值):

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

但是在示例中,您实际上给了6!= 5和6!= 7,因此,只要当前节点的值小于新节点的值,就应该“向前移动”
您正在执行两个矛盾的操作:

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


请记住,根据此算法,“当前”应该指向7(newNode是6),因此您应该执行以下操作:

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


重要:
如果newNode最小/最大,该怎么办?您还应该处理这两个边缘情况-否则,您将获得NPE!

10-06 05:37
查看更多