Sorted collection in Java

Question

I m a beginner in Java   Please suggest which collection s  can should be used for maintaining a sorted list in Java  I have tried Map and Set  but they weren t what I was looking for

User · Answer

You want the SortedSet implementations  namely TreeSet

User · Answer

Use Google Guava s TreeMultiset class  Guava has a spectacular collections API   One problem with providing an implementation of List that maintains sorted order is the promise made in the JavaDocs of the add   method

User · Answer

What you want is a binary search tree  It maintains sorted order while offering logarithmic access for searches  removals and insertions  unless you have a degenerated tree - then it s linear   It is quite easy to implement and you even can make it implement the List interface  but then the index-access gets complicated   Second approach is to have an ArrayList and then a bubble sort implementation  Because you are inserting or removing one element at a time  the access times for insertions and removals are linear  Searches are logarithmic and index access constant  times can get different for LinkedList   The only code you need is 5  maybe 6 lines of bubble sort

User · Answer

What I have done is implement List having a internal instance with all the methods delegated    public class ContactList implements List lt Contact gt   Serializable       private static final long serialVersionUID   -1862666454644475565L      private final List lt Contact gt  list   public ContactList         super        this list   new ArrayList lt Contact gt        public ContactList List lt Contact gt  list        super          copy and order list     List lt Contact gt aux  new ArrayList list       Collections sort aux        this list   aux     public void clear         list clear       public boolean contains Object object        return list contains object       After  I have implemented a new method  putOrdered  which insert in the proper position if the element doesn t exist or replace just in case it exist   public void putOrdered Contact contact        int index Collections binarySearch this list contact       if index lt 0           index  - index 1           list add index  contact        else          list set index  contact             If you want to allow repeated elements just implement addOrdered instead  or both    public void addOrdered Contact contact        int index Collections binarySearch this list contact       if index lt 0           index  - index 1             list add index  contact       If you want to avoid inserts you can also throw and unsupported operation exception on   add  and  set  methods    public boolean add Contact object        throw new UnsupportedOperationException  Use putOrdered instead            and also You have to be careful with ListIterator methods because they could modify your internal list  In this case you can return a copy of the internal list or again throw an exception   public ListIterator lt Contact gt  listIterator         return  new ArrayList lt Contact gt  list   listIterator

User · Answer

The problem with PriorityQueue is that it s backed up by an simple array  and the logic that gets the elements in order is done by the  queue 2 n 1  and queue 2  n 1    thingie  It works great if you just pull from head  but makes it useless if you are trying to call the  toArray on it at some point    I go around this problem by using com google common collect TreeMultimap  but I supply a custom Comparator for the values  wrapped in an Ordering  that never returns 0    ex  for Double   private static final Ordering lt Double gt  NoEqualOrder   Ordering from new Comparator lt Double gt            Override     public int compare Double d1  Double d2                if  d1  lt  d2                return -1                    else               return 1                        This way I get the values in order when I call  toArray    and also have duplicates

User · Answer

If you want to maintain a sorted list which you will frequently modify  i e  a structure which  in addition to being sorted  allows duplicates and whose elements can be efficiently referenced by index   then use an ArrayList but when you need to insert an element  always use Collections binarySearch   to determine the index at which you add a given element  The latter method tells you the index you need to insert at to keep your list in sorted order

User · Answer

You can use Arraylist and Treemap  as you said you want repeated values as well then you cant use TreeSet  though it is sorted as well  but you have to define comparator

User · Answer

There are a few options  I d suggest TreeSet if you don t want duplicates and the objects you re inserting are comparable   You can also use the static methods of the Collections class to do this   See Collections sort java util List  and TreeSet for more info

User · Answer

If you just want to sort a list  use any kind of List and use Collections sort    If you want to make sure elements in the list are unique and always sorted  use a SortedSet

User · Answer

Use sort   method to sort the list as below   List list   new ArrayList       add elements to the list  Comparator comparator   new SomeComparator     Collections sort list  comparator     For reference see the link  http   tutorials jenkov com java-collections sorting html

User · Answer

