Когда использовать связанный список по массиву/списку массива?
Мой oneliner для преобразования трассировки стека в прилагаемую многострочную строку:
Stream.of(e.getStackTrace()).map((a) -> a.toString()).collect(Collectors.joining("\n", "[", "]"))
Легко перейти к регистратору «как есть».
5 ответов
Связанные списки предпочтительны по массивам когда:
-
Вам нужны постоянно-разовые вставки/удаления из списка (такие как в режиме реального времени вычисление, где предсказуемость времени абсолютно очень важна)
-
, Вы не знаете, сколькими объекты будут в списке. С массивами Вы, возможно, должны повторно объявить и скопировать память, если массив становится слишком большим
-
, Вам не нужен произвольный доступ ни к каким элементам
-
, Вы хотите быть в состоянии вставить объекты посреди списка (такие как приоритетная очередь)
, Массивы предпочтительны когда:
-
Вам нужен индексируемый / произвольный доступ к элементам
-
, Вы знаете число элементов в массиве загодя так, чтобы можно было выделить корректный объем памяти для массива
-
, Вам нужна скорость при итерации через все элементы в последовательности. Можно использовать математику указателя на массиве для доступа к каждому элементу, тогда как Вам нужен к поиску узел на основе указателя для каждого элемента в связанном списке, который может привести к отсутствиям страницы, которые могут привести к хитам производительности.
-
память является беспокойством. Заполненные массивы поднимают меньше памяти, чем связанные списки. Каждый элемент в массиве является просто данными. Каждый узел связанного списка требует данных, а также одного (или больше) указатели на другие элементы в связанном списке.
Списки массива (как те в.Net) приносят Вам пользу массивов, но динамично выделяют ресурсы для Вас так, чтобы Вы не должны были волноваться слишком много о размере списка, и можно удалить объекты в любом индексе без любого усилия или перестановки элементов вокруг. Мудрый производительностью, arraylists медленнее, чем необработанные массивы.
Преимущество списков появляется, если Вы должны вставить объекты в середине и не хотите начинать изменять размеры массива и смещать вещи вокруг.
Вы корректны в этом, это обычно - не случай. У меня было несколько очень конкретных случаев как этот, но не слишком многие.
Хм, Arraylist может использоваться в случаях, любят, следует, я предполагаю:
- Вы не уверены, сколько элементов будет существующих
- , но необходимо получить доступ ко всем элементам случайным образом посредством индексации
Для, например, необходимо импортировать и доступ все элементы в списке контактов (размер которого неизвестен Вам)
Для добавления к другим ответам большинство реализаций списка массива резервирует дополнительную способность в конце списка так, чтобы новые элементы могли быть добавлены до конца списка в O (1) время. Когда способность списка массива превышена, новый, больший массив выделяется внутренне, и все старые элементы копируются. Обычно, новый массив удваивает размер старого. Это означает, что [в среднем 110], добавление новых элементов до конца списка массива является O (1) операция в этих реализациях. Таким образом, даже если Вы не знаете числа элементов заранее, список массива может все еще быть быстрее, чем связанный список для добавления элементов, пока Вы добавляете их в конце. Очевидно, вставка новых элементов в произвольных местоположениях в списке массива является все еще O (n) операция.
элементы Доступа в списке массива также быстрее, чем связанный список, даже если доступы последовательны. Это вызвано тем, что элементы массива хранятся в непрерывной памяти и могут кэшироваться легко. Узлы связанного списка могут потенциально быть рассеяны по многим различным страницам.
я рекомендовал бы только использовать связанный список, если Вы знаете, что собираетесь быть вставкой или удалением объектов в произвольных местоположениях. Списки массива будут быстрее для в значительной степени всего остального.
Массивы имеют O (1) произвольный доступ, но являются действительно дорогими, чтобы добавить материал на или удалить материал из.
Связанные списки являются действительно дешевыми, чтобы добавить или удалить объекты куда угодно и выполнить итерации, но произвольный доступ является O (n).