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.
SortedInsert
- where we do not see if the fields are public or final or needs synchorinzation, having getters or setters - is not enougth for a review and readers will folow theese suggestions without a design-review and will break better solutions. \$\endgroup\$