Insert node in sorted doubly linked list

Question

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?

Answer 1

Look for unused operations

At first glance, I notice the following:

• You set node.prev = previous, but if previous is null, then this statement is pointless. Later there is a previous == null condition. You could move this statement into the else block of that condition.
• You set node.next = current, but if current is null, then this statement is pointless. Later there is a current != null condition. You could delay this assignment until that condition.

By reordering the statements based on the above observations, we arrive at this:

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

Node node = new Node();
node.data = data;

if (previous == null) {
    head = node;
} else {
    // re-link previous node
    previous.next = node;
    node.prev = previous;
}

if (current != null) {
    // re-link next node
    current.prev = node;
    node.next = current;
}

return head;

Notice the nice symmetry in the code segments that re-link the previous and next nodes. This implementation is slightly easier to read.

A note on encapsulation

As @rolfl pointed out, this method would break the encapsulation of a linked list implementation, as it would reveal the Node class, which should be an inner class of the linked list, an implementation detail that should not be exposed to users.

However, such method can be perfectly legitimate as a private method inside the implementation of a linked list. Since the exercise only asked to implement a method, this can be a legitimate sub-task in the implementation of a sorted doubly-linked list.

Java conventions

Methods should be named camelCase, so this should have been sortedInsert.

Alternative approach

This solution required me to do a lot of head scratching which I fear would be difficult to do in front of an interviewer.

As long as you can come out with a solution that works, normally you should be fine. Just beware of corner cases (empty list, singleton list), go through test cases, thinking out loud.

Any other approach with fewer chances of mistakes?

In case it helps you, I took a bit different approach.

No matter what happens, we will have to return a Node with data, so we might as well start with that:

Node node = new Node();
node.data = data;

If the list is empty, we won't have to do any re-linking, so we might as well return immediately:

if (head == null) {
    return node;
}

At this point we know that head is not null. If data is less than head.data, we just need to insert the new node in front, and we're done:

if (data < head.data) {
    node.next = head;
    return node;
}

Ok so we need to insert the node somewhere, after head or later. Let's iterate until we find a node that's not smaller:

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

If we didn't reach the end, then re-link the next node:

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

Re-link the previous node and finally return head:

current.next = node;
node.prev = current;

return head;

This is slightly more verbose than the reworked version of yours, but each step taken was pretty clear, with intuitively safe choices. I'm not sure one solution is better than the other, I think they are both good enough.

Answer 2

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.