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 ?

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. — ajb
– ajb, Commented Aug 22, 2017 at 6:18
I've spent 7 hours trying to understand this, thank you! Now finally makes sense! — Alex Stroia
– Alex Stroia, Commented Aug 22, 2017 at 6:29
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
– Assafs, Commented Aug 23, 2017 at 12:05
@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 :-) — Assafs
– Assafs, Commented Sep 26, 2017 at 6:52

Assafs · Accepted Answer · 2017-08-22 06:41:55Z

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.

nagendra547 · Accepted Answer · 2017-08-22 06:36:34Z

0

This is implementation of

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

answered Aug 22, 2017 at 6:36

nagendra547

6,4403 gold badges34 silver badges48 bronze badges

Collectives™ on Stack Overflow

Java - Ordered Linked List algorithm

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related