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 ?

• ajb: This algorithm makes sure the list is always in sorted order, so you can't have "9 11 10" in the linked list. I don't understand what you're asking.
• Alex Stroia: I've spent 7 hours trying to understand this, thank you! Now finally makes sense!
• Assafs: Alex, if my answer below was helpful, may I kindly ask you accept it by clicking on the grey check mark, making it green?
• Assafs: @AlexStroia, any chance I can convince you to accept my answer below? It's just a click on the gray check mark next to it, making it green. This answer is one of the only few non-accepted answers I have, I'm trying to complete a set :-)

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.