Post

ArrayList vs LinkedList

Часто встечающиюся вопросы о Java

Posted Updated
By Ilya Muromtsev
5 min read
ArrayList vs LinkedList

ArrayList vs LinkedList, сложность

ArrayList и LinkedList: устройство, вставка, поиск

1. Внутреннее устройство

ArrayList

  • Основан на динамическом массиве (Object[] elementData).
  • Автоматически расширяется при заполнении (обычно в 1.5 раза).
  • Прямой доступ по индексу за O(1).
  • Неэффективен при частых вставках/удалениях в середину.
    1
2

    ArrayList<Integer> list = new ArrayList<>();
// Внутри: Object[10] (по умолчанию), при переполнении -> Object[15] и т.д.

LinkedList

  • Основан на двусвязном списке (узлы Node с ссылками prev/next).
  • Нет затрат на расширение массива.
  • Эффективен для вставок/удалений в начало/середину/конец.
  • Медленный доступ по индексу (требуется обход с начала или конца).
    1
2

    LinkedList<Integer> list = new LinkedList<>();
// Внутри: first -> Node(prev=null, item=1, next=Node2) <-> Node2(prev=Node1, item=2, next=null) <- last

2. Сложность операций add/insert/get/remove

ArrayList (динамический массив)

ОперацияСложность (Big O)Пояснение
Добавление в конец (add(E e))O(1) (амортизированная)Вставка в конец обычно O(1), но при расширении массива — O(n)
Вставка по индексу (add(int index, E e))O(n)Требуется сдвиг всех элементов правее index
Получение по индексу (get(int index))O(1)Прямой доступ к элементу массива
Удаление по индексу (remove(int index))O(n)Сдвиг всех элементов правее index
Поиск по значению (contains(E e))O(n)Линейный поиск (перебор всех элементов)
Удаление по значению (remove(Object o))O(n)Поиск (O(n)) + удаление (O(n))

Особенности:

  • Доступ по индексу (get/set) — очень быстрый (O(1)), так как используется массив.
  • Вставка/удаление в начало/середину — медленные (O(n)), так как требуют сдвига элементов.
  • Расширение массива — при заполнении создаётся новый массив (обычно в 1.5 раза больше), и все элементы копируются (O(n)).

LinkedList (двусвязный список)

ОперацияСложность (Big O)Пояснение
Добавление в конец (add(E e))O(1)Просто создаётся новый узел и связывается с last
Вставка по индексу (add(int index, E e))O(n)Поиск позиции (O(n)) + вставка (O(1))
Получение по индексу (get(int index))O(n)Требуется обход с начала или конца (оптимизируется для индексов ближе к краям)
Удаление по индексу (remove(int index))O(n)Поиск (O(n)) + удаление (O(1))
Поиск по значению (contains(E e))O(n)Линейный поиск (перебор всех узлов)
Удаление по значению (remove(Object o))O(n)Поиск (O(n)) + удаление (O(1))
Добавление в начало (addFirst(E e))O(1)Просто обновляются ссылки first и next
Удаление из начала (removeFirst())O(1)Просто обновляется ссылка first

Особенности:

  • Вставка/удаление в начало/конец — очень быстрые (O(1)), так как не требуют сдвига элементов.
  • Доступ по индексу (get/set) — медленный (O(n)), так как требует обхода списка.
  • Использование памяти — каждый элемент (Node) хранит 3 поля: item, next, prev (больше накладных расходов, чем у ArrayList).

Сравнительная таблица

ОперацияArrayListLinkedList
Доступ по индексуO(1)O(n)
Вставка в конецO(1)*O(1)
Вставка в началоO(n)O(1)
Вставка в серединуO(n)O(n) (поиск) + O(1) (вставка)
Удаление из началаO(n)O(1)
Удаление из концаO(1)O(1)
Поиск по значениюO(n)O(n)
  • В среднем O(1), но при расширении массива — O(n).

3. Когда что использовать?

