В чём разница между ArrayList и LinkedList?

ArrayList и LinkedList — это две реализации интерфейса List в Java, но внутренне они устроены по-разному, что определяет их поведение, производительность и применимость в различных ситуациях.

📦 1. Структура данных

Коллекция Структура
ArrayList Основан на массиве (Object[])
--- ---
LinkedList Основан на двусвязном списке (Node<prev,next>)
--- ---

🚀 2. Время выполнения операций

Операция ArrayList LinkedList
Получение элемента (get(index)) ✅ Быстро — O(1) ❌ Медленно — O(n) (нужно пройти по списку)
--- --- ---
Добавление в конец (add) ✅ Быстро — O(1) (если не resize) ✅ Быстро — O(1)
--- --- ---
Вставка в середину (add(index)) ❌ Медленно — O(n) (смещение) ❌ Медленно — O(n) (проход к индексу)
--- --- ---
Удаление по индексу ❌ Медленно — O(n) (смещение) ❌ Медленно — O(n) (проход + перепривязка)
--- --- ---
Удаление с начала (remove(0)) ❌ Самая медленная — O(n) ✅ Самая быстрая — O(1)
--- --- ---

🛠 3. Использование памяти

  • ArrayList хранит только данные.

  • LinkedList хранит данные + ссылки на предыдущий и следующий элементы → больше затрат памяти на каждый элемент.

🔄 4. Реализация

ArrayList

Object\[\] elementData;
int size;
  • При превышении размера — происходит копирование массива в новый с увеличенной длиной (обычно на 50%).

LinkedList

private static class Node&lt;E&gt; {
E item;
Node&lt;E&gt; next;
Node&lt;E&gt; prev;
}
  • Каждый элемент — это узел, хранящий ссылки на соседей.

⛓ 5. Итерация

  • Оба поддерживают Iterator, ListIterator, for-each.

  • У LinkedList вставка/удаление через итератор быстрее и безопаснее (нет сдвига, как в массиве).

⚠️ 6. Когда какую коллекцию использовать?

Выбирайте ArrayList, если:

  • Часто нужен **доступ по индексу
    **
  • Преобладают добавления в конец и **чтение
    **

  • Размер списка известен заранее

  • Важна **производительность по памяти
    **

Выбирайте LinkedList, если:

  • Часто происходит **удаление/вставка в начало или середину
    **
  • Используется **много итераторов
    **
  • Размер списка сильно **меняется
    **
  • Не нужен быстрый доступ по индексу

📊 Пример:

List&lt;String&gt; arrayList = new ArrayList<>();
List&lt;String&gt; linkedList = new LinkedList<>();
arrayList.add("one");
arrayList.get(0); // быстро
linkedList.add("one");
linkedList.get(0); // медленно (поиск узла)

🧠 Вывод

Критерий ArrayList LinkedList
Быстрый доступ по индексу ✅ Да (O(1)) ❌ Нет (O(n))
--- --- ---
Вставка/удаление в середине ❌ Медленно (O(n)) ❌ Медленно (O(n))
--- --- ---
Вставка/удаление в начале ❌ Очень медленно (O(n)) ✅ Очень быстро (O(1))
--- --- ---
Использование памяти 🔽 Эффективнее 🔼 Затратнее
--- --- ---
Подходит для Чтения, индексированного доступа Частых вставок/удалений
--- --- ---

Выбор зависит от конкретных задач — нет универсального "лучше", только "лучше для вашего случая".

08-07-2025
Easy 9 просмотров