Insert node in sorted doubly linked list

Description:


Given a reference to the head of a doubly-linked list and an integer,
create a new Node object having data value and insert it into a
sorted linked list.

Code:

Node SortedInsert(Node head, int data) {

    Node current  = head;
    Node previous = null;
    while (current != null && current.data < data) {
        previous = current;
        current  = current.next;
    }

    Node node = new Node();
    node.data = data;
    node.next = current;
    node.prev = previous;

    if (previous == null) {
        head = node;
    } else {
        previous.next = node;
    }

    if (current != null) {
        current.prev = node;
    }

    return head;
}

This solution required me to do a lot of head scratching which I fear would be difficult to do in front of an interviewer. Any other approach with fewer chances of mistakes?

Well, the problem statement is broken. Maybe this is a trick question? In the situation that the value to be inserted is at the beginning of the list (perhaps the list is empty, or the value is small), then you can't successfully control the changes needed to modify the head reference for everyone who has it.

The code you have implies that the possibly new head is always returned after each call, but you run a risk of creating multi-headed lists with multiple heads, if the code outside your function does not do the correct assignments with the head.

That sort of risk is not acceptable in a Java library/function, and thus your encapsulation is wrong, etc.

In front of an interviewer, I would recommend that you say something like: "Well, this function would not be useful in a Java context, the data should be encapsulated and the head node should not be exposed to the user. The function should have no return value, and should not take in the head node as a parameter, but instead the function should be a method on a class that encapsulates a sorted list"

Having said that, though, and looking at your code, your code does as good a job as can be done in the circumstances, and it has good style, naming, and formatting.

If I was really picky, I would suggest that you reverse the if/else condition:

if (previous == null) {
    head = node;
} else {
    previous.next = node;
}

to be:

if (previous != null) {
    previous.next = node;
} else {
    head = node;
}

because that makes it match the logic of the next condition:

if (current != null) {
    current.prev = node;
}

Otherwise, it's all good.

StackExchange Code Review Q#150680, answer score: 3