Как стать автором
Обновить

Рекомендации Oracle по выбору между ArrayList и LinkedList

Уровень сложностиПростой
Время на прочтение19 мин
Количество просмотров3.3K
Автор оригинала: dev.java
  1. Введение

  2. Сложность алгоритмов

  3. Чтение элементов из списка

  4. Итерация по элементам списка

  5. Вставка элементов в список

  6. Сравнение вставки

  7. Анализ потребления памяти

  8. Какую реализацию выбрать?

1. Введение

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

2. Сложность алгоритмов

2.1. Сложность алгоритмов для основных операций со списками

Основой всех дискуссий о различиях между списками на основе массива (ArrayList) и связного списка (LinkedList) является сложность алгоритмов, измеряемая с помощью математической нотации O(n). Сложность операций, предоставляемых интерфейсом List, обычно описывается как O(1), O(n) или даже O(log n).

В данной статье мы сравним сложность следующих операций:

  1. Получение элемента: поскольку производительность этой операции зависит от позиции элемента, рассмотрим три случая его получения — из начала списка, из конца и из середины

  2. Вставка элемента: аналогично, сравним вставку для разных позиций элементов — в начало списка, в середину и в конец (хотя технически это не совсем вставка)

  3. Итерация по элементам списка: здесь существуют два подхода к итерации — с использованием индекса и с помощью Iterator

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

Сложность операций для ArrayList и LinkedList
Сложность операций для ArrayList и LinkedList

На первый взгляд разница невелика: для 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.

Внутренняя структура 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/op

4.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 кажется более сложной. Необходимо сдвинуть правую часть массива на одну ячейку вправо, чтобы освободить место для нового элемента. Перемещение содержимого массива выглядит как операция, которая не может быть дешевой.

Вставка элемента в ArrayList
Вставка элемента в 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/op

5.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/op

6. Сравнение вставки для LinkedList и ArrayList


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

  1. Вставка в начало списка
    LinkedList имеет два преимущества: время вставки не зависит от размера списка. Благодаря прямой ссылке на первый элемент переходы по указателям происходят максимум один раз.

    Кроме того, производительность не зависит от способа добавления элементов в LinkedList. Факт случайного распределения узлов в памяти не влияет на результат.

  2. Добавления элементов в конец списка
    Производительность почти одинакова, так как в этом случае 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. Хотя это сразу экономит память, последующее добавление элементов снова потребует расширения.

Потребление памяти для 1 и 1000 элементов
Потребление памяти для 1 и 1000 элементов

Как видно из таблицы, несмотря на то, что 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(), который инициирует копирование внутреннего массива в массив меньшего размера.

Теги:
Хабы:
+6
Комментарии8

Публикации

Работа

Java разработчик
176 вакансий

Ближайшие события