Какая разница между ArrayList и LinkedList?android-14

Оба класса реализуют интерфейс List, но имеют принципиальные различия в реализации и производительности.

1. Внутренняя структура

// ArrayList
transient Object[] elementData; // Хранение в массиве

// LinkedList
transient Node<E> first; // Связный список через узлы
transient Node<E> last;

• ArrayList: Использует динамический массив для хранения элементов. При превышении capacity создается новый массив с увеличенным размером (обычно в 1.5 раза).

• LinkedList: Реализован как двусвязный список, где каждый элемент (Node) содержит ссылки на предыдущий и следующий элементы.

2. Производительность операций

Доступ по индексу

list.get(index);

• ArrayList: O(1) - прямое обращение по индексу в массиве
• LinkedList: O(n) - требуется последовательный перебор от начала/конца

Вставка/удаление в середину

list.add(index, element);
list.remove(index);

• ArrayList:

  • O(n) - требует сдвига всех последующих элементов
  • O(1) если добавление в конец (без resize)

• LinkedList:

  • O(1) если известна позиция (итератор)
  • O(n) для поиска позиции

Добавление в начало

list.add(0, element);

• ArrayList: O(n) - требует сдвига всех элементов
• LinkedList: O(1) - просто создается новый узел

3. Память

• ArrayList:

  • Занимает меньше памяти (только массив + служебные поля)
  • Может иметь "лишнюю" память (capacity > size)

• LinkedList:

  • Занимает больше памяти (каждый элемент имеет 2 ссылки)
  • Нет избыточного выделения памяти

4. Итерация

• ArrayList: Быстрее благодаря кэшированию и последовательному доступу в памяти
• LinkedList: Медленнее из-за необходимости перехода по ссылкам

5. Использование

Когда использовать ArrayList:

• Частый доступ по индексу
• Частое добавление в конец
• Минимальные вставки/удаления в середину

Когда использовать LinkedList:

• Частые вставки/удаления в начало/середину
• Редкий доступ по индексу
• Реализация очередей/стэков

Резюмируем:

• ArrayList - массив с быстрым доступом, медленными вставками
• LinkedList - связный список с медленным доступом, быстрыми вставками/удалениями