Using LambdaJ  You can try solving these tasks with LambdaJ if you are using prior versions to java 8  You can find it here  http   code google com p lambdaj   Here you have an example   Sort Iterative  List lt Person gt  sortedByAgePersons   new ArrayList lt Person gt  persons   Collections sort sortedByAgePersons  new Comparator lt Person gt              public int compare Person p1  Person p2               return Integer valueOf p1 getAge    compareTo p2 getAge                      Sort with LambdaJ  List lt Person gt  sortedByAgePersons   sort persons  on Person class  getAge        Of course  having this kind of beauty impacts in the performance  an average of 2 times   but can you find a more readable code   Sort with java 8 using lambda expression  Collections sort persons   p1  p2  - gt  p1 getAge   compareTo p2 getAge        or persons sort  p1  p2  - gt  p1 getAge   compareTo p2 getAge

User · Answer

You want the SortedSet implementations  namely TreeSet

User · Answer

Use TreeSet which gives elements in sorted order  OR use Collection sort   for external sorting with Comparator

User · Answer

You want the SortedSet implementations  namely TreeSet

User · Answer

For Set you can use TreeSet   TreeSet orders it s elements on the basis of a natural ordering or any sorting order passed to the Comparable for that particular object  For map use TreeMap  TreeMap provides the sorting over keys  To add an object as a key to the TreeMap that class should implement comparable interface which in turn forces to implement compare to   method which contains the definition of the sorting order  http   techmastertutorial in java-collection-impl html

User · Answer

If you want to maintain a sorted list which you will frequently modify  i e  a structure which  in addition to being sorted  allows duplicates and whose elements can be efficiently referenced by index   then use an ArrayList but when you need to insert an element  always use Collections binarySearch   to determine the index at which you add a given element  The latter method tells you the index you need to insert at to keep your list in sorted order

User · Answer

For Set you can use TreeSet   TreeSet orders it s elements on the basis of a natural ordering or any sorting order passed to the Comparable for that particular object  For map use TreeMap  TreeMap provides the sorting over keys  To add an object as a key to the TreeMap that class should implement comparable interface which in turn forces to implement compare to   method which contains the definition of the sorting order  http   techmastertutorial in java-collection-impl html

User · Answer

This comes very late  but there is a class in the JDK just for the purpose of having a sorted list  It is named  somewhat out of order with the other Sorted  interfaces   java util PriorityQueue   It can sort either Comparable lt   gt s or using a Comparator   The difference with a List sorted using Collections sort      is that this will maintain a partial order at all times  with O log n   insertion performance  by using a heap data structure  whereas inserting in a sorted ArrayList will be O n   i e   using binary search and move    However  unlike a List  PriorityQueue does not support indexed access  get 5    the only way to access items in a heap is to take them out  one at a time  thus the name PriorityQueue

User · Answer

TreeMap and TreeSet will give you an iteration over the contents in sorted order  Or you could use an ArrayList and use Collections sort   to sort it  All those classes are in java util

User · Answer

You can use Arraylist and Treemap  as you said you want repeated values as well then you cant use TreeSet  though it is sorted as well  but you have to define comparator

User · Answer

What I have done is implement List having a internal instance with all the methods delegated    public class ContactList implements List lt Contact gt   Serializable       private static final long serialVersionUID   -1862666454644475565L      private final List lt Contact gt  list   public ContactList         super        this list   new ArrayList lt Contact gt        public ContactList List lt Contact gt  list        super          copy and order list     List lt Contact gt aux  new ArrayList list       Collections sort aux        this list   aux     public void clear         list clear       public boolean contains Object object        return list contains object       After  I have implemented a new method  putOrdered  which insert in the proper position if the element doesn t exist or replace just in case it exist   public void putOrdered Contact contact        int index Collections binarySearch this list contact       if index lt 0           index  - index 1           list add index  contact        else          list set index  contact             If you want to allow repeated elements just implement addOrdered instead  or both    public void addOrdered Contact contact        int index Collections binarySearch this list contact       if index lt 0           index  - index 1             list add index  contact       If you want to avoid inserts you can also throw and unsupported operation exception on   add  and  set  methods    public boolean add Contact object        throw new UnsupportedOperationException  Use putOrdered instead            and also You have to be careful with ListIterator methods because they could modify your internal list  In this case you can return a copy of the internal list or again throw an exception   public ListIterator lt Contact gt  listIterator         return  new ArrayList lt Contact gt  list   listIterator