ArrayList:

  • Частый доступ по индексу (например, get(i)).
  • Редкие вставки/удаления (или только в конец).
  • Пример: Хранение списка студентов для быстрого поиска по номеру в журнале.
    1
2
3

    ArrayList<String> students = new ArrayList<>();
students.add("Анна");  // O(1)
students.get(0);       // O(1)

LinkedList:

  • Частые вставки/удаления в начало/середину.
  • Реализация очереди/стека (например, Deque).
  • Пример: История действий в приложении с возможностью отмены (добавление и удаление с обоих концов).
    1
2
3

    LinkedList<String> history = new LinkedList<>();
history.addFirst("Action1");  // O(1)
history.removeLast();         // O(1)

4. Память и накладные расходы

  • ArrayList:
    • Требует меньше памяти на элемент (только данные + запас массива).
    • Избыточный размер массива может привести к “пустому” расходу памяти.
  • LinkedList:
    • Каждый элемент хранит 2 ссылки (prev и next), что увеличивает потребление памяти на 16-24 байта на элемент (в 64-битной JVM).
    • Нет избыточного выделения памяти.

5. Примеры операций

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

1
2
3
4
5

  // ArrayList: O(n)
  list.add(5, "element");  // Сдвигает все элементы правее 5-й позиции

  // LinkedList: O(n) на поиск позиции + O(1) на вставку
  list.add(5, "element");  // Быстрее для больших списков, если индекс ближе к началу/концу

_Итерация_

  • Для ArrayList итерация быстрее (данные расположены в памяти последовательно, что дружественно к кэшу процессора).
  • Для LinkedList итерация медленнее (переход по ссылкам, нет локалиности данных).
1
2
3
4
5

  // Быстрее для ArrayList
  for (String item : arrayList) { ... }

  // Медленнее для LinkedList
  for (String item : linkedList) { ... }

Как расширяется ArrayList при достижении capacity?

  1. Начальная емкость (Initial Capacity)
    • По умолчанию ArrayList создаётся с начальной емкостью 10:
      1

       ArrayList<Integer> list = new ArrayList<>(); // capacity = 10
    • Можно задать свою начальную емкость:
      1

       ArrayList<Integer> list = new ArrayList<>(100); // capacity = 100
  2. Что происходит при добавлении элементов? Когда массив заполняется, ArrayList автоматически расширяется:
    • Проверка заполненности:
      • При вызове add(element) проверяется, хватает ли места:
        1
2
3

        if (size + 1 > elementData.length) {
    grow(); // Вызов метода расширения
}
    • Расширение (grow()):
    • Новый размер = старый размер * 1.5 (в OpenJDK) или старый размер + (старый размер » 1).
    • Например:
      • Было 10 → станет 15.
      • Было 15 → станет 22 (15 + 7).
    • Внутри создаётся новый массив большего размера, и все элементы копируются в него:
      1
2

      int newCapacity = oldCapacity + (oldCapacity >> 1); // Увеличение в ~1.5 раза
elementData = Arrays.copyOf(elementData, newCapacity);

  3. Пример процесса расширения Допустим, у нас ArrayList с начальной capacity = 3:

    ОперацияРазмер (size)Вместимость (capacity)Что происходит?
    list.add(1)13Массив [1, null, null]
    list.add(2)23Массив [1, 2, null]
    list.add(3)33Массив [1, 2, 3] (заполнен)
    list.add(4)44 + (4 » 1) = 6Новый массив [1, 2, 3, 4, null, null]
  4. Как избежать частых расширений? Если известно примерное количество элементов, лучше сразу задать capacity:
    1

     ArrayList<Integer> list = new ArrayList<>(1000); // Минимизирует ресайзы
  5. Итог
    • ArrayList расширяется в ~1.5 раза при заполнении.
    • Копирование элементов при расширении требует времени (O(n)).
    • Оптимизация: задавайте начальный размер, если знаете примерное количество элементов.
Java
faq
This post is licensed under CC BY 4.0 by the author.