By Jijoy


2012-01-04 10:35:53 8 Comments

In Java there are the SortedSet and SortedMap interfaces. Both belong to Java's standard Collections framework and provide a sorted way to access the elements.

However, in my understanding there is no SortedList in Java. You can use java.util.Collections.sort() to sort a list.

Any idea why it is designed like that?

11 comments

@Marcono1234 2019-07-13 15:40:09

In case you are looking for a way to sort elements, but also be able to access them by index in an efficient way, you can do the following:

  1. Use a random access list for storage (e.g. ArrayList)
  2. Make sure it is always sorted

Then to add or remove an element you can use Collections.binarySearch to get the insertion / removal index. Since your list implements random access, you can efficiently modify the list with the determined index.

Example:

/**
 * @deprecated
 *      Only for demonstration purposes. Implementation is incomplete and does not 
 *      handle invalid arguments.
 */
@Deprecated
public class SortingList<E extends Comparable<E>> {
    private ArrayList<E> delegate;

    public SortingList() {
        delegate = new ArrayList<>();
    }

    public void add(E e) {
        int insertionIndex = Collections.binarySearch(delegate, e);

        // < 0 if element is not in the list, see Collections.binarySearch
        if (insertionIndex < 0) {
            insertionIndex = -(insertionIndex + 1);
        }
        else {
            // Insertion index is index of existing element, to add new element 
            // behind it increase index
            insertionIndex++;
        }

        delegate.add(insertionIndex, e);
    }

    public void remove(E e) {
        int index = Collections.binarySearch(delegate, e);
        delegate.remove(index);
    }

    public E get(int index) {
        return delegate.get(index);
    }
}

@swpalmer 2015-05-29 23:58:20

JavaFX SortedList

Though it took a while, Java 8 does have a sorted List. http://docs.oracle.com/javase/8/javafx/api/javafx/collections/transformation/SortedList.html

As you can see in the javadocs, it is part of the JavaFX collections, intended to provide a sorted view on an ObservableList.

Update: Note that with Java 11, the JavaFX toolkit has moved outside the JDK and is now a separate library. JavaFX 11 is available as a downloadable SDK or from MavenCentral. See https://openjfx.io

@Erel Segal-Halevi 2017-10-28 18:54:57

Unfortunately, this SortedList does not work like a usual list - for example, it does not have a default constructor (you have to construct it using an ObservableList, whatever that means...)

@COBRA.cH 2018-03-23 13:28:53

The SortedList from JavaFX clearly is for the use of GUI-Components and because of the overhead NOT suited for just having a List of sorted objects. Also it would mean to reference the whole FX Module even if the GUI is not used in the project.

@swpalmer 2018-03-24 16:44:32

@COBRA.cH Yes, that is true. A more performant Sorted List could probably be a thin wrapper around a TreeMap, where an integer is used to count duplicates of the key. You could also use a TreeSet with a comparator that never returns 0.

@Basil Bourque 2018-07-30 04:59:23

Why the down-votes? The question starts with a presupposition that there is no sorted list in the JDK libraries. This Answer corrects that assumption. Whether you like or disike the implementation of this particular sorted list is not a reason to down-vote. This Answer does not recommend the class, merely points out its existence.

@SJuan76 2012-01-04 10:39:42

Since all lists are already "sorted" by the order the items were added (FIFO ordering), you can "resort" them with another order, including the natural ordering of elements, using java.util.Collections.sort().

EDIT:

Lists as data structures are based in what is interesting is the ordering in which the items where inserted.

Sets do not have that information.

If you want to order by adding time, use List. If you want to order by other criteria, use SortedSet.

@bestsss 2012-01-04 10:48:10

Set doesn't allow duplicates

@Alderath 2012-01-04 11:48:52

I do not think this is a very good answer. Sure, lists in the java API do have an a specific ordering determined by when/how the items were inserted. However, the existence of lists ordered in a manner which depends on insertion method/time does not prevent having other data structures in which order is determined in another way (e.g. by a Comparator). Basically, the OP is asking why there is not a data structure equivalent to a SortedSet with the exception that the data structure should allow for multiple occurences of elements which are equal.

@Alderath 2012-01-04 11:52:38

