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.
This question is related to
java
sorting
collections
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.
import java.util.TreeSet;
public class Ass3 {
TreeSet<String>str=new TreeSet<String>();
str.add("dog");
str.add("doonkey");
str.add("rat");
str.add("rabbit");
str.add("elephant");
System.out.println(str);
}
What I have done is implement List having a internal instance with all the methods delegated.
public class ContactList implements List<Contact>, Serializable {
private static final long serialVersionUID = -1862666454644475565L;
private final List<Contact> list;
public ContactList() {
super();
this.list = new ArrayList<Contact>();
}
public ContactList(List<Contact> list) {
super();
//copy and order list
List<Contact>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<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<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<Contact> listIterator() {
return (new ArrayList<Contact>(list)).listIterator();
}
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
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.
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.
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
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.
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<Student>
{
public int compare(Student a, Student b)
{
return a.rollno - b.rollno;
}
}
Main Class
class Main
{
public static void main (String[] args)
{
ArrayList<Student> ar = new ArrayList<Student>();
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<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<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
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.
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
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.
What I have done is implement List having a internal instance with all the methods delegated.
public class ContactList implements List<Contact>, Serializable {
private static final long serialVersionUID = -1862666454644475565L;
private final List<Contact> list;
public ContactList() {
super();
this.list = new ArrayList<Contact>();
}
public ContactList(List<Contact> list) {
super();
//copy and order list
List<Contact>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<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<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<Contact> listIterator() {
return (new ArrayList<Contact>(list)).listIterator();
}
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.
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<?>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).
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<Student>
{
public int compare(Student a, Student b)
{
return a.rollno - b.rollno;
}
}
Main Class
class Main
{
public static void main (String[] args)
{
ArrayList<Student> ar = new ArrayList<Student>();
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<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<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
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
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
Use TreeSet which gives elements in sorted order. OR use Collection.sort() for external sorting with Comparator().
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.
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
Use TreeSet which gives elements in sorted order. OR use Collection.sort() for external sorting with Comparator().
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.
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<Person> sortedByAgePersons = new ArrayList<Person>(persons);
Collections.sort(sortedByAgePersons, new Comparator<Person>() {
public int compare(Person p1, Person p2) {
return Integer.valueOf(p1.getAge()).compareTo(p2.getAge());
}
});
Sort with LambdaJ
List<Person> 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?
Collections.sort(persons, (p1, p2) -> p1.getAge().compareTo(p2.getAge()));
//or
persons.sort((p1, p2) -> p1.getAge().compareTo(p2.getAge()));
import java.util.TreeSet;
public class Ass3 {
TreeSet<String>str=new TreeSet<String>();
str.add("dog");
str.add("doonkey");
str.add("rat");
str.add("rabbit");
str.add("elephant");
System.out.println(str);
}
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.
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.
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
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<Person> sortedByAgePersons = new ArrayList<Person>(persons);
Collections.sort(sortedByAgePersons, new Comparator<Person>() {
public int compare(Person p1, Person p2) {
return Integer.valueOf(p1.getAge()).compareTo(p2.getAge());
}
});
Sort with LambdaJ
List<Person> 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?
Collections.sort(persons, (p1, p2) -> p1.getAge().compareTo(p2.getAge()));
//or
persons.sort((p1, p2) -> p1.getAge().compareTo(p2.getAge()));
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.
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
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.
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.
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.
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<Double> NoEqualOrder = Ordering.from(new Comparator<Double>() {
@Override
public int compare(Double d1, Double d2)
{
if (d1 < d2) {
return -1;
}
else {
return 1;
}
}
});
This way I get the values in order when I call .toArray(), and also have duplicates.
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.
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<String> 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) & 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()) & Sorting List is:-");
cities.sort(Comparator.naturalOrder());
System.out.println(cities);
}
}
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.
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
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<String> 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) & 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()) & Sorting List is:-");
cities.sort(Comparator.naturalOrder());
System.out.println(cities);
}
}
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<Double> NoEqualOrder = Ordering.from(new Comparator<Double>() {
@Override
public int compare(Double d1, Double d2)
{
if (d1 < d2) {
return -1;
}
else {
return 1;
}
}
});
This way I get the values in order when I call .toArray(), and also have duplicates.
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.
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
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<?>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).
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.
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.
Source: Stackoverflow.com