CODEWITHSUNDEEP
javadata-structures
Cheok Yan Cheng
Cheok Yan Cheng

Reputation: 42710

Data structure with O(1) performance for get(int index) and ability to avoid duplication

Set is an obvious choice, if I do not want to have duplication on my list of data.

However, Set doesn't have get(int index) method : Why doesn't java.util.Set have get(int index)?

Several suggestions to implement a pseudo get(int index) and none of them are efficient.

  1. toArray and access the new array by index.
  2. Get the iterator, and use a for loop to access the indexed element by count.

Is there any advanced data structure, which enables me to

  1. Avoid duplication.
  2. Have O(1) performance for get(int index).

Upvotes: 4

Views: 215

Answers (2)

Jon Skeet
Jon Skeet

Reputation: 1500805

The simplest approach is to have a composite collection which contains a HashSet and an ArrayList. Your add operation would try to add it to the set, and only add it to the list if that has actually added a new item. The get operation would just get from the list.

Do you ever need to remove values? If not, that makes life simpler - otherwise, removing an item would be an O(N) operation. Not necessarily a problem, but something to bear in mind.

Upvotes: 9

Jigar Joshi
Jigar Joshi

Reputation: 240898

How about BiMap<Integer, T>

A bimap (or "bidirectional map") is a map that preserves the uniqueness of its values as well as that of its keys. This constraint enables bimaps to support an "inverse view", which is another bimap containing the same entries as this bimap but with reversed keys and values.

Upvotes: 3

Related Questions