java list implementation

Question

I have the following use case:

• a list containing objects with various properties - e.g name,type,date
• the list can contain a lot of elements(50k - 200k)

I wanted to ask what would be the best list implementation for this situation given the fact that I need to do operations on the list such as

• order - e.g by type(alphabetically)
• filtering - e.g. by date
• no inserts
• sublists - similar to paging.

Thanks.

Answer 1

A single collection type can't satisfy all of those use-cases. The nearest I can see is TreeSet.

• order - Implement your object to override equals and hascode based on type
• sublists - headSet, tailSet
• filtering - roll your won

Answer 2

java.util.ArrayList seems best in this case (backed up by a vector). One thing that you need to do upfront is reserve enough space when constructing the instance (it's best if you know the number of elements beforehead), to avoid copying on resized vector allocations.

Another win compared to LinkedList is the absense of internode references which reduces the required heap size roughly twice compared to ArrayList.

• append: O(1) (given no inserts)
• ordering = sorting: O(n*log(n))
• filtering: O(n)
• sublist: O(1)

Answer 3

If you know the size of the list (or an upper bound) before-hand and can guarantee no insertions then you need to use ArrayList.

It is backed up by an array so lookups are fast.