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

2 つの問題:

  1. curNode == newNodeあなたは（値で）壊れます：

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

    しかし、あなたが 6 != 5 と 6 != 7 を与えた例では、実際には、現在のノードが新しいノードよりも小さい値を持っている限り、「前進」する必要があります

  2. あなたは2つの相反する行動をしています:
    • newNode.setNext(curNode);
    • curNode.setNext(newNode);

与えられた例を考えてみましょう。7 に到達するまで、新しいノード 6 で実行する必要があります。より大きな最初のノードに到達したら、次の 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 が最小/最大の場合はどうなりますか? これら 2 つのエッジ ケースも処理する必要があります。そうしないと、NPE が発生します。

于 2013-10-20T21:57:48.373 に答える