So my follow up question would be: "Why is there no data structure which works like a SortedSet, but which can contain multiple equal elements?" (and please don't answer "because Sets can only contain one element")

@Janus Troelsen 2012-06-24 00:41:51

@Alderath: See stackoverflow.com/questions/416266/sorted-collection-in-java . In short: Use Guava's TreeMultiset

@usr-local-ΕΨΗΕΛΩΝ 2015-11-02 09:36:41

I think the sentence lists are already sorted by its order is a bit misleading. Yes, Lists have a default FIFO ordering (the order the items were added), but reading that sentence I was thinking about the natural ordering of elements, which is kinda different thing. I will propose an edit

@Koray Tugay 2017-08-04 04:53:57

Lists are NOT "sorted", even if you put the "sorted" in double quotes. They are ordered.

@Spoike 2012-01-04 10:41:01

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 Set or Bag collections instead

NOTE: I put this option at the top because this is what you normally want to do anyway.

A sorted set automatically sorts the collection at insertion, meaning that it does the sorting while you add elements into the collection. It also means you don't need to manually sort it.

Furthermore if you are sure that you don't need to worry about (or have) duplicate elements then you can use the TreeSet<T> instead. It implements SortedSet and NavigableSet interfaces and works as you'd probably expect from a list:

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 a Comparator<T>.

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()

As mentioned above, sorting of Lists is a manipulation of the data structure. So for situations where you need "one source of truth" that will be sorted in a variety of ways then sorting it manually is the way to go.

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"

Using comparators

One clear benefit is that you may use Comparator in the sort method. Java also provides some implementations for the Comparator such as the Collator which is useful for locale sensitive sorting strings. Here is one example:

Collator usCollator = Collator.getInstance(Locale.US);
usCollator.setStrength(Collator.PRIMARY); // ignores casing

Collections.sort(strings, usCollator);

Sorting in concurrent environments

Do note though that using the sort method is not friendly in concurrent environments, since the collection instance will be manipulated, and you should consider using immutable collections instead. This is something Guava provides in the Ordering class and is a simple one-liner:

List<string> sorted = Ordering.natural().sortedCopy(strings);

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 its elements).

Caveat on the PriorityQueue iterator

The PriorityQueue class implements the Iterable<E> and Collection<E> 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

NOTE: You shouldn't have to do this.

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 pointless, unless you want to do it as an exercise, because of two main reasons:

  1. It breaks the contract that List<E> interface has because the add methods should ensure that the element will reside in the index that the user specifies.
  2. Why reinvent the wheel? You should be using the TreeSet or Multisets instead as pointed out in the first point above.

However, if you want to do it as an exercise here is a code sample to get you started, 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.

@Alderath 2012-01-04 12:18:31

+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 2012-01-04 12:49:06

And, after looking at the other question which someone linked in the comments, another big disadvantage is 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.

@Spoike 2012-01-04 13:10:19

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.

@bestsss 2012-01-04 17:24:25

Sorted list is implemented via tree, otherwise it's just way too costy

@bestsss 2012-01-04 17:25:08

Priority queue is just a heap, you can access only the top, imo it does not belong to the answer of the question.

@Mike 'Pomax' Kamermans 2013-06-12 14:27:21

Also worth noting is that Collections.sort() even lets you define the compare function that is used to sort, by using a Comparator object.

@user2223059 2016-02-09 19:38:50

I would argue that there is a need for some kind of sorted, indexed collection. I'm working on an application, and I need a data collection that is accessible via an index number, but maintains a very specific order. I don't want to have to use sort() or comparators all the time. So yeah, I'm probably going to create a custom collection that just inherits from Collection, rather than list, that fulfills this function.

@Caitlin 2016-10-07 17:25:32

The TreeMultiset allows for multiples in a really weird way. If you have two objects that have the same key, instead of actually inserting all of the objects into the Multiset, it just keeps track of the count that match that key. This is fine if you are using primitives. But if you are using objects, and plan on using other pieces of the object, it won't return the objects expected.

@juanmf 2017-02-04 18:46:17

@Spoike ` because the add methods should ensure that the element will reside in the index that the user specifies` actually,it adds at the end, you can specify index in a Map, with put(). Am I confused?

@Spoike 2017-02-07 14:34:32

@juanmf The key (or index) for a Map is not the same thing as the index for a List. Using put() there is no way for sure that putting something in a lower number and something in a higher number will come in the order you want when you iterate on the entrySet of the map (i.e. unless you sort the entrySet by the key).

@Torque 2019-04-05 07:37:17

A huge downside to all of these suggestions is the missing .sub*-function that SourtedMap and SortedSet provide, and that at least in my experience is the most needed feature.

@Marcono1234 2019-07-13 15:25:36

@Spoike, the own implementation of a SortedList can be written more efficiently. Since a random access list is used (ArrayList) and you know that it is already sorted before adding a new item, you can use Collections.binarySearch to get the index where the new item should be inserted.

@Premraj 2015-12-21 22:58:24

Set and Map are non-linear data structure. List is linear data structure.

