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.
Sorted collection in Java
Admin
1
Viewed 211723
21 Answers
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).
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.
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
Why don't make it yourself?
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Random;
class SortedList<E extends Comparable<E>> extends ArrayList<E> {
@Override
public boolean add(E e) {
int i = Collections.binarySearch(this, e);
if (i < 0) i = ~i;
super.add(i, e);
return true;
} // add(E e)
@Override
public void add(int index, E element) {
this.add(element);
} // add(int, E)
@Override
public boolean addAll(Collection<? extends E> c) {
int oldSize = this.size();
for (E element : c) this.add(element);
return oldSize != this.size();
} // addAll(Collection<? extends E>)
@Override
public boolean addAll(int index, Collection<? extends E> c) {
int oldSize = this.size();
Iterator<? extends E> it = c.iterator();
for (int i = 0; i < index; ++i) it.next();
while (it.hasNext()) this.add(it.next());
return oldSize != this.size();
} // addAll(Collection<? extends E>)
@Override
public E set(int index, E element) {
E ret = this.get(index);
this.remove(index);
this.add(element);
return ret;
} // set(int, E)
} // SortedList<E> Class
public class Solution {
public static void main(String[] args) {
Random r = new Random(1);
List<Integer> sortedList = new SortedList<>();
List<Integer> unsortedList = new ArrayList<>();
for (int i = 0; i < 50; ++i) {
int next = r.nextInt(1000);
sortedList.add(next);
unsortedList.add(next);
} // for (int i = 0; i < 50; ++i)
System.out.println("unsortedList:");
System.out.println(unsortedList);
System.out.println("\nsortedList:");
System.out.println(sortedList);
sortedList.clear();
sortedList.addAll(unsortedList);
System.out.println("\ntest for addAll(Collection) method:");
System.out.println(sortedList);
sortedList.clear();
sortedList.addAll(30, unsortedList);
System.out.println("\ntest for addAll(int, Collection) method:");
System.out.println(sortedList);
sortedList.set(0, 999);
System.out.println("\ntest for set(int, E) method:");
System.out.println(sortedList);
} // main(String[])
} // Solution Class
output:
unsortedList:
[985, 588, 847, 313, 254, 904, 434, 606, 978, 748, 569, 473, 317, 263, 562, 234, 592, 262, 596, 189, 376, 332, 310, 99, 674, 959, 298, 153, 437, 302, 205, 854, 800, 6, 363, 955, 689, 820, 75, 834, 415, 660, 477, 737, 477, 592, 220, 888, 500, 357]
sortedList:
[6, 75, 99, 153, 189, 205, 220, 234, 254, 262, 263, 298, 302, 310, 313, 317, 332, 357, 363, 376, 415, 434, 437, 473, 477, 477, 500, 562, 569, 588, 592, 592, 596, 606, 660, 674, 689, 737, 748, 800, 820, 834, 847, 854, 888, 904, 955, 959, 978, 985]
test for addAll(Collection) method:
[6, 75, 99, 153, 189, 205, 220, 234, 254, 262, 263, 298, 302, 310, 313, 317, 332, 357, 363, 376, 415, 434, 437, 473, 477, 477, 500, 562, 569, 588, 592, 592, 596, 606, 660, 674, 689, 737, 748, 800, 820, 834, 847, 854, 888, 904, 955, 959, 978, 985]
test for addAll(int, Collection) method:
[6, 75, 205, 220, 357, 363, 415, 477, 477, 500, 592, 660, 689, 737, 800, 820, 834, 854, 888, 955]
test for set(int, E) method:
[75, 205, 220, 357, 363, 415, 477, 477, 500, 592, 660, 689, 737, 800, 820, 834, 854, 888, 955, 999]
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);
}
}
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
Related