User · Answer

import java util TreeSet   public class Ass3       TreeSet lt String gt str new TreeSet lt String gt         str add  dog        str add  doonkey        str add  rat        str add  rabbit        str add  elephant        System out println str

User · Answer

If you just want to sort a list  use any kind of List and use Collections sort    If you want to make sure elements in the list are unique and always sorted  use a SortedSet

User · Answer

TreeMap and TreeSet will give you an iteration over the contents in sorted order  Or you could use an ArrayList and use Collections sort   to sort it  All those classes are in java util

User · Answer

If you just want to sort a list  use any kind of List and use Collections sort    If you want to make sure elements in the list are unique and always sorted  use a SortedSet

User · Answer

If you want to maintain a sorted list which you will frequently modify  i e  a structure which  in addition to being sorted  allows duplicates and whose elements can be efficiently referenced by index   then use an ArrayList but when you need to insert an element  always use Collections binarySearch   to determine the index at which you add a given element  The latter method tells you the index you need to insert at to keep your list in sorted order

User · Answer

TreeMap and TreeSet will give you an iteration over the contents in sorted order  Or you could use an ArrayList and use Collections sort   to sort it  All those classes are in java util

User · Answer

import java util TreeSet   public class Ass3       TreeSet lt String gt str new TreeSet lt String gt         str add  dog        str add  doonkey        str add  rat        str add  rabbit        str add  elephant        System out println str

User · Answer

with Java 8 Comparator  if we want to sort list then  Here are the 10 most populated cities in the world and we want to sort it by name  as reported by Time        Osaka  Japan      Mexico City  Mexico             Beijing  China      S  o Paulo  Brazil      Mumbai  India      Shanghai         China      Delhi  India      Tokyo  Japan    import java util Arrays   import java util Comparator   import java util List   public class SortCityList                  Here are the 10 most populated cities in the world and we want to sort it by        name  as reported by Time  Osaka  Japan      Mexico City  Mexico             Beijing  China      S  o Paulo  Brazil      Mumbai  India      Shanghai         China      Delhi  India      Tokyo  Japan              public static void main String   args            List lt String gt  cities   Arrays asList  Osaka    Mexico City    S  o Paulo    Mumbai    Shanghai    Delhi                    Tokyo            System out println  Before Sorting List is -            System out println cities           System out println  --------------------------------             System out println  After Use of List sort String CASE INSENSITIVE ORDER   amp  Sorting List is -            cities sort String CASE INSENSITIVE ORDER           System out println cities           System out println  --------------------------------            System out println  After Use of List sort Comparator naturalOrder     amp  Sorting List is -            cities sort Comparator naturalOrder             System out println cities

User · Answer

TreeSet would not work because they do not allow duplicates plus they do not provide method to fetch element at specific position  PriorityQueue would not work because it does not allow fetching elements at specific position which is a basic requirement for a list  I think you need to implement your own algorithm to maintain a sorted list in Java with O logn  insert time  unless you do not need duplicates  Maybe a solution could be using a TreeMap where the key is a subclass of the item overriding the equals method so that duplicates are allowed

User · Answer

The most efficient way to implement a sorted list like you want would be to implement an indexable skiplist as in here  Wikipedia  Indexable skiplist   It would allow to have inserts removals in O log n   and would allow to have indexed access at the same time  And it would also allow duplicates   Skiplist is a pretty interesting and  I would say  underrated data structure  Unfortunately there is no indexed skiplist implementation in Java base library  but you can use one of open source implementations or implement it yourself  There are regular Skiplist implementations like ConcurrentSkipListSet and ConcurrentSkipListMap

User · Answer

If you want to maintain a sorted list which you will frequently modify  i e  a structure which  in addition to being sorted  allows duplicates and whose elements can be efficiently referenced by index   then use an ArrayList but when you need to insert an element  always use Collections binarySearch   to determine the index at which you add a given element  The latter method tells you the index you need to insert at to keep your list in sorted order

User · Answer

There are a few options  I d suggest TreeSet if you don t want duplicates and the objects you re inserting are comparable   You can also use the static methods of the Collections class to do this   See Collections sort java util List  and TreeSet for more info

