CODEWITHSUNDEEP
javaalgorithmsortingsortedlist
Dania
Dania

Reputation: 67

SortedList which allows repetition and random access of elements

I am developing an algorithm which relies heavily on the order of elements inside some list, however, that list needs to allow repetition and random access to its elements (without the use of iterator). I've searched for such a thing in java, but the found options were always lacking one of the conditions I mentioned.

Can anyone please suggest me a solution in java for this problem, with a low or moderate time complexity?

If I extended the class of ArrayList and override the method add, and inside the method after addition I call collection.sort (), would that be good regarding time complexity?

I think adding an element takes a constant time since it's directly added to the end of the list, and the sort method takes n logn, so in this case, will insertion take n logn time?

Any help is appreciated.

Thanks.

Upvotes: 0

Views: 540

Answers (2)

rakesh99
rakesh99

Reputation: 1266

You may use a TreeMap which stores the keys in sorted order and number of times that key occurs ,you can store as as values. Now you can iterate over the Map and populate an ArrayList (filling duplicates where a key's value is greater than 0) Overall complexity is nlogn space complexity log n

if you extend ArrayList and find insertion point/or call collections.sort() your algorithm is O(n^2 *logn) in best case. If your initial capacity of List isn't sufficient for all insertions it will resize(an extra O(n) operation)

Upvotes: 1

whaleberg
whaleberg

Reputation: 2189

You could try a TreeMultiset from google's Guava library. It doesn't have an indexed random accessor, but you can access sublists by specifying range bounds.

http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/index.html

Upvotes: 1

Related Questions