Java: What is the best way to traverse and insert element into a ranked linked list?

Question

Due to the frequent insertions and deletions at the head and tail of the linked list, I have chosen to use the linked list from the Java API. And the linked list will be ranked in descending order, i.e. 100,98,97,95,90

LinkedList<MyObject> mylinkedlist = new LinkedList<MyObject>();

Myobject new_value = new MyObject(96);

Occasionally I have to insert elements into this linked list(not at the head and tail). Because the linked list must be in descending order, I have to traverse the linked list in descending order from the head or ascending order from the tail and then insert it into a correct index.

I came up with an attempt as follow

  int i;
  for(int i=0; i<mylinkedlist.size(); i++)
  {
      if(mylinkedlist.get(num).getInt() <= new_value.getInt()){
         break;
      }
  }

   mylinkedlist.add(i,new_value)

I can just tell my code above is really poor. However, is there a way to optimize my code and avoid using break and at the same time , also avoid traversing the entire linked list because it could be super long ?

It would be greatly appreciated if code example could be provided. Thanks.

UPDATE: Sincere apologies for not phrasing my questions properly. MY problem should be that given the linked list currently contains 100,98,97,95,90, if I want to insert a new and different value, say 96. How should one detect the index of the linked list such that the new value 96 can be inserted into it, while preserving the descending order of the linked list?

It is really important that the (1) descending order of the list and the (2) uniqueness of elements in the list are preserved in this problem.

Note that accessing a linked list's elements by index is not fast at all. — daniu, Apr 15 '18 at 20:36

score 1 · Answer 1 · answered Apr 15 '18 at 21:34

If you have to use a list, there is a possibility to achieve the same result using the standard API: Collections.binarySearch method provides exactly the feature you are looking for.

So the code would resemble the following:

private static void insert(List<MyObject> items, MyObject newValue) {
  int insertionPoint =
      Collections.binarySearch(items, 
                               newValue, 
                               // reversed comparator is used because the items are in DESC order
                               Comparator.comparingInt(MyObject::getInt).reversed());
  // if newValue is not in the list, insertionPoint will be negative, see javadoc
  int i = (insertionPoint < 0) ? -insertionPoint - 1 : insertionPoint;
  // add it at i, even if duplicate (?)
  items.add(i, newValue);
}

This does not really optimise the solution, just cleans it up a bit, eliminating the break and reusing the standard API. The javadoc gives some detail about its efficiency:

This method runs in log(n) time for a "random access" list (which provides near-constant-time positional access). If the specified list does not implement the RandomAccess interface and is large, this method will do an iterator-based binary search that performs O(n) link traversals and O(log n) element comparisons.

If the list becomes huge and you begin to look for efficiency, I'd recommend to switch to ArrayList, which implements RandomAccess and will be more efficient provided that the order of items is respected.

If your collection does not allow duplicates, it will be much better to use a sorted set.

NayoR · Accepted Answer · 2018-04-16T07:09:23.583

You should consider using another data structure, as TreeSet.

This class implements SortedSet and use natural ordering or a comparator provided at the creation time. Then you'll just have to add the object, it will be automatically sorted.

Using natural ordering

In MyObject class:

public int compareTo(MyObject o) {
    return this.getInt() - o.getInt()
}

Using TreeSet:

SortedSet<MyObject> objectSet = new TreeSet<MyObject>();
Myobject newObject = new MyObject(95);
objectSet.add(newObject);

Using Comparator

If you don't want to modify MyObject class (for instance):

class MyObjectComp implements Comparator<MyObject> {

    @Override
    public int compare(MyObject o1, MyObject o2) {
        return o1.getInt() - o2.getInt();
    }

}

SortedSet<MyObject> objectSet = new TreeSet<MyObject>(new MyObjectComp());
Myobject newObject = new MyObject(95);
objectSet.add(newObject);

Descending Set

For a descending set, it is possible to use TreeSet's descendingSet method:

SortedSet<MyObject> objectSet = new TreeSet<MyObject>(new MyObjectComp()).descendingSet();
Myobject newObject = new MyObject(95);
objectSet.add(newObject);

For more information about sorted structures in Java, you can read this question.

How come it doesn’t say it is automatically sorted in the link ? And in my case, I need a list that is in descending order and another list in ascending order . Would it be able to do that ? Thanks. — mynameisJEFF, Apr 16 '18 at 02:02
Excuse me, I meant TreeSet instead of TreeList. I've editted the answer. The TreeSet's method descendingSet should provide you a descending Set — NayoR, Apr 16 '18 at 07:07

Java: What is the best way to traverse and insert element into a ranked linked list?

2 Answers2

Using natural ordering

Using Comparator

Descending Set