Является ли ArrayList или LinkedList лучше для сортировки?

Ответ 1

До Java 7 это не имело никакого значения, потому что Collections.sort удалил содержимое списка в массив.

С Java 8 использование ArrayList должно быть немного быстрее, потому что Collections.sort будет вызывать List.sort, а ArrayList имеет специализированную версию, которая напрямую сортирует массив подстановки, сохраняя копию.

Итак, нижняя строка ArrayList лучше, так как она дает аналогичную или лучшую производительность в зависимости от версии Java.

Ответ 2

Если вы собираетесь использовать java.util.Collections.sort(List), тогда это действительно не имеет значения.

Если List не реализует RandomAccess, тогда он будет сбрасываться в List. Список будет сбрасываться в массив для целей сортировки в любом случае.

(Спасибо, что поддержал меня честным Ральфом. Похоже, я смутил реализации сортировки и перетасовки. Они достаточно близки к тому же самому?)

Ответ 3

Если вы можете использовать библиотеку Apache, посмотрите TreeList. Он правильно решает вашу проблему.

Ответ 4

Только 1000 предметов? Почему вас это волнует?

Я обычно всегда использую ArrayList, если у меня нет конкретной необходимости в противном случае.

Посмотрите исходный код. Я думаю, что сортировка основана на массивах в любом случае, если я правильно помню.

Ответ 5

Если вы просто сортируете и не динамически обновляете свой отсортированный список, то либо это хорошо, и массив будет более эффективным с точки зрения памяти. Связанные списки действительно лучше, если вы хотите сохранить отсортированный список. Вставка объекта происходит быстро в середину связанного списка, но медленнее в массив.

Массивы лучше, если вы хотите найти объект посередине. С помощью массива вы можете выполнить двоичную сортировку и найти, находится ли член в списке в O (logN). Со связанным списком вам нужно пройти весь список, который очень медленный.

Я думаю, что лучше для вашего приложения зависит от того, что вы хотите сделать со списком после его сортировки.