1. Обзор
Что касается коллекций , стандартная библиотека Java предоставляет множество вариантов на выбор. Среди этих вариантов есть две известные реализации List , известные как ArrayList и LinkedList, каждая со своими свойствами и вариантами использования.
В этом уроке мы увидим, как эти два элемента реализованы на самом деле. Затем мы оценим различные приложения для каждого из них.
2. Список массивов
Внутри ArrayList использует массив для реализации интерфейса List . Поскольку массивы в Java имеют фиксированный размер, ArrayList создает массив с некоторой начальной емкостью. Попутно, если нам нужно хранить больше элементов, чем эта емкость по умолчанию, он заменит этот массив новым и более просторным.
Чтобы лучше понять ее свойства, давайте оценим эту структуру данных в отношении ее трех основных операций: добавления элементов , получения одного по индексу и удаления по индексу .
2.1. Добавлять
Когда мы создаем пустой ArrayList, он инициализирует свой резервный массив емкостью по умолчанию (в настоящее время 10):
Добавить новый элемент, пока этот массив еще не заполнен, так же просто, как присвоить этот элемент определенному индексу массива. Этот индекс массива определяется текущим размером массива, так как мы практически добавляем к списку:
backingArray[size] = newItem;
size++;
Таким образом, в лучшем и среднем случаях временная сложность операции добавления составляет O(1) , что довольно быстро. Однако по мере заполнения резервного массива реализация добавления становится менее эффективной:
Чтобы добавить новый элемент, мы должны сначала инициализировать новый массив большей емкости и скопировать все существующие элементы в новый массив. Только после копирования текущих элементов мы можем добавить новый элемент. Следовательно, временная сложность в худшем случае равна O(n) , поскольку сначала нужно скопировать n элементов.
Теоретически добавление нового элемента выполняется за амортизированное постоянное время. То есть добавление n элементов требует O(n) времени. Однако некоторые отдельные добавления могут работать плохо из-за накладных расходов на копирование.
2.2. Доступ по индексу
Доступ к элементам по их индексам — это то, где ArrayList действительно сияет. Чтобы получить элемент с индексом i, нам просто нужно вернуть элемент, находящийся в индексе i из резервного массива. Следовательно, временная сложность доступа по индексной операции всегда равна O(1).
2.3. Удалить по индексу
Предположим, мы собираемся удалить индекс 6 из нашего ArrayList, который соответствует элементу 15 в нашем резервном массиве:
Пометив нужный элемент как удаленный, мы должны переместить все элементы после него назад на один индекс. Очевидно, чем ближе элемент к началу массива, тем больше элементов мы должны переместить. Таким образом, временная сложность составляет O (1) в лучшем случае и O (n) в среднем и худшем случаях.
2.4. Приложения и ограничения
Обычно ArrayList является выбором по умолчанию для многих разработчиков, когда им нужна реализация List . На самом деле, это разумный выбор, когда количество операций чтения намного превышает количество операций записи .
Иногда нам нужны одинаково частые операции чтения и записи. Если у нас есть оценка максимального количества возможных элементов, то все равно имеет смысл использовать ArrayList . Если это так, мы можем инициализировать ArrayList с начальной емкостью:
int possibleUpperBound = 10_000;
List<String> items = new ArrayList<>(possibleUpperBound);
Эта оценка может предотвратить множество ненужных операций копирования и выделения массивов.
Более того, в Java массивы индексируются значениями int . Таким образом, нельзя хранить более 2 32 элементов в массиве Java и, следовательно, в ArrayList .
3. Связанный список
LinkedList , как следует из названия, использует набор связанных узлов для хранения и извлечения элементов . Например, вот как выглядит реализация Java после добавления четырех элементов:
Каждый узел поддерживает два указателя: один указывает на следующий элемент, а другой — на предыдущий. Расширяя это, двусвязный список имеет два указателя, указывающих на первый и последний элементы.
Опять же, давайте оценим эту реализацию в отношении тех же основных операций.
3.1. Добавлять
Чтобы добавить новый узел, сначала мы должны связать текущий последний узел с новым узлом:
А затем обновите последний указатель:
Поскольку обе эти операции тривиальны, временная сложность операции добавления всегда составляет O(1) .
3.2. Доступ по индексу
LinkedList, в отличие от ArrayList, не поддерживает быстрый произвольный доступ. Итак, чтобы найти элемент по индексу, мы должны вручную пройти часть списка .
В лучшем случае, когда запрошенный элемент находится в начале или в конце списка, временная сложность будет такой же быстрой, как O (1). Однако в среднем и наихудшем сценарии мы можем получить время доступа O(n) , поскольку нам нужно проверять множество узлов один за другим.
3.3. Удалить по индексу
Чтобы удалить элемент, мы должны сначала найти запрошенный элемент, а затем удалить его из списка . Следовательно, время доступа определяет временную сложность, то есть O(1) в лучшем случае и O(n) в среднем и в худшем случае.
3.4. Приложения
Связанные списки больше подходят, когда скорость добавления намного выше, чем скорость чтения .
Кроме того, его можно использовать в сценариях с интенсивным чтением, когда большую часть времени нам нужен первый или последний элемент. Стоит отметить, что LinkedList также реализует интерфейс Deque , поддерживая эффективный доступ к обоим концам коллекции.
Как правило, если мы знаем различия в их реализации, мы можем легко выбрать один для конкретного варианта использования.
Например, предположим, что мы собираемся хранить множество событий временных рядов в структуре данных, похожей на список. Мы знаем, что будем получать всплески событий каждую секунду.
Кроме того, нам нужно периодически проверять все события одно за другим и предоставлять некоторую статистику. Для этого варианта использования LinkedList является лучшим выбором, потому что скорость добавления намного выше, чем скорость чтения.
Кроме того, мы бы прочитали все элементы, поэтому мы не можем превзойти верхнюю границу O (n) .
4. Вывод
В этом руководстве мы сначала рассмотрели, как ArrayList и LinkLists реализованы в Java.
Мы также оценили различные варианты использования для каждого из них.