Insert into sorted Doubly Linked List

Question

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?

Can we see a full stack trace? Also, the line numbers given by an exception report aren't always right, so that might not be the correct line. — tbodt
– tbodt, Commented Oct 20, 2013 at 21:48
Exception in thread "main" java.lang.NullPointerException at DELinkedList.insertMid(DELinkedList.java:43) at DataStructure.insert(DataStructure.java:72) at COSC311Driver.main(COSC311Driver.java:48) — Nexion
– Nexion, Commented Oct 20, 2013 at 21:49
The loop terminates as soon as curNode.getNext() is null... — Oliver Charlesworth
– Oliver Charlesworth, Commented Oct 20, 2013 at 21:49

Nir Alfasi · Accepted Answer · 2013-10-20 22:12:20Z

2

Two problems:

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
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!

edited Oct 20, 2013 at 22:12

answered Oct 20, 2013 at 21:57

Nir Alfasi

53.6k11 gold badges94 silver badges138 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Nexion Over a year ago

Yeah I noticed those problems and corrected them before you had posted this, but I'm still getting a NPE on the curNode.getPrev().setNext(newNode); line, even when I added checks for the edge-cases

Nir Alfasi Over a year ago

@Nexion if you checked all the edge cases you shouldn't get NPE... there are only 2 options: curNode is null or curNode.getPrev() is null. Run with a debugger and find out which is the case.

Nexion Over a year ago

Updated the OP with my revised code that's still giving me a NPE on the same line... for some reason curNode never changes from being anything but front. I have no idea why...

Nir Alfasi Over a year ago

@Nexion you probably have more than one bug here. Example: when front.getNext() == null you set newNode.setPrev(front); without checking which one of them is bigger.

Collectives™ on Stack Overflow

Insert into sorted Doubly Linked List

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related