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.

Objects with various properties, that means objects of unrelated classes, or objects of classes who share same superclass? Or you mean objects with properties of various values? Be more specific.. — d1e
– d1e, Commented Feb 20, 2012 at 21:37
what about thread-safety? how many threads will populate it? — Sergey Benner
– Sergey Benner, Commented Feb 20, 2012 at 21:38

Savvas Dalkitsis · Accepted Answer · 2012-02-20 21:33:44Z

2

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.

answered Feb 20, 2012 at 21:33

Savvas Dalkitsis

11.6k17 gold badges67 silver badges104 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Alexander Pavlov · Accepted Answer · 2012-02-20 21:35:43Z

0

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)

answered Feb 20, 2012 at 21:35

Alexander Pavlov

32.4k5 gold badges71 silver badges95 bronze badges

Comments

Aravind Yarram · Accepted Answer · 2012-02-20 21:36:01Z

0

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

answered Feb 20, 2012 at 21:36

Aravind Yarram

80.5k49 gold badges239 silver badges335 bronze badges

Collectives™ on Stack Overflow

java list implementation

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related