В ситуациях, когда нет явного преимущества между LinkedList и ArrayList, что следует использовать?

Question

В случае, когда единственной операцией, выполняемой над списком, является неслучайный доступ (без удалений, дополнений или других томов), целесообразно ли использовать массив, ArrayList, LinkedList или что-то еще? или это не имеет значения, который выбран?

Answer 1

За исключением некоторых конкретных ситуаций (например, встроенных систем), вы, вероятно, работаете с иерархической и / или виртуальной системой памяти.

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

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

http://en.wikipedia.org/wiki/Locality_of_reference

В области компьютерных наук, местность ссылка, также известный как принцип местности, это явление то же значение или соответствующее хранилище места, к которым часто обращаются. Существует два основных типа ссылок местонахождение. Временная местность относится к повторное использование конкретных данных и / или ресурсы в течение относительно небольшого времени длительностей. Пространственная местность относится к использование элементов данных в относительно близкие места хранения. Последовательная местность, частный случай пространственная локализация, происходит, когда данные элементы расположены и доступны линейно, например, проходя элементы в одномерном массиве.

Местность - это всего лишь один тип предсказуемое поведение, которое происходит в Компьютерные системы. Системы, которые проявлять сильную местность ссылки хорошие кандидаты на производительность оптимизация за счет использования методы, такие как кэш и технология предварительной выборки инструкций для память, или как расширенная ветвь предиктор при конвейерной обработке процессоры.

Исходя из этого, при прочих равных условиях я бы выбрал ArrayList вместо LinkedList.

Answer 2

Я думаю, что ваш вопрос в какой-то степени отвечает самому себе: если не имеет значения, какой из них выбран, то не имеет значения, какой вы выберете; если это имеет значение, тогда выберите лучший.

Это мягко издевательски, но из-за отсутствия специфики выбор сводится к следующему.

Если это поможет, Учебное пособие по коллекциям Java , похоже, рекомендует ArrayList в качестве реализации списка общего назначения, когда нет соответствующих критериев:

В каждом случае одна реализация - HashSet, ArrayList и HashMap - явно используется для большинства приложений, при прочих равных условиях.

Конечно, сторонний код, который я видел (и код стороннего, который я написал), также принимает этот принцип.

Answer 3

Судя по вашему вопросу, кажется, что все, что вы делаете - это перебираете список (без добавления, без удаления, без случайных поисков). Таким образом, между двумя реализациями не должно быть большой разницы (как вы заметили).

Единственное, о чем я могу думать, - это создание пространства и объектов. ArrayList требует меньше памяти для хранения своих данных (массив против узла: данные + следующий + предыдущий). Таким образом, мой вариант по умолчанию будет использовать ArrayList.

Answer 4

A LinkedList будет иметь дополнительную нагрузку на память для ссылок.Я не думаю, что есть большая разница между ArrayList и массивом, если вы используете конструктор для установки начальной емкости ArrayList, поэтому я склонен использовать ArrayList всякий раз, когда не вижу явного преимущества.Это ситуативно, хотя ... например, если я использую параметры vararg для ввода, я могу сохранить все как массивы для простоты.

Answer 5

LinkedList на самом деле довольно специализированный;Я бы использовал его только с большим, довольно динамичным списком, требующим только последовательного доступа.

Если ваш список небольшой или требует произвольного доступа или не имеет большого количества вставок и удалений, используйте ArrayList.

Answer 6

Если данные статические и вы просто выполняете поиск, используйте массив.Если вы используете ArrayList, у вас будет некоторое время инициализации, а у LinkedList будет медленный поиск + инициализация.