Java doubly linked list looping

Question

My goal is to loop backwards through a list I have created and if an element is smaller than my chosen number t a node with the value of t will be inserted in front of the element that is smaller. Also, if every element in the list is bigger than t a node with the value of t will be put at the start of the list. Example:

DoublyLinkedList<Integer> list = new DoublyLinkedList<>();

list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);

list.addAtFirstSmaller(4);
System.out.println("Nodelist: " + list.toString());

And I should expect the outcome: [1, 2, 4, 3, 4, 5] But instead I get: [1, 2, 3, 4, 4, 5]

This is my code so far:

public void addAtFirstSmaller(T t)
{
    ListNode<T> node = tail;
    ListNode<T> newNode = new ListNode<T>(t);
    while(node.previous != null)
    {
        int compared = node.previous.element.compareTo(t);
        node = node.previous;
        if(compared < 0)
        {
            ListNode<T> temp = node.next;
            node.next = newNode;
            newNode.next = temp;
            newNode.next.previous = newNode;
            node.previous = null;
            size++;
        }
        else if(compared > 0 && node.previous == null)
        {
            addFirst(t);
            size++;
        }
    }
}

To me it seems like everything is pushed to the right. Any idea on what to do?

Answer 1

As you already verified: the example output is correct as the idea is to maintain the list sorted. The misinterpretation was understandable, as "in front of" is somewhat ambiguous.

However, there are still a few issues with your code:

• Although the assignment node.previous = null will make the loop end once you have inserted the new node, this breaks a previous link that really should remain untouched. Only the head node should have previous equal to null, while in general node could have a predecessor, which must remain its predecessor.

• newNode.previous never receives a value. It should be set to node.

• When the value to insert is greater than the value in the tail node, the node will be inserted at the wrong spot -- there is never a scenario in your code where the new node will become the new tail, yet this is a possibility that should be foreseen.

• I would assume that addFirst would already increase size, so increasing it again after you call this function is wrong. This really should be the responsibility of addFirst.

Assuming that you have implemented addLast, the corrected code could be like this:

public void addAtFirstSmaller(T t) {
    ListNode<T> node = tail;
    ListNode<T> newNode = new ListNode<T>(t);
    while (node != null && node.element.compareTo(t) >= 0) {
        node = node.previous;
    }
    if (node == null) {
        addFirst(t);
    } else if (node == tail) {
        addLast(t);
    } else {
        ListNode<T> temp = node.next;
        node.next = newNode;
        newNode.next = temp;
        newNode.previous = node;
        temp.previous = newNode;
        size++;
    }
}

In case you don't have it yet, addLast could look like this:

public void addLast(T t) {
    ListNode<T> newNode = new ListNode<T>(t);
    tail.next = t;
    t.previous = tail;
    tail = t;
    size++;
}