CODEWITHSUNDEEP
javainsertlinked-listsorting
Nexion
Nexion

Reputation: 433

Insert into sorted Doubly Linked List

I know this isn't that complicated but for some reason I'm not able to figure it out.

I'm trying to just insert an element into a doubly linked list, and keep everything sorted. I've looked up a few different questions similar to this but none seem to be quite the same.

Simply, if I had a doubly linked list: 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);
    }
}

It's just giving me a NPE on the line curNode.getNext().setPrev(newNode()); but how can that happen if I check for it in my while loop comdition?

Upvotes: 1

Views: 1937

Answers (1)

Nir Alfasi
Nir Alfasi

Reputation: 53525

Two problems:

  1. You break on curNode == newNode (in values):

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

    but in the example that you gave 6 != 5 and 6 != 7 so actually, you should "move forward" as long as the current node has a smaller value than the new node

  2. you're doing two contradicting actions:
    • newNode.setNext(curNode);
    • curNode.setNext(newNode);

Consider the example that you gave, you should run with the new node, 6, until you reach 7. Once you got to the first node that is bigger you should do the following 4 actions:

- 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

keep in mind that "current" should point to 7 (newNode is 6) according to this algorithm, so you should do:

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

IMPORTANT:
What about the cases where the newNode is the smallest/biggest ? you should handle those two edge-cases as well - otherwise you'll get NPE!

Upvotes: 2

Related Questions