Содержание:

1. ArrayList
2. LinkedList
3. Сравнение ArrayList и LinkedList
4. Список литературы/курсов

Список — это упорядоченная коллекция, наиболее часто используемая в Java Collections Framework. Интерфейс List контролирует порядок добавленных элементов списка, сохраняет его и позволяет в любой момент времени обратиться к любому элементу по его порядковому номеру. Списки выражают то, что у нас есть коллекция элементов, которые расположены в некоторой последовательности друг за другом. Эта последовательность может измениться только если ее изменит сам разработчик. Каждый элемент имеет целочисленный индекс (как в массиве). Стандартные реализации интерфейса List позволяет иметь элементы с одинаковым значением. Как мы уже сказали выше, List знает про индекс элемента, что позволяет получить (get(...)) элемент по индексу или задать значением для определённого индекса (set(...)). Методы коллекций add, addAll, remove так же позволяют указать индекс элемента, с которым они будут работать. Кроме того, у List есть своя версия итератора, которая называется ListIterator. Он знает про индекс элемента, поэтому умеет итерироваться не только вперёд, но и назад. Его даже можно создать от определённого места в коллекции.

Интерфейс List имеет две стандартные реализации — ArrayList и LinkedList.

ArrayList

ArrayList — это список на основе массива (Array), то есть он содержит внутри себя массив. Работа ArrayList схожа с работой простых массивов и по-сути является оболочкой для них. Этот класс содержит самые необходимые методы для работы с массивами, таким образом разработчик освобожден от необходимости контролировать размерность массива и манипулировать элементами внутри него. Например, длина массива внутри списка будет увеличиваться автоматически при добавлении в него элемента с индексом превышающим размер массива. А при удалении объекта, нет необходимости сдвигать все остальные элементы справа на один индекс влево.

Наличие массива как основной структуры несет за собой все плюсы и минусы массивов. Такой список позволяет добиться произвольного доступа (Random Access) к элементам, т.е. добавляет возможность сразу получить элемент по индексу, а не перебирать все элементы, пока не найдём элемент с нужным порядковым номером. Для массива в памяти выделяется количество ячеек равное размерности массива. Ячейки смежные и располагаются друг за другом, элементы массива в них хранятся в такой же последовательности, как и в массиве. Это крайне позитивно влияет на скорость получения элемента по индексу и итерирования. Например, некоторые оптимизации при работе с циклами позволяют доставать из памяти не каждый элемент отдельно, а сразу набор одним запросом, что еще увеличивает скорость перебора массива.

Но при этом добавление и удаление элементов эффективно только при работе с концом массива, и наоборот, чем ближе к началу списка, тем такие операции затратнее. Отсюда вытекают и сложности с любыми сортировками. А увеличение размера массива приводит к выделению памяти и полному копированию всех элементов. Чтобы минимизировать издержки, рекомендуется определять размер исходного массива сразу при инициализации объекта ArrayList, используя специальный конструктор ArrayList(int capacity).

LinkedList

Вторая реализация интерфейса List — класс LinkedList. Это решение основано на другой структуре данных - двусвязном списке. Как следует из названия, каждый элемент такого списка имеет две связи: с предыдущим и следующим элементом. Каждая запись в связанном списке представлена в виде объекта класса Entry, который хранит сами данные, а также ссылку на следующий (next) и предыдущий (previous) объект Entry. Таким образом LinkedList реализует последовательный доступ (Sequential Access).

В отличие от массивов все элементы располагаются в памяти в случайном порядке. Для получения элемента по его индексу необходимо преодолеть путь от начала (или конца) списка через каждый элемент, пока не будет достигнут искомый. Но при этом вставка или удаление любого элемента предполагает лишь изменение ссылок у соседних элементов. Увеличение длины списка также простая операция: достаточно добавить ссылку в последнем элементе, сделав его предпоследним, и заменить ссылку на последний элемент в полях самого объекта LinkedList.

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

Сравнение ArrayList и LinkedList

ArrayList и LinkedList — идентичны с точки зрения интерфейса, то есть их методы полностью совпадают. Они оба могут добавлять и извлекать элементы из любой части списка. Но из-за особенностей структур, в которых хранятся элементы массива, можно наблюдать разную алгоритмическую сложность одних и тех же операций. Сравним средние значения в таблице:

Согласно существующим оценкам сложности и учитывая плюсы и минусы каждого из решений, можно дат ь следующие рекомендации по использованию классов списков:

ArrayList подходит для ситуаций, когда:

• Предполагается добавление элементов в конец заранее проинициализированного пустого списка;
• Планируется единоразовое заполнение списка с дальнейшим многократным итерированием;
• Планируется единоразовое заполнение списка с дальнейшим многократным обращение к элементам по индексу.

Не рекомендуется использовать ArrayList, если

• Предполагается частая перестановка элементов местами, в т.ч. пересортировки;
• Будут частые вставки/удаления в/из середины списка.

LinkedList подходит для ситуаций, когда:

• Изначально даже примерно неизвестна размерность списка, при этом предполагается большое количество добавлений элементов;
• Предполагается большое количество вставок (удалений) элементов в список;
• Необходимо периодически пересортировывать список или изменять порядок элементов;

Не рекомендуется использовать LinkedList, если:

• Предполагается частое обращение к элементам по индексу;
• Необходимо часто итерировать список, при условии минимального количества изменений в нем, после первичного заполнения.

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

Список литературы/курсов

1. https://java-blog.ru/collections/java-list
2. https://docs.oracle.com/javase/tutorial/collections/interfaces/list.html
3. https://vertex-academy.com/tutorials/ru/list-java-primer/

Тема 15. Java Collection Framework | Оглавление | Тема 17. Очереди