What is the difference between an ordered and a sorted collection?

Question

Is there any difference between a sorted and an ordered collection?

Answer 1

An ordered collection maintains the order of the elements based on the sequence you put stuff into/remove them from the collection.

A sorted collection keeps the elements sorted based on a sort criteria.

Answer 2

An ordered collection means that the elements of the collection have a specific order. The order is independent of the value. A List is an example.

A sorted collection means that not only does the collection have order, but the order depends on the value of the element. A SortedSet is an example.

In contrast, a collection without any order can maintain the elements in any order. A Set is an example.

Answer 3

Java uses "ordered collection" to mean a collection such as List, where (unlike HashSet), the collection remembers what order the elements are supposed to be in. So elements can be added to the collection at a particular "place" in the order.

Java uses "sorted collection" to mean a collection such as SortedSet, where (unlike List), the order that the iterator traverses the collection is in accordance with a specified Comparator or the natural order of the elements.

Answer 4

Sorted would imply ordering according to an implementation of Comparable or Comparator. Ordered would imply that it is following the insertion order or some other definition of order that is consistent and defined, but otherwise arbitrary.

So a sorted list of strings would be sorted according to the String.compareTo method. A list might contain a list of strings inserted in arbitrary order, but that order will always remain the same.

Of course there are methods on the Collections class to sort a list.

Answer 5

Yes, though the concepts are similar.

List is an ordered collection: each element has an index, which forms an ordering of the elements, but not usually related to any property of the elements themselves.

SortedMap and SortedSet are sorted collections, which means that iteration through the collection will happen in a sequence derived from the elements themselves. For example, if you have a SortedSet<String> then the Strings will be sorted according to the lexicographical sort order.

An ordered Collection can be sorted but doesn't have to be (e.g. after using Collections.sort()) when the external ordering is identical with the elements' sort order. A sorted collection is always implicitly ordered (i.e. there is always a "first" element, and it's always the same as long as you don't add another, smaller one).