CODEWITHSUNDEEP
javalistsorting
Afonso Matos
Afonso Matos

Reputation: 2476

Sorting a list from the beginning

I have a list of objects that will take lots of adds/removes. I want the list to be sorted according to a certain function.

Right now, everytime I add a new object, I do:

list.add(obj1);
Collections.sort(list1, comparator);

Removing an object doesn't "unsort" the list, so I only need to do this for the add operation.

However, Collections.sort is O(>N) which is not very fast.

Is there any structure in java that allows me to keep a sorted list from the very beginning?

Forgot to mention

I tried to use TreeSet. It allows me to a pass a comparator which will be used for sorting but which will also be used to remove elements which is not what I want. I want it to be sorted but the remove functionality be identical to a list.

Upvotes: 0

Views: 193

Answers (2)

tucuxi
tucuxi

Reputation: 17945

As Alencar proposes, use Collections.binarySearch(yourList, key, comparator) to find the correct insert position. This is far faster than looking up the whole list, since binarySearch only needs log2(size of list) queries to find the correct insertion position.

So, if your insert code was

void sortedInsert(List<T> list, T value, Comparator<T> comparator) {
  int pos=0;
  ListIterator<T> it=list.listIterator();
  while (it.hasNext() && comparator.compare(value, it.next()) < 0) pos ++;
  if (pos < it.previousIndex()) it.previous();
  it.add(value);
}

... and a faster version would be ...

void sortedInsert2(List<T> list, T value, Comparator<T> comparator) {
  int pos = Collections.binarySearch(list, value, comparator);
  if (pos < 0) {
     pos = -pos -1; // returns negatives if not found; see javadoc
  }
  list.insert(value, pos);
}

Note that the difference may not be that great, because inserting into a non-linked list requires shifting elements up. So if the underlying list is an ArrayList, copying, on average, half the elements one place to the right to make place for the new element results in O(n) extra time per copy. And if the list is linked, you still need to pay that O(n) penalty, but this time to perform the binary search -- in that case, it would probably be better to use the first version.

Note that the 1st version uses a ListIterator just in case you decide to use linked lists. For ArrayLists, it would be easier to use list.get(pos) and list.add(pos, value), but those are a very bad idea in the context of iterating linked lists.

Upvotes: 2

Alencar Hentges
Alencar Hentges

Reputation: 23

Can't you add the object in the "right" place? already sorted?

You said that every time you add a new object you sort the list/collection.

Maybe you can use a Binary Search to find the exact index you need to insert the new value or use your comparator to find.

Upvotes: 1

Related Questions