1

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

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

简单地说，如果我有一个双向链表： 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循环条件中检查它怎么会发生呢？

4

1 回答 1

2

两个问题：

  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

请记住，根据此算法，“当前”应指向7(newNode is )，因此您应该这样做：6

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

重要提示：
newNode 最小/最大的情况如何？你也应该处理这两种极端情况——否则你会得到 NPE！

于 2013-10-20T21:57:48.373 回答