List with comparable Vs TreeSet

Question

Option 1: Create a list that implements Comparable and sorts it with collection.sort (List l) every time you add a value. Option 2: Create a TreeSet (which keeps itself sorted all the time).

Which one will be faster? I ask about this because List gives me the ListIterator I need in my case, since it allows me to add an element during iteration.

Answer 1

The most important differences:

Criterion | List with Collections.sort | TreeSet ----------------+----------------------------+--------- cost of adding | O(n log n) | O(log n) equal sort keys | permitted | eliminated as duplicates iteration | bidirectional, can insert | unidirectional, can not insert 

To insert an element during iteration without receiving a ConcurrentModificationException , you can do:

 for (E e : new ArrayList<E>(collection)) { // some other code collection.add(anotherE); } 

Answer 2

Collections.sort uses a modified merge sort with nlog (n) time . If you call the method every time you add, you can get n ^ 2log (n) time. While insertion in TreeSet is guaranteed by log (n). Therefore, if you name it on every addition, it will become n.log (n) . Therefore, I would suggest using TreeSet instead. But TreeSet does not allow duplication, so this may affect your decision.

If you use List, instead of using Collections.sort there is one thing you can do to optimize; as you know, every time you insert an item into the list, the list is already sorted, so using insertion sorting will give you better performance, since insertion sorting works better in such cases.

Answer 3

Use TreeSet here.

Adding to a TreeSet is a log(n) operation. Adding to the list is const time, but sorting is n log(n) .