Search code examples
javadata-structuresguava

Java data structures: IndexedSet or HashList

Is there a Java data structure that satisfies the following requirements?

  1. Indexed access. (i.e., i should be able to retrieve objects with get(i))
  2. Constant time get() & contains() methods
  3. Should enforce ordering (enforced by Comparator)
  4. Should be mutable

I could not find any in Oracle's JDK or Guava that gives the above listed features out of the box

List provides indexed access & some kind of ordering but not constant-time contains(). SortedSet and SortedMap provide constant-time contains() and sorting but not indexed access!!

Am I missing something or is there any data structure out there that could be manipulated to provide the features listed above?

My current solution:

A combination of HashMap & ArrayList => I use ArrayList to store the sorted keys which provides indexed access and use HashMap for constant-time contains() method. I just wanna make sure that I am not trying to re-invent something that has already been done

Why I need this:

Let's call this data structure SortedDataStore I am developing an Android app & most of the UI in that is a list of items and these items are pulled off the local db. (the local db gets its data from a remote server). The UI is populated using RecyclerView and I need constant-time indexed access to get the object from my SortedDataStore and populate the views. Since the order of items is decided based on their attributes, there is a need for sorting. Also the data gets updated a lot (items get modified, deleted and new items get added). When the new data comes in, I check against my SortedDataStore if it should be deleted, or added or modified (and moved to another index) for which I need constant-time contains() & mutability.

Solution
    • Based on what you've described as your expected data size, ArrayList seems like it would actually be just fine in practice -- your data isn't big enough for the linear-time factor to matter that much.
    • Otherwise, what you're doing is the right solution; there's no provided mutable data structure that does all that at once.
    • If you can avoid mutation, Guava's ImmutableSet satisfies the rest of your demands. You can use ImmutableSet.asList().get(index) to get out elements by index in O(1) time, and otherwise it supports O(1) contains and insertion order.