Какую реализацию List использовать?

Question

В моей программе я часто использую коллекции для хранения списков объектов.В настоящее время я использую ArrayList для хранения объектов.Мой вопрос: это лучший выбор?Может быть, лучше использовать LinkedList?Или что-то еще?

Критерии, которые следует учитывать:

• Использование памяти
• Производительность

Операции, которые мне нужны:

• Добавить элемент в коллекцию
• Перебирать элементы

Есть мысли?

Обновление: мой выбор: ArrayList :) Основываясь на этом обсуждении, а также на следующих:

• Когда использовать LinkedList поверх ArrayList?
• Список реализаций: делаетLinkedList действительно так плохо работает по сравнению с ArrayList и TreeList?

Answer 1

Я всегда по умолчанию на ArrayList, и в вашем случае также, за исключением случаев, когда

• Мне нужна безопасность потоков (в этом случае я начинаю смотреть на реализации List в java.util.concurrent)
• Я знаю, что буду много вставлять и манипулировать списком, или профилирование покажет, что мое использование ArrayList является проблемой (очень редко)

Что касается выбора во втором случае, у этого потока SO.com есть несколько полезных идей: Реализация списка: действительно ли LinkedList так плохо работает по сравнению с ArrayList и TreeList?

Answer 2

Учитывая ваши критерии, вы должны использовать LinkedList.

LinkedList реализует интерфейс Deque, что означает, что он может добавлять в начало или конец списка за постоянное время (1). Кроме того, ArrayList и LinkedList будут выполнять итерацию за (N) время.

Вы НЕ должны использовать ArrayList просто потому, что стоимость добавления элемента при заполнении списка. В этом случае добавление элемента будет (N) из-за создания нового массива и копирования всех элементов из одного массива в другой.

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

Answer 3

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

Answer 4

Это зависит от вашего профиля использования.

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

Оба хороши в итерации, обе реализации Итератора O (1) для next().

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

Answer 5

Если вы добавляете только в конец списка, ArrayList должно быть в порядке. Из документации ArrayList:

Детали политики роста не указаны за исключением того факта, что добавление элемента имеет постоянную амортизированную стоимость времени

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

Answer 6

ArrayList отлично подходит для ваших (и большинства других) целей. Он имеет очень небольшую нагрузку на память и имеет хорошую амортизированную производительность для большинства операций Случаи, когда он не идеален, относительно редки:

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

Answer 7

Это классический компромисс между оптимизацией вставки и извлечения.Общий выбор для задачи, как вы описываете это ArrayList.

Answer 8

Связанный список быстрее для добавления / удаления внутренних элементов (т.е. не голова или хвост)

Arraylist быстрее для итерации