1. Introduction
Java provides a rich collection framework with various interfaces and classes that cater to diverse data structure needs. However, it doesn’t provide a built-in implementation of sorted lists. In this article, we look into the reasons behind this absence, comparing the concepts of sorting on insertion and sorting on demand.
We also discuss how sorting on insertion can potentially break the contract of the List interface, and we explore alternative ways to achieve sorted behavior.
2. Sorting on Insertion and Sorting on Demand
To understand why sorted lists aren’t present in Java, we must first differentiate between sorting on insertion and sorting on demand.
2.1. Sorting on Insertion
Sorting on insertion involves rearranging elements immediately at the time of insertion, ensuring a sorted order with each addition. Some data structures do behave this way. Usually, their implementation is based on a tree structure, most notably, TreeSet and TreeMap.
The main advantage of a sorting-on-insertion implementation is the efficiency of reading data from such a structure. Writing data is more costly because we need to find the right place in the structure and, sometimes, even rearrange existing data.
This cost may be much smaller than that of sorting the whole unsorted collection on every read. However, sorting on insertion with multiple sorting conditions is much more complex and involves keeping track of multiple index tree structures, making saving even more complex and costly.
2.2. Sorting on Demand
On the other hand, sorting on demand defers the sorting operation until explicitly requested by the user. Sorted reads are costly because we must sort the whole collection every time.
On the upside, saving data is very cheap, and the underlying data structure can be much simpler — for example, an array backing the ArrayList. Moreover, we can decide to sort by different conditions each time or even not to sort at all.
3. Why Sorting on Insertion Breaks the List Contract
Sorting on insertion would break the contract of the List interface. The contract of the List interface specifies that elements should be maintained in the order they were inserted, allowing for duplicates. Sorting on insertion would violate this contract by rearranging the elements. This order is important for many list operations and algorithms that rely on the order of elements.
By sorting the list on every insertion, we’d change the order of elements and potentially disrupt the expected behavior of other methods defined in the List interface.
4. Implementing Sorting on Insertion
In most cases, we shouldn’t implement our own data structures to achieve sorting on insertion. There are already collections that do it well, although they’re based on tree data structure, not linear lists.
4.1. Using TreeSet With Natural Order
If we’re happy with the natural order and want to ignore duplicates, we can create a TreeSet instance with a default constructor:
TreeSet<Integer> sortedSet = new TreeSet<>();
sortedSet.add(5);
sortedSet.add(2);
sortedSet.add(8);
sortedSet.add(1);
System.out.println(sortedSet); // Output: [1, 2, 5, 8]
4.2. Using TreeSet With a Custom Order
We can also use a custom Comparator to achieve the custom order. Let’s say we have a set of strings, and we want to sort them by their last letter:
Comparator<String> customComparator = Comparator.comparing(str -> str.charAt(str.length() - 1));
TreeSet<String> sortedSet = new TreeSet<>(customComparator);
sortedSet.add("Canada");
sortedSet.add("Germany");
sortedSet.add("Japan");
sortedSet.add("Sweden");
sortedSet.add("India");
System.out.println(sortedSet); // Output: [India, Canada, Sweden, Japan, Germany]
5. Implementing Sorting on Demand
If we want to use the List interface, we can implement sorting on demand. We can do that in two ways: by sorting in place or by creating a new sorted list.
5.1. Sorting in Place
To sort a list in place, we’ll use the sort method from the Collections class. It’ll mutate our list, changing the order of the elements:
List<Integer> numbers = new ArrayList<>();
numbers.add(5);
numbers.add(2);
numbers.add(8);
numbers.add(1);
System.out.println("Before sorting: " + numbers); // Output: Before sorting: [5, 2, 8, 1]
Collections.sort(numbers);
System.out.println("After sorting: " + numbers); // Output: After sorting: [1, 2, 5, 8]
Sorting in place is usually faster and more memory-efficient, but by definition, it needs to work on a mutable collection, which isn’t always desirable or possible.
5.2. Sorting Without Mutation
We can also sort our list without changing the original collection. To do that, we’ll create a stream from the list, sort it, and then collect it into a new list:
List<Integer> sortedList = numbers.stream().sorted().collect(Collectors.toList());
System.out.println("After sorting: " + sortedList); // Output: After sorting: [1, 2, 5, 8]
System.out.println("Original list: " + numbers); // Output: Original list: [5, 2, 8, 1]
We could also use the knowledge from previous paragraphs, and instead of collecting the elements of the stream to a new list, we could collect it to a TreeSet. That way, we wouldn’t need to explicitly sort it — the TreeSet implementation will do that for us:
TreeSet<Integer> sortedSet = numbers.stream().collect(Collectors.toCollection(() -> new TreeSet<>()));
System.out.println("After sorting: " + sortedSet); // Output: After sorting: [1, 2, 5, 8]
System.out.println("Original list: " + numbers); // Output: Original list: [5, 2, 8, 1]
6. Summary
In this article, we’ve seen that the absence of a built-in sorted list implementation in Java’s collection framework is a thoughtful decision that upholds the List interface contract. We then looked into which data structures we can use instead if we want to achieve sorting on insertion.
Finally, we also learned how to sort on demand if we decide to use the List interface.
