Sorted array list in Java

Question

I m baffled that I can t find a quick answer to this   I m essentially looking for a datastructure in Java which implements the java util List interface  but which stores its members in a sorted order   I know that you can use a normal ArrayList and use Collections sort   on it  but I have a scenario where I am occasionally adding and often retrieving members from my list and I don t want to have to sort it every time I retrieve a member in case a new one has been added   Can anyone point me towards such a thing which exists in the JDK or even 3rd party libraries   EDIT   The datastructure will need to preserve duplicates   ANSWER s SUMMARY   I found all of this very interesting and learned a lot   Aioobe in particular deserves mention for his perseverance in trying to achieve my requirements above  mainly a sorted java util List implementation which supports duplicates    I have accepted his answer as the most accurate for what I asked and most thought provoking on the implications of what I was looking for even if what I asked wasn t exactly what I needed     The problem with what I asked for lies in the List interface itself and the concept of optional methods in an interface   To quote the javadoc      The user of this interface has precise control over where in the list each element is inserted    Inserting into a sorted list doesn t have precise control over insertion point   Then  you have to think how you will handle some of the methods   Take add for example      public boolean add Object o    Appends the specified element to the end of this list  optional operation      You are now left in the uncomfortable situation of either 1  Breaking the contract and implementing a sorted version of add 2  Letting add add an element to the end of the list  breaking your sorted order 3  Leaving add out  as its optional  by throwing an UnsupportedOperationException and implementing another method which adds items in a sorted order   Option 3 is probably the best  but I find it unsavory having an add method you can t use and another sortedAdd method which isn t in the interface   Other related solutions  in no particular order     java util PriorityQueue which is probably closest to what I needed than what I asked for   A queue isn t the most precise definition of a collection of objects in my case  but functionally it does everything I need it to   net sourceforge nite util SortedList   However  this implementation breaks the contract of the List interface by implementing the sorting in the add Object obj  method and bizarrely has a no effect method for add int index  Object obj    General consensus suggests throw new UnsupportedOperationException   might be a better choice in this scenario  Guava s TreeMultiSet A set implementation which supports duplicates ca odell glazedlists SortedList  This class comes with the caveat in its javadoc  Warning  This class breaks the contract required by List

User · Answer

I think the choice between SortedSets Lists and  normal  sortable collections depends  whether you need sorting only for presentation purposes or at almost every point during runtime  Using a sorted collection may be much more expensive because the sorting is done everytime you insert an element    If you can t opt for a collection in the JDK  you can take a look at the Apache Commons Collections

User · Answer

Since the currently proposed implementations which do implement a sorted list by breaking the Collection API  have an own implementation of a tree or something similar  I was curios how an implementation based on the TreeMap would perform   Especialy since the TreeSet does base on TreeMap  too   If someone is interested in that  too  he or she can feel free to look into it   TreeList  Its part of the core library  you can add it via Maven dependency of course   Apache License   Currently the implementation seems to compare quite well on the same level than the guava SortedMultiSet and to the TreeList of the Apache Commons library   But I would be happy if more than only me would test the implementation to be sure I did not miss something important   Best regards

User · Answer

Have a look at SortedList       This class implements a sorted list  It is constructed with a comparator that can compare two objects and sort objects accordingly  When you add an object to the list  it is inserted in the correct place  Object that are equal according to the comparator  will be in the list in the order that they were added to this list  Add only objects that the comparator can compare           When the list already contains objects that are equal according to the comparator  the new object will be inserted immediately after these other objects

User · Answer

You can try Guava s TreeMultiSet    Multiset lt Integer gt  ms TreeMultiset create Arrays asList 1 2 3 1 1 -1 2 4 5 100     System out println ms

User · Answer

Lists typically preserve the order in which items are added  Do you definitely need a list  or would a sorted set  e g  TreeSet lt E gt   be okay for you  Basically  do you need to need to preserve duplicates

User · Answer

I had the same problem  So I took the source code of java util TreeMap and wrote IndexedTreeMap  It implements my own IndexedNavigableMap   public interface IndexedNavigableMap lt K  V gt  extends NavigableMap lt K  V gt       K exactKey int index      Entry lt K  V gt  exactEntry int index      int keyIndex K k       The implementation is based on updating node weights in the red-black tree when it is changed  Weight is the number of child nodes beneath a given node  plus one - self  For example when a tree is rotated to the left       private void rotateLeft Entry lt K  V gt  p        if  p    null            Entry lt K  V gt  r   p right           int delta   getWeight r left  - getWeight p right           p right   r left          p updateWeight delta            if  r left    null                r left parent   p                     r parent   p parent            if  p parent    null                root   r            else if  p parent left    p                delta   getWeight r  - getWeight p parent left               p parent left   r              p parent updateWeight delta             else               delta   getWeight r  - getWeight p parent right               p parent right   r              p parent updateWeight delta                      delta   getWeight p  - getWeight r left           r left   p          r updateWeight delta            p parent   r              updateWeight simply updates weights up to the root      void updateWeight int delta            weight    delta          Entry lt K  V gt  p   parent          while  p    null                p weight    delta              p   p parent                    And when we need to find the element by index here is the implementation that uses weights   public K exactKey int index        if  index  lt  0    index  gt  size   - 1            throw new ArrayIndexOutOfBoundsException              return getExactKey root  index      private K getExactKey Entry lt K  V gt  e  int index        if  e left    null  amp  amp  index    0            return e key            if  e left    null  amp  amp  e right    null            return e key            if  e left    null  amp  amp  e left weight  gt  index            return getExactKey e left  index             if  e left    null  amp  amp  e left weight    index            return e key            return getExactKey e right  index -  e left    null   0   e left weight  - 1       Also comes in very handy finding the index of a key       public int keyIndex K key        if  key    null            throw new NullPointerException              Entry lt K  V gt  e   getEntry key       if  e    null            throw new NullPointerException              if  e    root            return getWeight e  - getWeight e right  - 1   index to return           int index   0      int cmp      index    getWeight e left        Entry lt K  V gt  p   e parent         split comparator and comparable paths     Comparator lt   super K gt  cpr   comparator      if  cpr    null            while  p    null                cmp   cpr compare key  p key               if  cmp  gt  0                    index    getWeight p left    1                            p   p parent                  else           Comparable lt   super K gt  k    Comparable lt   super K gt   key          while  p    null                if  k compareTo p key   gt  0                    index    getWeight p left    1                            p   p parent                      return index      You can find the result of this work at http   code google com p indexed-tree-map   TreeSet TreeMap  as well as their indexed counterparts from the indexed-tree-map project  do not allow duplicate keys   you can use 1 key for an array of values  If you need a SortedSet with duplicates use TreeMap with values as arrays  I would do that

