cyprian said:
if the linear search in List interface are costly, according to the
api, are there alternative searches provided for in the api for List?
Linear searches are O(n). So for very large length lists it is slow. For
short lists it doesn't really matter.
(
http://en.wikipedia.org/wiki/Big_O_notation )
If you have a Comparator and sort the list, you can use
Collections.binarySearch. The will give O(log n) for a RandomAccess List
(such as ArrayList). For a LinkedList, I guess it will be O(n).
Alternatively you could have a separate Map, that maps onto indexes of
the List (possibly a List<Integer>, int[] if you the contents of the
List are not unique). That obviously requires keeping two data
structures (are you sure you need the List?), but runs at O(1).
If the List does not contain duplicates, then you might be able to use
LinkedHashSet. Again that will be O(1).
Tom Hawtin
