Java - Ordered Linked List algorithm

Question

I have a problem in understanding the algorithm of the Linked List, if someone could explain for me, I understood almost everything only a specific part, when the new added item is less than the previous item so we have to move the new item to the left

public boolean addItem(ListItem newItem) {
    if (this.root == null) {
        // The list was empty, so this item becomes the head of the list
        this.root = newItem;
        return true;
    }

    ListItem currentItem = this.root;
    while (currentItem != null) {
        int comparison = (currentItem.compareTo(newItem));
        if (comparison < 0) {
            // newItem is greater, move right if possible
            if (currentItem.next() != null) {
                currentItem = currentItem.next();
            } else {
                // there is no next, so insert at end of list
                currentItem.setNext(newItem).setPrevious(currentItem);
                return true;
            }
        } else if (comparison > 0) { 
            // newItem is less, insert before
            if (currentItem.previous() != null) {
                currentItem.previous().setNext(newItem);//previous entry is now the added item
                newItem.setPrevious(currentItem.previous()); //the new item previous entry is setted to the current item previous value
                newItem.setNext(currentItem); //pointing the new item to the current item
                currentItem.setPrevious(newItem); //the previous entry of the current item is equal with the new item

            } else {
                // the node with a previous is the root
                newItem.setNext(this.root).setPrevious(newItem);
                this.root = newItem;
            }
            return true;
        } else {
            // equal
            System.out.println(newItem.getValue() + " is already present, not added.");
            return false;
        }
    }

    return false;
}

so where comparison is greater than 0, so lets say I have: 9 11 10 in my Linked List, so the previous entry of 10, which is 11 goes to the previous position to the right, newItem(10)is setted to the previous position with the currentItem.previous value, so the current item is not also 10 now ?

Answer 1

The algorithm is simple. To make it clearer, let me replace the code blocks with a simple English explanation of what it does:

if the list is empty, put the new item as the root of the list.
otherwise, if the list has items, take the root as the current item to compare it to. 
this will go over a few iterations until we find the right spot to insert the new item. 

For every iteration:

  if the new item is bigger than the current spot on the list, move up one spot in the 
  list to compare next time.

  else, if the new item is smaller than the current spot, 
  and the current spot is not the root of the list - insert 
  the new item between the current spot and the one before it.

  If the current spot is the root of the list, make the new item 
  the root of the list and tag along the entire list as its next items.

And that's it - you always get a sorted list after a few iterations (the most iterations is the length of the list). you start from the beginning of the list and look at each item against the one you have to insert. If as long as it's bigger than the current spot you move up the list. When you passed the spot it needs to be (the previous spot was smaller, the next spot is bigger) you just insert it in the middle. And you may insert it at the very beginning or at the very end. I hope that helps you understand the algorithm better.

Answer 2

This is implementation of

• sorted Linked List
• No duplicates are allowed in Linked List
• All elements are unique and in ascending order.