Список отсортированных массивов в Java

Я сбит с толку, что не могу найти быстрый ответ на этот. По сути, я ищу структуру данных на Java, которая реализует интерфейс java.util.List , но хранит свои элементы в отсортированном порядке. Я знаю, что вы можете использовать обычный ArrayList и использовать в нем Collections.sort () , но у меня есть сценарий, в котором я иногда добавляю и часто получаю участников из своего списка, и я не хочу, чтобы мне приходилось сортировать его каждый раз, когда я извлекаю член, если был добавлен новый. Может ли кто-нибудь указать мне на такую ​​вещь, которая существует в JDK или даже сторонних библиотеках?

РЕДАКТИРОВАТЬ : структура данных должна сохранять дубликаты.

РЕЗЮМЕ ОТВЕТА : Я нашел все это очень интересно и многому научился. В частности, Aioobe заслуживает упоминания за его настойчивость в попытках достичь моих требований выше (в основном, отсортированная реализация java.util.List, которая поддерживает дубликаты). Я принял его ответ как наиболее точный из того, что я спросил, и как наводящий на большинство размышлений о последствиях того, что я искал, даже если то, что я спросил, было не совсем тем, что мне нужно.

Проблема с тем, что я просил, заключается в самом интерфейсе List и концепции дополнительных методов в интерфейсе. Процитируем javadoc:

Пользователь этого интерфейса имеет точный контроль над тем, где в списке должен быть вставлен каждый элемент.

Вставка в отсортированный список не имеет точного контроля над точкой вставки. Затем вы должны подумать, как вы будете обрабатывать некоторые методы. Возьмем add , например:

public boolean add (Object o)

  Добавляет указанный элемент в конец этого списка (необязательная операция).

Теперь вы оказались в неудобной ситуации: 1) Нарушение контракта и реализация отсортированной версии добавления 2) Если разрешить добавить , добавить элемент в конец списка, нарушив порядок сортировки. 3) Оставив добавить (как необязательный), выбрасывая исключение UnsupportedOperationException и реализуя другой метод, который добавляет элементы в отсортированном порядке.

Вариант 3, вероятно, лучший, но я считаю сомнительным наличие метода добавления, который вы не можете использовать, и другого метода sortedAdd, которого нет в интерфейсе.

Другие связанные решения (в произвольном порядке):

• java.util.PriorityQueue , который является наверное, ближе всего к тому, что мне было нужно, чем то, о чем я просил. Очередь - не самое точное определение коллекции объектов в моем случае, но функционально она делает все, что мне нужно.
• net.sourceforge.nite.util.SortedList . Тем не мение, эта реализация нарушает контракт интерфейса List, реализуя сортировку в методе add (Object obj) и, как ни странно, не имеет никакого эффекта для add (int index, Object obj) . По общему мнению, throw new UnsupportedOperationException () может быть лучшим выбором в этом сценарии.
• Guava's TreeMultiSet Реализация набора, которая поддерживает дубликаты
• ca.odell.glazedlists.SortedList Этот класс имеет оговорку в своем javadoc: Предупреждение: этот класс нарушает контракт, требуемый List