1. Введение
В Java существует две реализации интерфейса List: ArrayList и LinkedList. Какая из них лучше? Как выбрать подходящую для вашего приложения? В данной статье мы сравним их различия, производительность и потребление памяти, чтобы помочь вам определиться с выбором.
2. Сложность алгоритмов
2.1. Сложность алгоритмов для основных операций со списками
Основой всех дискуссий о различиях между списками на основе массива (ArrayList) и связного списка (LinkedList) является сложность алгоритмов, измеряемая с помощью математической нотации O(n). Сложность операций, предоставляемых интерфейсом List, обычно описывается как O(1), O(n) или даже O(log n).
В данной статье мы сравним сложность следующих операций:
Получение элемента: поскольку производительность этой операции зависит от позиции элемента, рассмотрим три случая его получения — из начала списка, из конца и из середины
Вставка элемента: аналогично, сравним вставку для разных позиций элементов — в начало списка, в середину и в конец (хотя технически это не совсем вставка)
Итерация по элементам списка: здесь существуют два подхода к итерации — с использованием индекса и с помощью Iterator
Далее в таблице приведена сложность перечисленных операций, которую можно найти в любом учебнике по структурам данных.
На первый взгляд разница невелика: для LinkedList сложность O(n) встречается только в двух операциях — чтение из середины и вставка в середину. Однако при детальном рассмотрении обнаруживаются важные нюансы.
Для ArrayList:
операции вставки в начало и в середину требуют сдвига всех последующих элементов
чтение из середины выполняется мгновенно благодаря прямой индексации
Для LinkedList:
вставка в середину и чтение из середины выполняются за счет последовательного перебора узлов до нужного элемента
при вставке в начало происходит обновления ссылки соседнего узла
2.2. Что означает сложность алгоритма?
Обозначение O(n) означает, что после определённого порогового значения время выполнения алгоритма становится пропорциональным объему обрабатываемых данных (n). Проще говоря, если количество данных превышает этот порог, то их удвоение приведёт к двукратному увеличению времени обработки.
Для сложности O(1) время работы алгоритма не зависит от объёма данных. Это логично: например, чтение первого элемента списка не требует знания его общего размера.
Таким образом, нотация O(n) описывает асимптотическое поведение алгоритма. При этом объем обрабатываемых данных должен быть выше порогового значения.
Ключевой момент в определении сложности — фраза "после определённого порога". Как определить этот порог количества обрабатываемых данных?
Пороговое значение — это минимальный размер данных, после которого время выполнения становится пропорциональным объему входных данных (n).
Предположим, вы выполняете алгоритм для обработки данных, и известно, что количество операций составляет a n + b.
Пример 1
Пусть a = 10, b = 1, n = 10
Подставим эти значения в формулу: 10 10 + 1 = 101
Выполним упрощение, приведя сложность алгоритма к O(n): 10 10 = 100
Ошибка: (101 - 100) / 101 ≈ 1%
Порог: упрощение работает при n ≥ 10
Можно утверждать, что алгоритм работает за O(n) и дает погрешность менее 1%, если отбросить (упростить) константу 1 (b). Уже при n = 10 линейный член (10 * n) в 100 раз больше константы (1). Ошибка в 1% — несущественна. Ей можно пренебречь.
Пример 2
Пусть a = 1, b = 10
Чтобы сохранить погрешность оценки процессорного времени в 1% при работе алгоритма O(n), необходимо значение n >= 1000
Подставим эти значения в формулу: 1 * 1000 + 10 = 1010
Ошибка: (1010 - 1000) / 1010 ≈ 1%
Ключевая мысль — знание сложности O(n) полезно, но недостаточно. Важно понимать, что это конкретно означает для вашего случая? Какой именно у вашего приложения порог данных? Если порог — 1 000, а вы обрабатываете 100 элементов, формула O(n) неприменима к вашему случаю.
Внутренние механизмы ArrayList и LinkedList работают совершенно по-разному. Их производительность зависит не только от асимптотической сложности O(n), но и от скрытых факторов (кэш CPU, аллокация памяти и проч.). Далее мы разберём эти нюансы, чтобы помочь вам выбрать оптимальную структуру данных.
3. Чтение элементов из списка
Представим, что в нашей программе есть множество небольших задач. Какой способ будет наиболее эффективным для повышения производительности? При этом мы не хотим создавать множество потоков.
Давайте создадим первый бенчмарк для измерения производительности чтения из списка: первого элемента, последнего и из середины.
Поскольку мы ожидаем разные результаты при различном размере списка, тестирование будет проведено для списков разного размера. Все представленные бенчмарки выполнены с использованием JMH — единственного инструмента для надежного измерения производительности в Java.
3.1. Чтение первого и последнего элемента
Тестовый код выглядит следующим образом (одинаковый для ArrayList и LinkedList с разными размерами списков от 10 до 10_000 элементов). Результаты передаются в JMH Blackhole, чтобы гарантировать, что JVM-оптимизации не исказят измерения.
JMH Blackhole — это специальный инструмент, подавляющий некоторые оптимизации кода JVM с целью повышения точности бенчмарков.
Пример:
List ints = ...; // varies in size
int LAST = ints.size() - 1;
int MIDDLE = ints.size() / 2;
// читаем 1й элемент списка
ints.get(0);
// читаем последний элемент
ints.get(LAST);
// читаем средний элемент
ints.get(MIDDLE);Результаты чтения первого элемента:
ArrayList SIZE Score Error Units
Read first 10 1.181 ± 0.022 ns/op
Read first 100 1.200 ± 0.041 ns/op
Read first 1000 1.167 ± 0.009 ns/op
Read first 10000 1.174 ± 0.014 ns/op
LinkedList SIZE Score Error Units
Read first 10 1.127 ± 0.030 ns/op
Read first 100 1.107 ± 0.008 ns/op
Read first 1000 1.121 ± 0.016 ns/op
Read first 10000 1.119 ± 0.014 ns/opКак видно, результаты для обеих реализаций одинаковы и не зависят от размера списка, что соответствует ожиданиям.
Результаты чтения последнего элемента:
ArrayList SIZE Score Error Units
Read last 10 1.248 ± 0.020 ns/op
Read last 100 1.232 ± 0.035 ns/op
Read last 1000 1.240 ± 0.019 ns/op
Read last 10000 1.254 ± 0.040 ns/op
LinkedList SIZE Score Error Units
Read last 10 1.493 ± 0.040 ns/op
Read last 100 1.467 ± 0.019 ns/op
Read last 1000 1.475 ± 0.019 ns/op
Read last 10000 1.484 ± 0.042 ns/opНаблюдается небольшое снижение производительности для LinkedList (доли наносекунды), однако эта разница незначительна и не имеет практического значения.
3.2. Чтение среднего элемента списка
Ситуация меняется, когда вы пытаетесь получить доступ к середине списка:
ArrayList SIZE Score Error Units
Read middle 10 1.571 ± 0.055 ns/op
Read middle 100 1.616 ± 0.073 ns/op
Read middle 1000 1.543 ± 0.018 ns/op
Read middle 10000 1.537 ± 0.010 ns/op
LinkedList SIZE Score Error Units
Read middle 10 3.211 ± 0.023 ns/op
Read middle 100 31.118 ± 0.321 ns/op
Read middle 1000 566.079 ± 8.696 ns/op
Read middle 10000 7836.099 ± 902.666 ns/opКак видно, доступ к среднему элементу ArrayList примерно такой же по сложности, как и доступ к его последнему элементу, поскольку осуществляется по индексу. При этом он не зависит от размера массива — по крайней мере, для тестируемых размеров.
Совершенно иначе обстоит дело с LinkedList. Доступ к среднему элементу здесь требует значительных затрат и зависит от количества элементов в списке.
Тот факт, что доступ к последнему элементу был таким же быстрым, как и к первому, объясняется тем, что реализация LinkedList хранит прямые ссылки на первый и последний узлы своего связного списка.
Чтобы понять, почему доступ к среднему элементу так затратен, необходимо учитывать структуру связного списка, используемую в классе LinkedList.
Реализация связного списка в Java представляет собой коллекцию объектов типа Node, где каждый узел содержит три ссылки: на хранимый объект, на следующий узел и на предыдущий узел.
Таким образом, LinkedList по сути является двусвязным списком. Кроме того, класс LinkedList хранит две дополнительные ссылки: на первый и последний узлы, что обеспечивает быстрый доступ к ним.
Однако доступ к среднему узлу менее эффективен, поскольку требует последовательного перебора ссылок на последующие узлы (next) от начала или конца списка (в зависимости от того, какой путь короче. Это своего рода оптимизация) до нужной позиции. Именно это мы наблюдаем в бенчмарке: чтение среднего элемента LinkedList требует значительных затрат из-за отсутствия прямой ссылки на нужный элемент, причем время доступа увеличивается с ростом размера списка.
Стоит отметить, что доступ к среднему узлу является наихудшим сценарием. Благодаря наличию ссылок на первый и последний узлы, всегда выбирается кратчайший путь к целевому элементу.
Снижение производительности объясняется эффектом "погони за указателем". Как известно, чтение ссылок приводит к загрузке соответствующих областей памяти в кэш процессора. Если требуемая область уже находится в кэше, доступ происходит мгновенно. В противном случае возникает "промах кэша", требующий дополнительного времени на подгрузку данных из основной памяти.
Вы можете наблюдать этот эффект, создав связный список особым способом. В только что выполненном бенчмарке список создавался следующим кодом через поток.
var ints =
IntStream.range(0, LIST_SIZE)
.boxed()
.collect(Collectors.toCollection(LinkedList::new));Вероятнее всего (поскольку это не реальное приложение), все узлы этого списка расположены в памяти близко друг к другу. Поэтому при чтении ссылки next текущего узла высока вероятность, что следующий узел уже находится в кэше процессора, так как был загружен вместе с текущим узлом.
Теперь представим альтернативный способ создания списка, который гарантирует, что узлы будут разбросаны в памяти. В следующем примере мы создаем дополнительные узлы между элементами нашего тестового списка, сохраняя в них ссылки во время бенчмарка (чтобы сборщик мусора не перемещал объекты).
var ints = new LinkedList<>();
var intsOther = new LinkedList<>();
for (int i = 0; i < LIST_SIZE; i++) {
ints.add(i);
for (int j = 0; j < SPARSE_INDEX; j++) {
intsOther.add(j);
}
}Затем мы можем запустить бенчмарк несколько раз с разными значениями SPARSE_INDEX, чтобы исследовать влияние разрозненного расположения узлов на производительность.
Вот результаты:
LinkedList SIZE SPARSE Score Error Units
Read middle 1000 0 561.428 ± 4.853 ns/op
Read middle 1000 1 602.401 ± 17.126 ns/op
Read middle 1000 10 944.997 ± 31.920 ns/op
Read middle 1000 100 1509.282 ± 28.749 ns/opДействительно, "погоня за указателем" значительно снижает производительность при случайном доступе к элементам LinkedList. Как видно из тестов, работа со списком, узлы которого разбросаны в памяти хаотично, оказывается в три раза медленнее по сравнению со списком, где узлы расположены последовательно.
Стоит отметить, что в реальных приложениях, где элементы постоянно добавляются и удаляются из связного списка, чаще всего наблюдается именно такая (неоптимальная с точки зрения производительности) ситуация со случайным распределением узлов в памяти.
4. Итерация по элементам списка
4.1. Использование индекса и итератора
В Java существует два основных подхода к итерации по списку:
классический подход с использованием Iterator из Collections Framework
индексный подход — последовательный доступ к элементам по индексу
Для LinkedList итерация с индексами может привести к серьёзным проблемам с производительностью из-за "погони за указателями", поскольку каждый переход к следующему узлу требует разыменования ссылки.
Индексный подход:
var ints = ...; // LinkedList или ArrayList
for (var index = 0; index < ints.size(); index++) {
var v = ints.get(index);
// pass v to the blackhole
}Итератор (через for-each):
for (var v : ints) {
// pass v to the blackhole
}Компилятор автоматически преобразует for-each в итератор в байт-коде.
Для ArrayList оба шаблона примерно одинаковы. Использование индекса немного более затратно из-за необходимости управлять этим индексом.
Вы можете задаться вопросом, почему увеличение индекса (примитива) обходится дороже, чем работа с итератором (объектом)? Дело в том, что for-each не предоставляет программисту итератор, поэтому его нельзя использовать ни для чего, кроме перебора списка. Когда дело доходит до оптимизации кода, JIT-компилятор может это учесть и в некоторых случаях оптимизировать этот участок, избегая создания итератора. В результате получается код, который работает значительно быстрее, поскольку никакой объект итератора не создается.
ArrayList SIZE Score Error Units
Iterate iterator 1000 1.447 ± 0.024 ms/op
Iterate index 1000 1.986 ± 0.045 ms/opДля LinkedList ситуация иная. Использование итератора здесь обходится дороже, чем в ArrayList. В ArrayList достаточно применить смещение к базовому адресу в памяти, чтобы получить нужный элемент, тогда как в LinkedList приходится переходить по ссылкам, что с высокой вероятностью приводит к "промаху кэша", если следующий узел еще не загружен в него.
Использование индекса для перебора LinkedList крайне неэффективно и является плохой практикой. Такой подход подразумевает, что для каждого элемента списка вы начинаете с начала и последовательно переходите от узла к узлу (в отличие от итератора, который запоминает текущую позицию), пока не достигнете нужного индекса. Сложность такого алгоритма — O(n^2). Никогда не используйте этот способ для LinkedList!
Например, перебор LinkedList из 1000 элементов с помощью индекса занимает около полсекунды, тогда как с итератором — всего 4 мс.
LinkedList SIZE Score Error Units
Iterate iterator 1000 4.950 ± 0.116 ms/op
Iterate index 1000 584.889 ± 4.396 ms/op4.2. Итерация по копии LinkedList
Итерация по LinkedList примерно в два раза медленнее, чем по ArrayList. Возникает вопрос: будет ли эффективнее преобразовать сначала LinkedList в ArrayList, а затем уже выполнить перебор?
Конечно, такое копирование потребует дополнительной памяти, а также могут возникнуть проблемы, если исходный список изменится во время итерации. Но с точки зрения производительности этот подход стоит рассмотреть.
Разберём следующий шаблон и проведём замеры скорости:
var ints =
IntStream.range(0, 1_000)
.boxed()
.collection(Collection.toCollection(LinkedList::new));
var copyOfInts = ints.stream().toList();
for (var v: copyOfInts) {
// pass v to the blackhole
}Вот какие результаты получаются. Как видно, для списка из 1000 элементов копирование занимает всего 4% от времени полного перебора всех элементов. Поэтому если ваше приложение может позволить себе дополнительные затраты памяти и вам нужно многократно итерировать по списку или обращаться к элементам в произвольном порядке, то преобразование LinkedList в ArrayList очень быстро окупается.
Стоит отметить, что в данном случае мы используем метод Stream.toList() для создания списка. Во-первых, он создает неизменяемый список, а во-вторых, применяет оптимизацию — сразу создает массив нужного размера, вместо постепенного расширения массива, как это делают ArrayList и Collectors.toList().
LinkedList SIZE ITERATION Score Error Units
toList then iterate 1000 1 5.182 ± 0.347 ms/op
toList then iterate 1000 10 14.031 ± 0.793 ms/op
toList then iterate 1000 100 100.104 ± 7.422 ms/opВывод: беготня по указателям и "промахи кэша" могут убить производительность. Этому влиянию подвержены любые структуры данных, основанные на ссылках: связные списки, префиксные деревья, бинарные деревья, красно-черные деревья, списки с пропусками, и в меньшей степени — хеш-карты.
5. Вставка элементов в список
Связные списки известны своей превосходной производительностью при вставке элементов в произвольную позицию. Вставка элемента требует лишь изменения ссылки next предыдущего узла на вставляемый узел и ссылки prev следующего узла. На первый взгляд, это операция выглядит очень легковесной. Однако для нее вам необходимо получить доступ к предыдущему и следующему узлам. А из предыдущего примера вы уже знаете, что такая операция весьма затратна.
С другой стороны, вставка элемента в ArrayList кажется более сложной. Необходимо сдвинуть правую часть массива на одну ячейку вправо, чтобы освободить место для нового элемента. Перемещение содержимого массива выглядит как операция, которая не может быть дешевой.
Кстати, удаление элементов работает аналогично. В связном списке нужно перенаправить указатели соседних узлов, а в массиве — сдвинуть часть элементов влево.
Оба алгоритма фундаментально разные, и предугадать, какой окажется быстрее, непросто. Давайте попробуем измерить производительность этих операций.
5.1. Вставка элементов в LinkedList
Рассмотрим три сценария: вставка в начало списка, вставка в середину и вставка в конец.
Ожидаемые результаты:
поскольку LinkedList хранит прямые ссылки на первый и последний узлы, разница между вставкой в начало и конец должна быть незначительной и не зависеть от размера списка
вставка в середину, напротив, будет требовать больше ресурсов, причем сложность операции будет расти пропорционально размеру списка
Реальная картина для вставки в начало подтверждает эти ожидания — увеличение размера списка не приводит к существенному изменению производительности.
LinkedList SIZE Score Error Units
Insert first 10 7.002 ± 0.306 ns/op
Insert first 100 7.126 ± 0.424 ns/op
Insert first 1000 7.561 ± 0.371 ns/op
Insert first 10000 7.738 ± 0.614 ns/opАналогичная ситуация наблюдается при добавлении элементов в конец. Разница с вставкой в начало по-прежнему присутствует, но остается крайне незначительной.
LinkedList SIZE Score Error Units
Adding 10 9.135 ± 0.137 ns/op
Adding 100 9.076 ± 0.082 ns/op
Adding 1000 9.795 ± 0.399 ns/op
Adding 10000 9.549 ± 0.202 ns/opВставка в середину списка по индексу действительно оказывается значительно дороже, и эта стоимость растет с увеличением размера списка. Цена доступа к средним элементам оказывается высокой. Эти замеры проводились на разреженном связном списке, где узлы расположены в памяти не последовательно.
LinkedList SIZE Score Error Units
Insert middle 10 10.641 ± 0.679 ns/op
Insert middle 100 49.122 ± 1.808 ns/op
Insert middle 1000 584.870 ± 6.925 ns/op
Insert middle 10000 46157.961 ± 379.327 ns/op5.2. Вставка элементов в ArrayList
Вы можете предположить, что вставка элемента сводится лишь к сдвигу части массива на одну ячейку вправо. Однако необходимо учитывать и другой сценарий — изменение размера массива. Невозможно добавить элемент в полностью заполненный массив. В этом случае реализация ArrayList копирует весь массив в новый массив большего размера, после чего добавляет элемент. Размер нового массива вычисляется на основе размера текущего массива с коэффициентом 1.5. Поэтому при постоянном добавлении элементов (например, в цикле) операция увеличения размера происходит всё реже.
Рассмотрим две ситуации: вставка в массив, где есть свободное место и вставка в заполненный массив.
В первом случае всё работает как ожидается:
добавление в конец практически не зависит от размера массива. Небольшое увеличение времени выполнения, вероятно, связано с "промахами кеша" при работе с очень большими массивами. Разница между ArrayList размером 1_000 и 10_000 элементов незначительна
ArrayList SIZE Score Error Units
Adding 10 2.215 ± 0.053 ns/op
Adding 100 2.184 ± 0.027 ns/op
Adding 1000 5.607 ± 0.856 ns/op
Adding 10000 5.240 ± 0.777 ns/opвставка в середину более затратна из-за необходимости копирования части массива
ArrayList SIZE Score Error Units
Insert middle 10 23.708 ± 0.370 ns/op
Insert middle 100 25.399 ± 0.241 ns/op
Insert middle 1000 56.061 ± 0.840 ns/op
Insert middle 10000 294.457 ± 4.689 ns/opвставка в начало — самая дорогостоящая операция, так как требует перемещения наибольшего количества элементов (фактически всего массива)
ArrayList SIZE Score Error Units
Insert first 10 22.380 ± 0.266 ns/op
Insert first 100 26.929 ± 0.385 ns/op
Insert first 1000 78.958 ± 1.429 ns/op
Insert first 10000 717.892 ± 9.242 ns/opКогда массив не может вместить новый элемент, реализация ArrayList копирует внутренний массив в массив большего размера. Эта операция не учитывалась в предыдущих тестах, но вы можете легко создать новый тест с заполненным массивом, чтобы измерить влияние перераспределения.
Сравнение этих первоначальных тестов с аналогичным тестом для большего массива показывает стоимость создание нового массива и копирования существующих данных.
ArrayList SIZE Score Error Units
Adding in a full array 10 19.300 ± 2.953 ns/op
Adding in a full array 100 45.488 ± 3.922 ns/op
Adding in a full array 1000 432.351 ± 46.055 ns/op
Adding in a full array 10000 4140.668 ± 329.160 ns/opКак и ожидалось, стоимость операции зависит от размера массива и является затратной.
К счастью, перераспределение происходит редко. Количество операций растет сублинейно, а коэффициент роста уменьшается с каждым перераспределением.
Важный вывод: если вы можете заранее создать массив нужного размера — сделайте это. Это позволит избежать затрат на перераспределение.
Хоть стоимость перераспределения выше стоимости вставки, разница между вставкой в середину и в начало списка оказывается незначительной, что подтверждают следующие бенчмарки.
ArrayList SIZE Score Error Units
Insert middle in a full array 10 39.334 ± 1.588 ns/op
Insert middle in a full array 100 61.037 ± 2.130 ns/op
Insert middle in a full array 1000 451.471 ± 27.247 ns/op
Insert middle in a full array 10000 4638.632 ± 360.694 ns/op
ArrayList SIZE Score Error Units
Insert first in a full array 10 28.288 ± 0.656 ns/op
Insert first in a full array 100 52.935 ± 2.457 ns/op
Insert first in a full array 1000 452.179 ± 37.434 ns/op
Insert first in a full array 10000 4762.783 ± 133.468 ns/op6. Сравнение вставки для LinkedList и ArrayList
Как видно, ArrayList превосходит LinkedList по всем операциям, кроме одной. Это может быть неожиданно, ведь с алгоритмической точки зрения LinkedList выглядит лучше, особенно для операций вставки. Но поскольку этот эффективный алгоритм выполняется на оборудовании, где переходы по указателям очень затратны, эти накладные расходы становятся доминирующими и делают его неэффективным. Однако есть два случая, где LinkedList работает лучше.
Вставка в начало списка
LinkedList имеет два преимущества: время вставки не зависит от размера списка. Благодаря прямой ссылке на первый элемент переходы по указателям происходят максимум один раз.
Кроме того, производительность не зависит от способа добавления элементов в LinkedList. Факт случайного распределения узлов в памяти не влияет на результат.
Добавления элементов в конец списка
Производительность почти одинакова, так как в этом случае ArrayList не нужно перемещать элементы внутреннего массива. Хотя эта операция не так быстра, как в ArrayList, она предсказуема. Если же реализации ArrayList потребуется увеличить внутренний массив, это может вызвать значительное падение производительности.Несмотря на высокую стоимость перераспределения, из-за его редкого возникновения влияние на общую производительность приложения усредняется. Помните, что вы можете (и должны!) создавать ArrayList с нужным размером, когда это возможно. В целом, считать стоимость перераспределения веским аргументом в пользу LinkedList перед ArrayList — ошибочно.
Таким образом, есть два сценария, где LinkedList интересен и либо превосходит ArrayList, либо сравним с ним: операции в начале списка и операции в конце списка.
Неважно, чтение это, вставка или удаление — стоимость операций примерно одинакова.
Действительно, LinkedList отлично подходит для реализации стеков и очередей. Но для обычных списков он не так хорош и почти всегда уступает ArrayList по производительности.
7. Анализ потребления памяти
Как ведут себя ArrayList и LinkedList с точки зрения потребления памяти? Это сложный вопрос, так как разные JVM могут по-разному управлять памятью, а одна и та же JVM может использовать разные стратегии в зависимости от доступного объема памяти. Мы используем инструмент MemoryLayout из OpenJDK для измерения потребляемой памяти.
В целом хранение одинакового количества объектов в LinkedList требует больше памяти, чем в ArrayList — обычно значительно больше. Причина проста: каждое значение в LinkedList хранится в объекте Node, который также содержит две ссылки (на предыдущий и следующий узлы). Такой объект обычно занимает 24 байта (включая заголовок объекта Node).
Точное потребление памяти может варьироваться в зависимости от приложения. Для приложений, использующих менее 32GB памяти, эти цифры обычно точны.
Например:
для 1000 объектов LinkedList потребляет чуть более 24KB
ArrayList для тех же объектов — чуть менее 5KB
Однако есть один случай, когда хранение объекта в ArrayList требует больше памяти. Если вам нужно сохранить всего один объект, ArrayList может создать внутренний массив размером 10 (в зависимости от способа создания списка). В этом случае ArrayList потребляет больше памяти, чем LinkedList: 80 байт против 56 байт.
Таким образом, если у вас много списков с одним элементом, это может привести к проблемам с потреблением памяти. Иначе говоря: если ваше приложение создает множество ArrayList и вы сталкиваетесь с неожиданными проблемами памяти, стоит проверить, сколько объектов фактически хранят эти списки. Возможно, вы создаете почти пустые ArrayList, которые занимают много неиспользуемой памяти.
Точное потребление памяти одноэлементного ArrayList зависит от способа его создания. Вот различные варианты и их результаты:
var intsV1 = new ArrayList();
intsV1.add(1); // wraps an array of size 10
var intsV2 = new ArrayList();
intsV2.addAll(List.of(1)); // wraps an array of size 10
var intsV3 = new ArrayList(List.of(1)); // wraps an array of size 1В таком случае у вас есть несколько вариантов: использовать LinkedList и List.of().
Второй вариант более эффективен по памяти (всего 26 байт на элемент) по сравнению с ArrayList и LinkedList. Однако стоит помнить про неизменяемость таких списков.
Последнее замечание по потреблению памяти:
LinkedList всегда использует ровно столько памяти, сколько нужно для хранения элементов — в нём нет пустых узлов
ArrayList автоматически увеличивает внутренний массив при заполнении
Стоит помнить, что в ArrayList нет механизма автоматического уменьшения массива. Если приложение удаляет много элементов, внутренний массив может остаться большим (из-за необходимости в прошлом), но почти пустым, бесполезно занимая память.
Фактически, ArrayList копирует массив в более крупный при заполнении, но никогда не уменьшает его при опустошении. При проблемах с памятью это важно учитывать.
К счастью, есть метод ArrayList.trimToSize(), который уменьшает вместимость внутреннего массива до текущего размера списка. Например, после его вызова для одноэлементного ArrayList он станет компактнее одноэлементного LinkedList. Хотя это сразу экономит память, последующее добавление элементов снова потребует расширения.
Как видно из таблицы, несмотря на то, что ArrayList может использовать массив не полностью, он всё равно потребляет значительно меньше памяти, чем аналогичный LinkedList. Хранение узловых объектов (Node) расходует по 24 байта на каждый элемент — это намного больше, чем размер частично заполненного массива.
Даже в наихудшем сценарии, когда ArrayList требуется перераспределение памяти (и временно существуют два массива — заполненный и увеличенный), он всё равно остаётся более экономным, чем LinkedList.
Вывод: если в вашем приложении критично потребление памяти, ArrayList является самым оптимальным решением.
7.1. Сколько элементов можно разместить в заданной куче?
Допустим, ваше приложение постоянно добавляет элементы в список. Давайте сравним, сколько элементов поместится в ArrayList и LinkedList при заданном размере кучи (H). Мы рассматриваем только потребление памяти самими списками, без учёта размера хранимых объектов.
LinkedList:
требует 24 байта на каждый узел
максимум элементов: (H / 24)
ArrayList:
требуется 4 байта для ссылки на каждый объект в массиве
при заполненном внутреннем массиве: (H / 4) элементов
в среднем с учётом незаполненной части, составляющей 33% от общего объема, используется уже ~6 байт на элемент
при постоянном добавлении элементов ArrayList эффективнее LinkedList в 4-6 раз
Худший случай при перераспределении массива:
ArrayList использует два массива: старый (N) и новый (1.5 * N)
требуется 10 байт (6 + 4) на элемент
даже в этом случае ArrayList в 2.4 раза эффективнее
Можно сделать вывод, что для заданного размера кучи ArrayList всегда хранит больше элементов (до 6 раз), включая периоды перераспределения.
8. Какую реализацию выбрать?
ArrayList — это эффективная реализация, которая превосходит LinkedList практически во всех стандартных операциях со списками, по крайней мере, когда вам нужен обычный список. Даже если алгоритмы LinkedList теоретически лучше, эта структура основана на указателях и страдает от проблемы переходов по ссылкам.
Из-за этого:
итерация происходит медленно
доступ по индексу требует значительных затрат, что негативно влияет на все основные операции: вставку, замену и удаление. Даже если сами эти операции в LinkedList требуют меньше действий, их производительность резко падает из-за высокой стоимости доступа к нужному элементу
ArrayList не так эффективен при вставке элементов из-за операции System.arraycopy(), но в большинстве случаев всё равно работает лучше, чем LinkedList. Перераспределение памяти в ArrayList — довольно затратная операция, но она происходит редко, особенно если вы заранее знаете, сколько элементов нужно хранить. Вы можете избежать изменения размера, создавая ArrayList с достаточной начальной ёмкостью для всех необходимых объектов.
Есть один случай, когда LinkedList работает лучше ArrayList: когда нужно обращаться только к первому или последнему элементу списка. То есть, когда вам нужен стек или очередь (Queue), а не обычный список. Кстати, LinkedList действительно реализует Queue и Deque. Однако если вам нужна двусторонняя очередь (Deque), лучше выбрать реализацию ArrayDeque.
С точки зрения памяти, LinkedList потребляет значительно больше, чем ArrayList. Однако есть исключение: список из одного элемента в LinkedList может занимать меньше места, чем в ArrayList, если ArrayList использует массив размером 10. Это можно исправить, используя List.of() или вызвав ArrayList.trimToSize().
Если вам нужны списки с небольшим количеством элементов в условиях ограниченной памяти, создание ArrayList с начальной ёмкостью 2 — хорошее решение. Такой список занимает всего 48 байт для 0, 1 или 2 элементов. При добавлении элементов массив расширяется до 3, затем до 4 и до 6 элементов (занимая 56, 56 и 64 байта соответственно). Во всех случаях (кроме пустого списка) он компактнее LinkedList. Он также меньше стандартного ArrayList до размера 9 и совпадает по размеру с "подрезанным" ArrayList до размера 7.
Это можно увидеть в таблице ниже, полученной следующим образом:
создали списки: new ArrayList<>(2), new LinkedList<>(), new ArrayList<>(), new ArrayList<>().trimToSize()
измерили начальное потребление памяти
добавляли элементы по одному (от 0 до 10) для всех списков одновременно
для последнего списка после всех добавлений вызвали trimToSize() один раз
проверили потребление памяти
Последнее, что стоит запомнить: ArrayList никогда не уменьшается в размере. Вызов операции удаления или очистки не приводит к копированию внутреннего массива в массив меньшего размера. Однако эту ситуацию можно исправить, вызвав ArrayList.trimToSize(), который инициирует копирование внутреннего массива в массив меньшего размера.