User · Answer

It might be a bit too heavyweight for you  but GlazedLists has a SortedList that is perfect to use as the model of a table or JList

User · Answer

Minimalistic Solution  Here is a  minimal  solution   class SortedArrayList lt T gt  extends ArrayList lt T gt          SuppressWarnings  unchecked       public void insertSorted T value            add value           Comparable lt T gt  cmp    Comparable lt T gt   value          for  int i   size  -1  i  gt  0  amp  amp  cmp compareTo get i-1    lt  0  i--              Collections swap this  i  i-1             The insert runs in linear time  but that would be what you would get using an ArrayList anyway  all elements to the right of the inserted element would have to be shifted one way or another    Inserting something non-comparable results in a ClassCastException   This is the approach taken by PriorityQueue as well  A priority queue relying on natural ordering also does not permit insertion of non-comparable objects  doing so may result in ClassCastException     Overriding List add  Note that overriding List add  or List addAll for that matter  to insert elements in a sorted fashion would be a direct violation of the interface specification  What you could do  is to override this method to throw an UnsupportedOperationException   From the docs of List add      boolean add E e     nbsp  nbsp  nbsp  nbsp Appends the specified element to the end of this list  optional operation     Same reasoning applies for both versions of add  both versions of addAll and set   All of which are optional operations according to the list interface      Some tests  SortedArrayList lt String gt  test   new SortedArrayList lt String gt      test insertSorted  ddd       System out println test   test insertSorted  aaa       System out println test   test insertSorted  ccc       System out println test   test insertSorted  bbb       System out println test   test insertSorted  eee       System out println test         prints    ddd   aaa  ddd   aaa  ccc  ddd   aaa  bbb  ccc  ddd   aaa  bbb  ccc  ddd  eee

User · Answer

You could subclass ArrayList  and call Collections sort this  after any element is added - you would need to override two versions of add  and two of addAll  to do this   Performance would not be as good as a smarter implementation which inserted elements in the right place  but it would do the job  If addition to the list is rare  the cost amortised over all operations on the list should be low

User · Answer

Aioobe s approach is the way to go  I would like to suggest the following improvement over his solution though   class SortedList lt T gt  extends ArrayList lt T gt         public void insertSorted T value            int insertPoint   insertPoint value           add insertPoint  value                          return The insert point for a new value  If the value is found the insert point can be any        of the possible positions that keeps the collection sorted   33 or 3 3 or 33                private int insertPoint T key            int low   0          int high   size   - 1           while  low  lt   high                int mid    low   high   gt  gt  gt  1              Comparable lt   super T gt  midVal    Comparable lt T gt   get mid               int cmp   midVal compareTo key                if  cmp  lt  0                  low   mid   1              else if  cmp  gt  0                  high   mid - 1              else                   return mid     key found                                  return low      key not found           aioobe s solution gets very slow when using large lists  Using the fact that the list is sorted allows us to find the insert point for new values using binary search   I would also use composition over inheritance  something along the lines of   SortedList lt E gt  implements List lt E gt   RandomAccess  Cloneable  java io Serializable

User · Answer

Just make a new class like this   public class SortedList lt T gt  extends ArrayList lt T gt     private final Comparator lt   super T gt  comparator   public SortedList         super        this comparator   null     public SortedList Comparator lt T gt  comparator        super        this comparator   comparator      Override public boolean add T item        int index   comparator    null   Collections binarySearch  List lt   extends Comparable lt   super T gt  gt  this  item                Collections binarySearch this  item  comparator       if  index  lt  0            index   index   -1 - 2            super add index 1  item       return true      Override public void add int index  T item        throw new UnsupportedOperationException   add  with an index is not supported in SortedArrayList        Override public boolean addAll Collection lt   extends T gt  items        boolean allAdded   true      for  T item   items            allAdded   allAdded  amp  amp  add item             return allAdded      Override public boolean addAll int index  Collection lt   extends T gt  items        throw new UnsupportedOperationException   addAll  with an index is not supported in SortedArrayList           You can test it like this       List lt Integer gt  list   new SortedArrayList lt  gt   Integer i1  Integer i2  - gt  i1 compareTo i2        for  Integer i   Arrays asList 4  7  3  8  9  25  20  23  52  3             list add i             System out println list

User · Answer

Use java util PriorityQueue

[java] Sorted array list in Java

Examples related to java

Examples related to data-structures

Examples related to sorted