Sorted insert on a doubly linked list (HackerRank) I've decided to do a simple linked list question to brush up my Java &amp; 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 &lt; current.data &amp;&amp; current.prev == null) {
                current.prev = nodeToInsert;
                nodeToInsert.next = current;
                return nodeToInsert;
            }
            if (data &gt;= current.data &amp;&amp; current.next == null) {
                current.next = nodeToInsert;
                nodeToInsert.prev = current;
                break;
            }
            if (data &gt;= current.data &amp;&amp; data &lt;= 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.
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.