I have to sort a large list (more than 10,000 elements). On adding an element I have to insert it on the right place. I saw that an ArrayList will shift all the element that are after the insertion point.
How do all the different implementation of the List interface behave in such a case? And what are the pros and the cons when choosing one implementation over the other?
The two main implementations of List are ArrayList and LinkedList. There are others but they are generally used in specialis situations.
ArrayList can be accessed very quickly by index because it is backed by an array - you just need array[i] - but modifying the list requires moving much of the underlying array around so that is not efficient.
You can add/remove items with LinkedList very efficiently but finding the nth entry is slow because it has to start at the head and walk the list counting nodes until it gets to the required location.
Probably duplicate, but i will give you a hint.
To sort your data you can use:
Collections.sort(List list);
method, it will convert List to Array anyway, so you don't have to care about too much about type of List implementation. All it needs is interface Comparable implemented in your objects.
Can your data contain duplicates?
If NO, you can use a TreeSet<?>
If YES, you can use a TreeMap<?, Integer> where the Integer is the count per item
