Что лучше для сортировки: ArrayList или LinkedList?
Я хочу использовать структуру данных, которую нужно время от времени сортировать. Размер структуры данных вряд ли превысит 1000 элементов.
Какой из них лучше - ArrayList или LinkedList ?
Какой алгоритм сортировки лучше использовать?
3 ответа
До Java 7 это не имело никакого значения, потому что Collections.sort выводил содержимое списка в массив.
В Java 8 использование ArrayList должно быть немного быстрее, потому что Collections.sort вызовет List.sort, а ArrayList имеет специализированную версию, которая сортирует резервный массив напрямую, сохраняя копию.
Таким образом, суть в том, что ArrayList лучше, так как дает аналогичную или лучшую производительность в зависимости от версии Java.
Если вы можете использовать библиотеку Apache, взгляните на TreeList . Это решает вашу проблему правильно.
Если вы просто сортируете, а не динамически обновляете свой отсортированный список, то все в порядке, и массив будет более эффективным в использовании памяти. Связанные списки действительно лучше, если вы хотите сохранить отсортированный список. Вставка объекта происходит быстро в середину связанного списка, но медленно в массив.
Массивы лучше, если вы хотите найти объект в середине. С помощью массива вы можете выполнить двоичную сортировку и определить, есть ли член в списке за O (logN). Со связанным списком вам нужно пройти весь список, который очень медленный.
Я думаю, что лучше для вашего приложения, зависит от того, что вы хотите сделать со списком после его сортировки.