Double Linked List with String Java
<p>I wrote the following program:</p>

<pre><code>public class DLinkedList&lt;T extends Comparable&lt;T&gt;&gt; {

    private class DNode&lt;T&gt; {
        private DNode&lt;T&gt; prev, next;
        private T nodeValue;
        public DNode() {
            nodeValue = null;
            next = prev = this;
            }

        public DNode(T val) {
            nodeValue = val;
            next = prev = this;
            }
        }

    private DNode&lt;T&gt; header;

    private int size;

    public DLinkedList() {
        header = new DNode&lt;T&gt;();
        size = 0;
    }

    public Boolean empty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void addOrder(T val) {
        DNode&lt;T&gt; newNode = new DNode&lt;T&gt;(val);
        DNode&lt;T&gt; curr = header.next;
        int count = 0;

        while (curr != header &amp;&amp;
            curr.nodeValue.compareTo(newNode.nodeValue) &lt; 0 ) {

            curr = curr.next;
            newNode.prev = curr;
            newNode.next = curr.next;
            newNode.next.prev = curr;
            count++;
        }

        if (count == 1) {
            newNode.prev = curr;
            newNode.next = curr.prev;
            curr.prev.next.next = newNode;

        } else {
            newNode.prev = curr.prev;
            newNode.next = curr;
            curr.prev.next = newNode;
            count++;
        }
    }

    public String toString() {
        String str = "";
        DNode&lt;T&gt; curr = header.next;
        while (curr != header) {
            str += curr.nodeValue + ", ";
            curr = curr.next;
        }
        if (str.length() &gt; 0) {
            return str.substring(0, str.lastIndexOf(", "));
        } else {
            return str;
        }
    }

    public static void main(String[] args) {
            DLinkedList&lt;String&gt; d = new DLinkedList&lt;String&gt;();
            d.addOrder("t");
            d.addOrder("y");
            d.addOrder("e");
            d.addOrder("b");
            d.addOrder("p");
            System.out.println("List 1: t, y, e, b, p" + "\nList 1 added and sort : " +d);
    }
}
</code></pre>

<p>I am confused/lost as to how to fix my issue. I want to create a double linked list of nodes that hold String values and as I add those string values into the list, the list auto-sort it by way of insertion sort. </p>

<p>I start it off with a node call header which has a null value. Then as I add the String "t, y, e, b, p" into the list using the <code>addOrder(T val)</code> method everything seem to work. It will print out in sorted order "b, e, p, t, y".</p>

<p>The problem occur if I decided not to print the "p" at the end and instead do "t, y, e, b, c" all I get print out is "b, c" instead of doing "b, c, e, t, y". If I add an "a" instead of a "p" or "c" at the end of the list, everything seem to be fine printing "a, b, e, t, y". So it seem like it work with everything that is not "c, d, e". Seem like I need to code a method to add a newNode that will go between them which I'm at lost as how to do it now.</p>

<p>Another problem occurs if I decided to add string "t, y, e, v, p". It seems like this just prints "e, p". Which seems like it added "t, y, e, v" but when "p" comes in, it dropped "t, y, v" and left "e, p".</p>

<p>It seems like I can't add anything between "f-t", but anything before or after that is fine. I have a feeling it has something to do with my index "curr" that maybe it's stuck with my node header.</p>