enter image description here


The tree data structure SortedSet and SortedMap interfaces implements TreeSet and TreeMap respectively using used Red-Black tree implementation algorithm. So it ensure that there are no duplicated items (or keys in case of Map).

  • List is already maintains an ordered collection and index-based data structure, trees are no index-based data structures.
  • Tree by definition cannot contain duplicates.
  • In List we can have duplicates, so there is no TreeList(i.e. no SortedList).
  • List maintains elements in insertion order. So if we want to sort the list we have to use java.util.Collections.sort(). It sorts the specified list into ascending order, according to the natural ordering of its elements.

@Amagi82 2015-06-10 19:49:49

For any newcomers, as of April 2015, Android now has a SortedList class in the support library, designed specifically to work with RecyclerView. Here's the blog post about it.

@Matthew 2015-10-30 03:49:41

Worth noting that at the time of this comment Androids SortedList lacks support for onItemMoved() functionality with RecyclerView. Writing my own SortedList which is less efficient is what I had to do to get around the limitations.

@Vitaly Sazanovich 2014-01-27 14:32:07

Consider using indexed-tree-map . It's an enhanced JDK's TreeSet that provides access to element by index and finding the index of an element without iteration or hidden underlying lists that back up the tree. The algorithm is based on updating weights of changing nodes every time there is a change.

@Syam 2012-07-23 06:34:43

First line in the List API says it is an ordered collection (also known as a sequence). If you sort the list you can't maintain the order, so there is no TreeList in Java.
As API says Java List got inspired from Sequence and see the sequence properties http://en.wikipedia.org/wiki/Sequence_(mathematics)

It doesn't mean that you can't sort the list, but Java strict to his definition and doesn't provide sorted versions of lists by default.

@Ingo 2012-01-04 13:50:44

Another point is the time complexity of insert operations. For a list insert, one expects a complexity of O(1). But this could not be guaranteed with a sorted list.

And the most important point is that lists assume nothing about their elements. For example, you can make lists of things that do not implement equals or compare.

@bestsss 2012-01-04 17:25:50

you can have list w/ O(logn) insert/delete/find/contains but not w/ get(int).

@Alderath 2012-09-28 15:13:30

The last point isn't really a good explanation. You can make a SortedSet of things that do not implement Comparable. See this TreeSet constructor.

@Ingo 2012-09-28 17:15:49

@Alderath - maybe my wording was too weak. Yet the observation holds that elements of Sets and keys of Trees must be comparable at least for equality, whereas list elements need not. Whether the ordering/equality relation for Sets and Trees is implemented in a Comparator or elsewhere is immaterial - but you need one.

@Matt Quigley 2017-08-11 04:58:27

Lists do not guarantee O(1) insertion, they guarantee O(1) access. bigocheatsheet.com

@Betlista 2018-04-25 12:28:06

@MattQuigley do they? list.get(5) is not in O(1) for linked list...

@Matt Quigley 2018-04-26 20:59:23

@Betlista you're right! I can't update my comment, but the Java List interface doesn't guarantee any performance specifications on its methods.

@Costi Ciudatu 2012-01-04 10:47:38

Think of it like this: the List interface has methods like add(int index, E element), set(int index, E element). The contract is that once you added an element at position X you will find it there unless you add or remove elements before it.

If any list implementation would store elements in some order other than based on the index, the above list methods would make no sense.

@Michael Borgwardt 2012-01-04 10:44:59

Because the concept of a List is incompatible with the concept of an automatically sorted collection. The point of a List is that after calling list.add(7, elem), a call to list.get(7) will return elem. With an auto-sorted list, the element could end up in an arbitrary position.

Related Questions

Sponsored Content

84 Answered Questions

[SOLVED] Is Java "pass-by-reference" or "pass-by-value"?

55 Answered Questions

[SOLVED] Creating a memory leak with Java

58 Answered Questions

[SOLVED] How do I read / convert an InputStream into a String in Java?

22 Answered Questions

40 Answered Questions

[SOLVED] How do I efficiently iterate over each entry in a Java Map?

9 Answered Questions

[SOLVED] Why is subtracting these two times (in 1927) giving a strange result?

  • 2011-07-27 08:15:58
  • Freewind
  • 616092 View
  • 6538 Score
  • 9 Answer
  • Tags:   java date timezone

11 Answered Questions

31 Answered Questions

[SOLVED] When to use LinkedList over ArrayList in Java?

16 Answered Questions

[SOLVED] Why is char[] preferred over String for passwords?

15 Answered Questions

[SOLVED] Efficiency of Java "Double Brace Initialization"?

Sponsored Content