How to Implement a Sorted Array List in Java While Preserving Duplicates

Question

What is the best way to create a sorted list in Java that allows duplicate elements?

import java.util.*;

public class SortedArrayListExample {
    public static void main(String[] args) {
        List<Integer> sortedList = new ArrayList<>();
        // Adding elements in sorted order
        sortedAdd(sortedList, 5);
        sortedAdd(sortedList, 3);
        sortedAdd(sortedList, 7);
        sortedAdd(sortedList, 3); // Adding duplicate
        System.out.println(sortedList); // Outputs: [3, 3, 5, 7]
    }

    public static void sortedAdd(List<Integer> list, Integer element) {
        int index = Collections.binarySearch(list, element);
        if (index < 0) {
            index = -(index + 1); // Find insertion point
        }
        list.add(index, element); // Add element at index
    }
}

Answer

In Java, creating a sorted list that supports duplicates requires careful consideration of the implementation. While the standard `ArrayList` does not maintain order when inserting elements, you can use a custom approach or alternative data structures to achieve the desired behavior efficiently.

import java.util.*;

public class SortedArrayListExample {
    public static void main(String[] args) {
        List<Integer> sortedList = new ArrayList<>();
        // Adding elements in sorted order
        sortedAdd(sortedList, 5);
        sortedAdd(sortedList, 3);
        sortedAdd(sortedList, 7);
        sortedAdd(sortedList, 3); // Adding duplicate
        System.out.println(sortedList); // Outputs: [3, 3, 5, 7]
    }

    public static void sortedAdd(List<Integer> list, Integer element) {
        int index = Collections.binarySearch(list, element);
        if (index < 0) {
            index = -(index + 1); // Find insertion point
        }
        list.add(index, element); // Add element at index
    }
}

Causes

Java's `ArrayList` does not maintain sorted order on element insertion.
The `List` interface does not inherently support sorted operations without overriding the standard behavior.

Solutions

Use a `PriorityQueue` for automatic ordering but consider that it does not allow indexed access.
Implement a custom method to add items in sorted order by using binary search, as demonstrated in the provided code snippet.
Utilize third-party libraries that provide collection types designed to maintain sorted order.

Common Mistakes

Mistake: Using Collections.sort() every time before retrieving elements.

Solution: Instead, maintain the sorted order during insertion to optimize performance.

Mistake: Overriding the `add` method improperly in a custom list implementation.

Solution: Consider offering a separate method for sorted insertion that does not conflict with the `List` interface.

Helpers

Java sorted list
Java list with duplicates
Java collection sorted
PriorityQueue Java
SortedArrayList Java