Sorted insert on a doubly linked list (HackerRank)

Question

I've decided to do a simple linked list question to brush up my Java & CS.

---

This is the solution for

Given a reference to the head of a doubly-linked list and an integer, \$data\$ , create a new DoublyLinkedListNode object having data value \$data\$ and insert it into a sorted linked list while maintaining the sort. Full question

 /*
 * For your reference:
 *
 * DoublyLinkedListNode {
 * int data;
 * DoublyLinkedListNode next;
 * DoublyLinkedListNode prev;
 * }
 *
 */
 static DoublyLinkedListNode sortedInsert(DoublyLinkedListNode head, int data) {
 DoublyLinkedListNode nodeToInsert = new DoublyLinkedListNode(data);
 if (head == null) return nodeToInsert;
 DoublyLinkedListNode current = head;
 while (current != null) {
 if (data < current.data && current.prev == null) {
 current.prev = nodeToInsert;
 nodeToInsert.next = current;
 return nodeToInsert;
 }
 if (data >= current.data && current.next == null) {
 current.next = nodeToInsert;
 nodeToInsert.prev = current;
 break;
 }
 if (data >= current.data && data <= current.next.data) {
 DoublyLinkedListNode temp = current.next;
 current.next = nodeToInsert;
 nodeToInsert.prev = current;
 temp.prev = nodeToInsert;
 nodeToInsert.next = temp;
 break;
 }
 current = current.next;
 }
 return head;
 }

This passes all test cases.

• markspace: Since you're brushing up, if this were real production code, I'd ding you pretty hard on your lack of Javadoc comments. Get a copy of Effective Java by Joshua Bloch and read his advice on proper in-code documentation.
• JaDogg: @markspace yes comment in my code above is kind of weired. :( It came with the question itself.

Answer 1

To me, the main problem with your solution is readability. It took me some time to understand what exactly you're doing to solve a Hackerrank task.

Simplify Code

For instance, consider the following block of yours:

...
if (data < current.data && current.prev == null) {
 current.prev = nodeToInsert;
 nodeToInsert.next = current;
 return nodeToInsert;
}
...

Doing it in a while loop is a bit confusing as you can directly compare data with head.data - as per problem statement the list is sorted and so the smallest element is in the current head. Move it out of the loop. Additionally, remove current.prev == null as the head is the first element by definition.

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

Another block that can be simplified is:

if (data >= current.data && current.next == null) {
 current.next = nodeToInsert;
 nodeToInsert.prev = current;
 break;
}

Here, you check if current is a tail (last element) and then add your nodeToInsert to it. But then data >= current.data is redundant since current.next == null is sufficient to say whether an element is a tail or not. Hence:

if (current.next == null) {
 current.next = nodeToInsert;
 nodeToInsert.prev = current;
 break;
}

Or even here:

if (data >= current.data && data <= current.next.data) {
 DoublyLinkedListNode temp = current.next;
 current.next = nodeToInsert;
 nodeToInsert.prev = current;
 temp.prev = nodeToInsert;
 nodeToInsert.next = temp;
 break;
}

You can remove data >= current.data as it's given (initially current = head and so the check was made before the loop started):

if (data <= current.next.data) {
 DoublyLinkedListNode temp = current.next;
 current.next = nodeToInsert;
 nodeToInsert.prev = current;
 temp.prev = nodeToInsert;
 nodeToInsert.next = temp;
 break;
}

Add useful comments

You could've commented crucial blocks of your code better to make it easier to understand what you're doing. For instance:

// if current is the last element then add the new element after it
if (current.next == null) {
 current.next = nodeToInsert;
 nodeToInsert.prev = current;
 break;
}

Or

// if the new element is not greater than the next one 
// then insert it between the current element and the next one
if (data <= current.next.data) {
 DoublyLinkedListNode temp = current.next;
 current.next = nodeToInsert;
 nodeToInsert.prev = current;
 temp.prev = nodeToInsert;
 nodeToInsert.next = temp;
 break;
}

Static method

Well, I know, Hackerrank forces you to use the static sortedInsert() method so there's nothing you can do about it.

Answer 2

One thing I take issue with is that all of this code is in a static. If you're already drinking the Java kool-aid, you can have a brief static wrapper to do your if (head == null) shortcut, but the rest of the code should be one or more methods on DoublyLinkedListNode. Rather than continuing to reference your parameter data, the instance saved to nodeToInsert would, in the method you write, access its this.data.

Overall the question asks you to do a thing that sucks, so it isn't your fault: sorted insertion to a linked list is O(n), but you can do much better with a different choice of data structure, such as an AVL tree. If you're interested, here's an implementation of a sorted list in Java.

• JaDogg: Yes it's just a silly question. I'm already aware of AVL & RB trees. static was unfortunately there in the question.