0

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.

Dania
  • 67
  • 3
  • 12
  • possible duplicate of [Java List Sorting: Is there a way to keep a list permantly sorted automatically like TreeMap?](http://stackoverflow.com/questions/4903611/java-list-sorting-is-there-a-way-to-keep-a-list-permantly-sorted-automatically) – azurefrog Apr 02 '15 at 18:35
  • You might also want to take a look at [this question](http://stackoverflow.com/questions/8725387/why-is-there-no-sortedlist-in-java). It's a bit more general purpose, but might also be useful to you. – azurefrog Apr 02 '15 at 18:36
  • Thank you for providing this link, but I need an algorithm to implement, if you can provide me with any hint or suggestion, it will be a great help. Thanks – Dania Apr 02 '15 at 18:38
  • 1
    You kind of need a "TreeMultiset". TreeSet will work for you except for the duplicates issue. One thing you could try is wrapping TreeSet with your own container, such that it stores the pair (E, count) as each element of the TreeSet. When you try to add a duplicate, you increment the counter. And when you remove, decrement the counter until it is 0 in which case you really remove it. – VoidStar Apr 02 '15 at 18:41
  • TreeMultiset doesn't allow for random access – Neal Ehardt Apr 02 '15 at 18:44
  • Thank you @VoidStar, sounds great can you please provide me a link which contains an example of this? Also, I've updated the question, is the method I mentioned good? Thank you – Dania Apr 02 '15 at 18:45
  • @ Neal Ehardt, thanks for your comment, what about the method I added in the question, is it efficient? – Dania Apr 02 '15 at 18:46
  • @Dania No, O(n log n) insertion is incredibly slow. You can get O(n) insertion by searching the array for the correct insertion index O(n), then calling add(elt, idx) which is also O(n). – Neal Ehardt Apr 02 '15 at 18:49
  • @NealEhardt Thanks a lot for your useful answer, but how can I know the proper place of inserting the element without sorting? What method can provide me this operation with O(n)? Thanks – Dania Apr 02 '15 at 18:53
  • You can find the proper position in a sorted list in O(log n) by binary search. Basically you look into the middle of the list, if the element is equal, you have found the position, if it is smaller, you need to look into the upper half, if bigger in the lower half of the list. – Gregor Raýman Apr 02 '15 at 19:01
  • @ GregorRaýman Thank you, but this means I will need sorting with complexity of at least O(n logn), in addition to that I will have the O(log n) of the binary search, so totally and approximately, the complexity is O(n logn), is there any way faster? – Dania Apr 02 '15 at 19:09
  • @Dania no, you won't need sorting, since every addition to the list maintains the list ordered. Why would you sort an already sorted list? – JB Nizet Apr 02 '15 at 19:23
  • @JBNizet Oh yes, thank you for your answer, I didn't pay attention that it was written as sorted list in the comment. You're right no need for the sorting. – Dania Apr 03 '15 at 16:25

2 Answers2

1

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

whaleberg
  • 2,093
  • 22
  • 26
1

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)

rakesh99
  • 1,234
  • 19
  • 34
  • Great answer, thanks. is it possible to sort the tree based on the value instead of the key? – Dania Apr 03 '15 at 16:23
  • yes u can implement a comparator/or compareTo of key class to compare using values..this would require a extra lookups in the map. – rakesh99 Apr 04 '15 at 20:35