Sorted collection in Java

Question

I'm a beginner in Java. Please suggest which collection(s) can/should be used for maintaining a sorted list in Java. I have tried Map and Set, but they weren't what I was looking for.

Answer 1

there is a class in the JDK just for the purpose of having a sorted list. It is named (somewhat out of order with the other Sorted* interfaces) "java.util.PriorityQueue". It can sort either Comparable<?>s or using a Comparator.

The difference with a List sorted using Collections.sort(...) is that this will maintain a partial order at all times, with O(log(n)) insertion performance, by using a heap data structure, whereas inserting in a sorted ArrayList will be O(n) (i.e., using binary search and move).

However, unlike a List, PriorityQueue does not support indexed access (get(5)), the only way to access items in a heap is to take them out, one at a time (thus the name PriorityQueue).