Списки являются одними из наиболее широко используемых коллекций Java. Список — это упорядоченная коллекция (или последовательность). Таким образом, он в чем-то отличается от наборов, карт и очередей. Список может содержать дубликаты и нулевые значения. Они также дают пользователям полную видимость и контроль над элементами.
Согласно Документации API, в интерфейсе List есть специальные методы для позиционного доступа, поиска и итерации. Таким образом, мы должны учитывать эти три аспекта при выборе реализации List.
Стандартные классы в Java, которые реализуют интерфейс List, следующие.
ArrayList
Это самая популярная реализация интерфейса List, которая действует аналогично массиву, за исключением того, что пользователям не нужно беспокоиться о размере. Но, с другой стороны, он не поддерживает некоторые нативные аспекты массива, такие как примитивы (без упаковки/распаковки) и прямое копирование/клонирование через память (system.arraycopy ).
Стандартная реализация ArrayList поддерживается массивом. Он имеет внутренний механизм с именем grow в add и addAll<. /strong> методы, которые увеличивают массив при необходимости.
Производительность операций произвольного доступа составляет O(1). Таким образом, ArrayList — хороший вариант, когда частота таких методов, как get и set,и итерация (не потокозависимая безопасный) высок.
Производительность поиска позиции элемента (indexOf, contains) равна O(N), потому что в худшем случае необходимо проверить все элементы, как в обычном массиве. .
Производительность добавления новых элементов непостоянна, потому что необходимо скопировать массив в другой массив, когда размер превышает емкость. Кстати, лучше использовать addAll, когда нужно добавить несколько элементов, вместо многократного вызова add. В худшем случае порядок вычислений для add равен O(N).
Удаление объекта либо по индексу, либо по самому объекту выполняет аналогичную операцию по освобождению памяти путем копирования внутреннего массива в другой массив. Таким образом, в целом стоимость операций добавить и удалить в ArrayList высока. Тем не менее, в конструкторе есть возможность определить начальную емкость. Это было бы хорошим выбором для оценки емкости и ее корректировки, чтобы уменьшить количество копий массива в add и сохранить порядок добавления, близкий к O(1). Но если частота операций remove высока, это может оказаться не лучшим решением.
Связанный список
Представляет собой структуру данных, реализующую List и Deque (двустороннюю очередь), которая, в отличие от ArrayList, не поддерживает внутренние механизмы хранения. Каждый LinkedList включает два основных указателя для хранения головы (первой) и хвоста (последней).
Операции доступа хорошо работают только для первого и последнего узлов в O(1). Таким образом, производительность операции add равна O(1), поскольку новый элемент добавляется к последнему. Но для remove требуется O(N), поскольку он выполняет итерацию по всем элементам, чтобы разъединить объект или найти объект по его индексу и удалить его.
Порядок сложности операций поиска (indexOf, содержит) такой же, как у ArrayList за O(N).
Порядок итерации — O(1), но позиционное индексирование с помощью get и set занимает O(N), потому что ему нужен линейный поиск, чтобы найти элемент по индексу.
КопиОнВритеАррайлист
Этот класс чем-то похож на ArrayList, и единственное отличие состоит в том, что он предназначен для обеспечения потокобезопасности наряду с быстрым доступом для чтения. Фактически, для изменяющих операций, таких как добавить и установить, он выполняет свою операцию над скопированной версией объекта. без вмешательства в операции чтения/итерации. Поэтому, когда частота записи ниже, чем чтения, это будет лучшим вариантом вместо Collections.synchronizedList. .
Одним из примеров использования этого класса является случай, когда набор объектов-наблюдателей должен получать частые уведомления о событиях. В этом сценарии огромное количество итераций над наблюдателями делает их полностью неизменяемыми, поэтому всякий раз, когда в наблюдателях происходят какие-либо изменения, лучше применить изменения к новой копии коллекции, а затем заменить ее. Таким образом, итерация продолжит свою работу без ConcurrentModificationException. Но в старом сценарии все итерации должны быть остановлены перед началом изменений.
Вектор
Является устаревшим классом, очень похожим на ArrayList с тем же порядком операций. Основное отличие состоит в том, что все методы этого класса реализованы как синхронизированные, поэтому с вектором в каждый момент времени может работать только один поток. Другие отличия связаны с несколькими улучшениями, внесенными в ArrayList. Например, в ArrayList итерация реализована в ListIterator, который является более новым обновлением, чем Enumeration, используемым в Vector, и поддерживает удаление при итерации.
Куча
Согласно API, он представляет собой стек объектов в порядке поступления (LIFO). С точки зрения реализации, он расширяет Vector и представляет собой устаревший класс, в котором почти нет улучшений. Стандартная документация по API предлагает вместо него использовать реализации Deque, такие как ArrayDeque.
