我知道这并不复杂,但是由于某种原因我无法弄清楚。
我试图将元素插入到双向链表中,并使所有内容保持排序。
我查了几个与此类似的不同问题,但似乎没有一个完全一样。
简单来说,如果我有一个双向链表:
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!