Sorted array list in Java

by

Minimalistic Solution

Here is a quick and dirty solution.

class SortedArrayList<T> extends ArrayList<T> {
    @SuppressWarnings("unchecked")
    public void insertSorted(T value) {
        int i = Collections.binarySearch((List<Comparable<T>>) this, value);
        add(i < 0 ? -i - 1 : i, value);
    }
}

Note that despite the binarySearch, insertSorted will run in linear time since add(index, value) runs in linear time for an ArrayList.

Inserting something non-comparable results in a ClassCastException. (This is the approach taken by PriorityQueue as well: A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).)

A more complete implementation would, just like the PriorityQueue, also include a constructor that allows the user to pass in a Comparator.

Demo

SortedArrayList<String> test = new SortedArrayList<String>();

test.insertSorted("ddd");    System.out.println(test);
test.insertSorted("aaa");    System.out.println(test);
test.insertSorted("ccc");    System.out.println(test);
test.insertSorted("bbb");    System.out.println(test);
test.insertSorted("eee");    System.out.println(test);

….prints:

[ddd]
[aaa, ddd]
[aaa, ccc, ddd]
[aaa, bbb, ccc, ddd]
[aaa, bbb, ccc, ddd, eee]

Overriding List.add

Note that overriding List.add (or List.addAll for that matter) to insert elements in a sorted fashion would be a direct violation of the interface specification.

From the docs of List.add:

boolean add(E e)
    Appends the specified element to the end of this list (optional operation).

Maintaining the sortedness invariant

Unless this is some throw-away code, you probably want to guarantee that all elements remain sorted. This would include throwing UnsupportedOperationException for methods like add, addAll and set, as well as overriding listIterator to return a ListIterator whose set method throws.

More Related Contents:

  1. Automatically sorted by values map in Java
  2. Java sort 4 arrays into 1 array
  3. In selection sort, if we have two duplicate elements, what is the behavior of the algorithm?
  4. Sorted array in Java: how can I implement? [closed]
  5. Sort on a string that may contain a number
  6. Why is there no SortedList in Java?
  7. JTable design to synchronize with back-end data-structure
  8. How to sort List of objects by some property
  9. Java Array Sort descending?
  10. How to implement a Map with multiple keys? [duplicate]
  11. Sort a Map by values
  12. How to detect a loop in a linked list?
  13. Collections.sort with multiple fields
  14. Java Set retain order?
  15. Java 8 stream reverse order
  16. How do I sort a list by different parameters at different timed
  17. How to sort Date which is in string format in java?
  18. Why does my sorting loop seem to append an element where it shouldn’t?
  19. Sorting Strings that contains number in Java [duplicate]
  20. Why should I use Deque over Stack?
  21. Java List Sorting: Is there a way to keep a list permantly sorted automatically like TreeMap?
  22. Data structures that can map a range of keys to a value
  23. Android how to sort JSONArray of JSONObjects
  24. sorting integers in order lowest to highest java
  25. Why does my JTable sort an integer column incorrectly?
  26. How to use Collections.sort() in Java?
  27. Java Sorting: sort an array of objects by property, object not allowed to use Comparable
  28. Sorting ArrayList of Objects by Object attribute
  29. Creating a LinkedList class from scratch
  30. Sorting a List in parallel without creating a temporary array in Java 8

Leave a Comment