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

Question

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

Какой из них лучше - ArrayList или LinkedList?

Какой алгоритм сортировки лучше использовать?

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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

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