User · Answer

TreeSet would not work because they do not allow duplicates plus they do not provide method to fetch element at specific position  PriorityQueue would not work because it does not allow fetching elements at specific position which is a basic requirement for a list  I think you need to implement your own algorithm to maintain a sorted list in Java with O logn  insert time  unless you do not need duplicates  Maybe a solution could be using a TreeMap where the key is a subclass of the item overriding the equals method so that duplicates are allowed

User · Answer

There are a few options  I d suggest TreeSet if you don t want duplicates and the objects you re inserting are comparable   You can also use the static methods of the Collections class to do this   See Collections sort java util List  and TreeSet for more info

User · Answer

with Java 8 Comparator  if we want to sort list then  Here are the 10 most populated cities in the world and we want to sort it by name  as reported by Time        Osaka  Japan      Mexico City  Mexico             Beijing  China      S  o Paulo  Brazil      Mumbai  India      Shanghai         China      Delhi  India      Tokyo  Japan    import java util Arrays   import java util Comparator   import java util List   public class SortCityList                  Here are the 10 most populated cities in the world and we want to sort it by        name  as reported by Time  Osaka  Japan      Mexico City  Mexico             Beijing  China      S  o Paulo  Brazil      Mumbai  India      Shanghai         China      Delhi  India      Tokyo  Japan              public static void main String   args            List lt String gt  cities   Arrays asList  Osaka    Mexico City    S  o Paulo    Mumbai    Shanghai    Delhi                    Tokyo            System out println  Before Sorting List is -            System out println cities           System out println  --------------------------------             System out println  After Use of List sort String CASE INSENSITIVE ORDER   amp  Sorting List is -            cities sort String CASE INSENSITIVE ORDER           System out println cities           System out println  --------------------------------            System out println  After Use of List sort Comparator naturalOrder     amp  Sorting List is -            cities sort Comparator naturalOrder             System out println cities

User · Answer

Use sort   method to sort the list as below   List list   new ArrayList       add elements to the list  Comparator comparator   new SomeComparator     Collections sort list  comparator     For reference see the link  http   tutorials jenkov com java-collections sorting html

User · Answer

You want the SortedSet implementations  namely TreeSet

User · Answer

If you just want to sort a list  use any kind of List and use Collections sort    If you want to make sure elements in the list are unique and always sorted  use a SortedSet

User · Answer

The most efficient way to implement a sorted list like you want would be to implement an indexable skiplist as in here  Wikipedia  Indexable skiplist   It would allow to have inserts removals in O log n   and would allow to have indexed access at the same time  And it would also allow duplicates   Skiplist is a pretty interesting and  I would say  underrated data structure  Unfortunately there is no indexed skiplist implementation in Java base library  but you can use one of open source implementations or implement it yourself  There are regular Skiplist implementations like ConcurrentSkipListSet and ConcurrentSkipListMap

User · Answer

Use Google Guava s TreeMultiset class  Guava has a spectacular collections API   One problem with providing an implementation of List that maintains sorted order is the promise made in the JavaDocs of the add   method

User · Answer

There are a few options  I d suggest TreeSet if you don t want duplicates and the objects you re inserting are comparable   You can also use the static methods of the Collections class to do this   See Collections sort java util List  and TreeSet for more info

User · Answer

Sorting an ArrayList according to user defined criteria   Model Class   class Student           int rollno        String name  address         public Student int rollno  String name  String address                    this rollno   rollno            this name   name            this address   address                   public String toString                     return this rollno         this name         this address                 Sorting Class   class Sortbyroll implements Comparator lt Student gt                    public int compare Student a  Student b                    return a rollno - b rollno                 Main Class   class Main           public static void main  String   args                    ArrayList lt Student gt  ar   new ArrayList lt Student gt               ar add new Student 111   bbbb    london               ar add new Student 131   aaaa    nyc               ar add new Student 121   cccc    jaipur                System out println  Unsorted              for  int i 0  i lt ar size    i                  System out println ar get i               Collections sort ar  new Sortbyroll                System out println   nSorted by rollno              for  int i 0  i lt ar size    i                  System out println ar get i                   Output   Unsorted  111 bbbb london  131 aaaa nyc  121 cccc jaipur   Sorted by rollno  111 bbbb london  121 cccc jaipur  131 aaaa nyc

