← Назад к вопросам
В чём разница между ArrayList и LinkedList?
1.3 Junior🔥 211 комментариев
#Коллекции#ООП#Основы Java
Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI21 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
# Разница между ArrayList и LinkedList
Это два различных реализации интерфейса List в Java, и каждая имеет свои сильные и слабые стороны.
Внутренняя структура
ArrayList - это динамический массив. Данные хранятся в обычном массиве Java, который автоматически увеличивается в размере при необходимости.
ArrayList<String> list = new ArrayList<>();
list.add("первый"); // O(1) amortized
list.add("второй"); // O(1) amortized
list.get(0); // O(1) - быстро!
LinkedList - это двусвязный список. Каждый элемент (узел) содержит ссылки на предыдущий и следующий элементы.
LinkedList<String> list = new LinkedList<>();
list.add("первый"); // O(1)
list.add("второй"); // O(1)
list.get(0); // O(n) - медленно!
Сложность операций
| Операция | ArrayList | LinkedList |
|---|---|---|
| get(index) | O(1) | O(n) |
| add(element) | O(1) amortized | O(1) |
| add(index, element) | O(n) | O(n) if random access |
| remove(index) | O(n) | O(n) if random access |
| remove(element) | O(n) | O(n) |
Память и производительность
ArrayList:
- Занимает меньше памяти (нет лишних ссылок на соседние элементы)
- Лучше кэширование (элементы лежат в памяти подряд)
- Быстрое чтение по индексу
- При вставке в середину нужно сдвигать элементы
LinkedList:
- Занимает больше памяти (две ссылки на узел)
- Плохо кэшируется (узлы разбросаны по памяти)
- Быстрое добавление/удаление в начало/конец
- При вставке в конец можно добавить без сдвига
Когда что использовать
Используй ArrayList в 95% случаев:
- Нужен доступ по индексу
- Часто читаешь данные
- Редко вставляешь/удаляешь в начало/середину
Используй LinkedList редко:
- Много операций добавления/удаления в начало списка
- Часто итерируешь с Iterator.remove()
- Не нужен быстрый доступ по индексу
Итератор
ArrayList<String> al = new ArrayList<>();
for (String s : al) { // O(n)
System.out.println(s);
}
LinkedList<String> ll = new LinkedList<>();
for (String s : ll) { // O(n)
System.out.println(s); // For enhanced for - хорошо
}
// Но избегай так:
for (int i = 0; i < ll.size(); i++) {
ll.get(i); // O(n) для каждого элемента = O(n²) вообще!
}
Вывод
ArrayList - универсальный выбор, обеспечивающий предсказуемую производительность. LinkedList используется только для специфических сценариев, где нужны частые операции с началом/концом списка. В современной Java ArrayList предпочтительнее в большинстве случаев.