Why there is no SortedList in Java?

up vote56down votefavorite 21

In Java there are SortedSet and SortedMap. Both belongs to collections and provided a sorted way to access the elements. However, there is no SortedList in Java, in my understanding. You can usejava.util.Collections.sort() to sort a list. Any idea why it is designed like that? The Sun has provided the TreeSet and the TreeMap and but no TreeList. They provided a utilityCollections.sort() to sort the List. When they provided the Sorted Map and Set, what is the reason they didn't provide the Sorted List.? Is there any specific reason behind it.? I am preparing for SCJP, so while going through the Generics and Collections, I got this doubt. can anyone clarify. java sorting collections share|improve this question edited Nov 12 '12 at 11:36 MC Emperor 2,05511234 asked Jan 4 '12 at 10:35 Jijoy 1,29161735

1   Does stackoverflow.com/questions/416266/sorted-collection-in-java help you? –  Nico Haase Jan 4 '12 at 10:38 2   so what is your expected result when inserting an element in the middle of the list? –  bestsss Jan 4 '12 at 10:49 @bestsss It would be fully possible to have a SortedList class which does not implement the java.util.List interface. Read the question as an inquiry why there is no data structure which supports the requested functionality. Don't get distracted by insignificant details such as naming. –  Alderath Jan 4 '12 at 12:17 @Alderath, the usual structure for this is a tree (red/black, avl or btree) w/ extra prev/next links to support ordering. I do use similar structure red/black w/ prev/next links. It's a quite niche use, though. The tree can be traversed both ordered and insert order, has O(logn) find/contains but get(int) is O(n). Given the fact its niche applicability I'd assume it was left to the developers to implement one if they need. –  bestsss Jan 4 '12 at 17:22  add comment

6 Answers

activeoldestvotes

up vote115down voteaccepted

List iterators guarantee first and foremost that you get the list's elements in the internal order of the list (aka. insertion order). More specifically it is in the order you've inserted the elements or on how you've manipulated the list. Sorting can be seen as a manipulation of the data structure, and there are several ways to sort the list. I'll order the ways in the order of usefulness as I personally see it: 1. Consider using a Sets or Bags instead I put this option at the top because this is what you normally want to do anyway. A sorted setautomatically sorts the collection at insertion, meaning that you don't need to manually sort it. If you are sure you don't need to worry about (or have) duplicate elements then you can use the TreeSetinstead. It implements SortedSet and NavigableSet interfaces and works as you'd probably expect: TreeSet<String> set = new TreeSet<String>(); set.add("lol"); set.add("cat"); // automatically sorts natural order when adding for (String s : set) { System.out.println(s); } // Prints out "cat" and "lol" If you don't want the natural ordering you can use the constructor parameter that takes aComparator. Alternatively you can use Multisets (also known as Bags), that is a Set that allows duplicate elements, instead and there are third party implementations of them. Most notably from the Guava libraries there is a TreeMultiset, that works a lot like the TreeSet. 2. Sort your list with Collections.sort() You can sort your list with the java.util.Collections.sort() method. Here is a code sample on how: List<String> strings = new ArrayList<String>() strings.add("lol"); strings.add("cat"); Collections.sort(strings); for (String s : strings) { System.out.println(s); } // Prints out "cat" and "lol" 3. Wrap your list with java.util.PriorityQueue Though there is no sorted list in Java there is however a sorted queue which would probably work just as well for you. It is the java.util.PriorityQueue class. Nico Haase linked in the comments to a related question that also answers this. In a sorted collection you most likely don't want to manipulate the internal data structure which is why PriorityQueue doesn't implement the List interface (because that would give you direct access to it's elements). Note: The PriorityQueue class implements the Iterable and Collection interfaces so it can be iterated as usual. However the iterator is not guaranteed to return elements in the sorted order. Instead (as Alderath points out in the comments) you need to poll() the queue until empty. Note that you can convert a list to a priority queue via the constructor that takes any collection: List<String> strings = new ArrayList<String>() strings.add("lol"); strings.add("cat"); PriorityQueue<String> sortedStrings = new PriorityQueue(strings); while(!sortedStrings.isEmpty()) { System.out.println(sortedStrings.poll()); } // Prints out "cat" and "lol" 4. Write your own SortedList class You can write your own List class that sorts each time you add a new element. This can get rather computation heavy depending on your implementation, and is kind of pointless unless you want to do it as an exercise. I mention pointless because of two main reasons: It breaks the promises that List interface has, because the add methods should ensure that the element will reside in the index that the user specifies. Why reinvent the wheel? You should be using the TreeSet or Multisets instead as pointed out above. Here is some code sample to get you started though, it uses the AbstractList abstract class: public class SortedList<E> extends AbstractList<E> { private ArrayList<E> internalList = new ArrayList<E>(); // Note that add(E e) in AbstractList is calling this one @Override public void add(int position, E e) { internalList.add(e); Collections.sort(internalList, null); } @Override public E get(int i) { return internalList.get(i); } @Override public int size() { return internalList.size(); } } Note that if you haven't overridden the methods you need, then the default implementations from AbstractList will throw UnsupportedOperationExceptions. share|improve this answer edited Jul 12 at 11:59 m4tx 1,4281729 answered Jan 4 '12 at 10:41 Spoike 27.8k2991115

5   +1. Imo, this is more constructive than the top voted answer. It comes with two minor downsides though. The PriorityQueue does not support random access. You cannot do peek(elementIndex). So you cannot do e.g.Integer maxVal = prioQueue.peek(prioQueue.size() - 1);. Secondly if you're intending to use the PriorityQueue simply as a sorted list, it will sound less intuitive to see PriorityQueue in the code than it would have been to see SortedList, if such a data structure existed. –  Alderath Jan 4 '12 at 12:18 3   And, after looking at the other question which someone linked in the comments, another big disadvantageis that the iterator of PriorityQueue is not guaranteed to return elements in any specific order. So, unless I am overlooking something, the only way to e.g. print all objects in the PriorityQueue in order is to repeatedly poll() the queue until it is empty. To me, this feels borderline retarted. To print the objects in a PriorityQueue twice, you'd first have to copy the PriorityQueue and then poll() all objects from the original PriorityQueue and then pol()l all objects from the copy. –  Alderath Jan 4 '12 at 12:49  Hmm... looks like you're right Alderath. You can't use the iterator of PriorityQueue to get the elements in expected order. Looks like I have to edit my answer. –  Spoike Jan 4 '12 at 13:10 Sorted list is implemented via tree, otherwise it's just way too costy –  bestsss Jan 4 '12 at 17:24 2   Priority queue is just a heap, you can access only the top, imo it does not belong to the answer of the question. –  bestsss Jan 4 '12 at 17:25 show 1 more comment