User · Answer

Using LambdaJ  You can try solving these tasks with LambdaJ if you are using prior versions to java 8  You can find it here  http   code google com p lambdaj   Here you have an example   Sort Iterative  List lt Person gt  sortedByAgePersons   new ArrayList lt Person gt  persons   Collections sort sortedByAgePersons  new Comparator lt Person gt              public int compare Person p1  Person p2               return Integer valueOf p1 getAge    compareTo p2 getAge                      Sort with LambdaJ  List lt Person gt  sortedByAgePersons   sort persons  on Person class  getAge        Of course  having this kind of beauty impacts in the performance  an average of 2 times   but can you find a more readable code   Sort with java 8 using lambda expression  Collections sort persons   p1  p2  - gt  p1 getAge   compareTo p2 getAge        or persons sort  p1  p2  - gt  p1 getAge   compareTo p2 getAge

User · Answer

TreeMap and TreeSet will give you an iteration over the contents in sorted order  Or you could use an ArrayList and use Collections sort   to sort it  All those classes are in java util

User · Answer

The problem with PriorityQueue is that it s backed up by an simple array  and the logic that gets the elements in order is done by the  queue 2 n 1  and queue 2  n 1    thingie  It works great if you just pull from head  but makes it useless if you are trying to call the  toArray on it at some point    I go around this problem by using com google common collect TreeMultimap  but I supply a custom Comparator for the values  wrapped in an Ordering  that never returns 0    ex  for Double   private static final Ordering lt Double gt  NoEqualOrder   Ordering from new Comparator lt Double gt            Override     public int compare Double d1  Double d2                if  d1  lt  d2                return -1                    else               return 1                        This way I get the values in order when I call  toArray    and also have duplicates

User · Answer

Use TreeSet which gives elements in sorted order  OR use Collection sort   for external sorting with Comparator

User · Answer

This comes very late  but there is a class in the JDK just for the purpose of having a sorted list  It is named  somewhat out of order with the other Sorted  interfaces   java util PriorityQueue   It can sort either Comparable lt   gt s or using a Comparator   The difference with a List sorted using Collections sort      is that this will maintain a partial order at all times  with O log n   insertion performance  by using a heap data structure  whereas inserting in a sorted ArrayList will be O n   i e   using binary search and move    However  unlike a List  PriorityQueue does not support indexed access  get 5    the only way to access items in a heap is to take them out  one at a time  thus the name PriorityQueue

User · Answer

Sorting an ArrayList according to user defined criteria   Model Class   class Student           int rollno        String name  address         public Student int rollno  String name  String address                    this rollno   rollno            this name   name            this address   address                   public String toString                     return this rollno         this name         this address                 Sorting Class   class Sortbyroll implements Comparator lt Student gt                    public int compare Student a  Student b                    return a rollno - b rollno                 Main Class   class Main           public static void main  String   args                    ArrayList lt Student gt  ar   new ArrayList lt Student gt               ar add new Student 111   bbbb    london               ar add new Student 131   aaaa    nyc               ar add new Student 121   cccc    jaipur                System out println  Unsorted              for  int i 0  i lt ar size    i                  System out println ar get i               Collections sort ar  new Sortbyroll                System out println   nSorted by rollno              for  int i 0  i lt ar size    i                  System out println ar get i                   Output   Unsorted  111 bbbb london  131 aaaa nyc  121 cccc jaipur   Sorted by rollno  111 bbbb london  121 cccc jaipur  131 aaaa nyc

User · Answer

What you want is a binary search tree  It maintains sorted order while offering logarithmic access for searches  removals and insertions  unless you have a degenerated tree - then it s linear   It is quite easy to implement and you even can make it implement the List interface  but then the index-access gets complicated   Second approach is to have an ArrayList and then a bubble sort implementation  Because you are inserting or removing one element at a time  the access times for insertions and removals are linear  Searches are logarithmic and index access constant  times can get different for LinkedList   The only code you need is 5  maybe 6 lines of bubble sort

[java] Sorted collection in Java

Examples related to java

Examples related to sorting

Examples related to collections