Какова алгоритмическая сложность основных операций в ArrayList?

Алгоритмическая сложность операций в ArrayList

ArrayList — это динамический массив на основе обычного массива Java. Его производительность зависит от типа операции.

Таблица сложности основных операций

Подробный анализ основных операций

1. get(int index) — O(1)

Получение элемента по индексу — это самая быстрая операция:

ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

String element = list.get(1);  // O(1) — прямой доступ к массиву
System.out.println(element);   // B

Внутренне ArrayList хранит элементы в обычном массиве, поэтому доступ = просто обращение к array[index].

2. add(E element) — O(1) амортизированная

Добавление элемента в конец обычно быстро, но иногда требует расширения:

ArrayList<Integer> list = new ArrayList<>();
list.add(1);  // O(1) — добавляется в конец
list.add(2);  // O(1)
list.add(3);  // O(1)

Когда capacity переполняется, ArrayList создает новый массив большего размера (обычно в 1.5 раза) и копирует элементы:

// Логика ArrayList примерно такая:
public void add(E element) {
    if (size == capacity) {
        // Создаем новый массив большего размера (O(n))
        capacity *= 1.5;
        E[] newArray = new E[capacity];
        System.arraycopy(elementData, 0, newArray, 0, size);  // копирование O(n)
        elementData = newArray;
    }
    elementData[size++] = element;  // O(1)
}

Однако это редко, поэтому амортизированная сложность = O(1).

3. add(int index, E element) — O(n)

Вставка в определенную позицию требует сдвига всех элементов справа:

ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

list.add(1, "X");  // O(n) — сдвигаем "B" и "C" вправо
// Результат: [A, X, B, C]

Визуализация:

До:        [A, B, C, null]
После:     [A, X, B, C]
               ↑ вставка
                 ↓ сдвиг

Вставка в начало (index=0) — самая плохая: сдвигаются все n элементов.

4. remove(int index) — O(n)

Удаление элемента требует сдвига остальных влево:

ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

list.remove(1);  // O(n) — сдвигаем "C" влево
// Результат: [A, C]

Визуализация:

До:        [A, B, C]
После:     [A, C, null]
              ↑ удаление
               ↓ сдвиг

5. remove(Object o) и contains(Object o) — O(n)

Эти методы требуют поиска элемента в массиве:

ArrayList<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(30);

boolean found = list.contains(20);  // O(n) — проверяет все элементы
list.remove(Integer.valueOf(20));    // O(n) — поиск + удаление

Практический пример

import java.util.*;

public class ArrayListPerformance {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        
        // O(1) амортизированная
        for (int i = 0; i < 1000000; i++) {
            list.add(i);  // быстро
        }
        
        // O(1)
        int first = list.get(0);        // очень быстро
        int last = list.get(999999);    // очень быстро
        int middle = list.get(500000);  // очень быстро
        
        // O(n)
        list.add(0, -1);   // медленно — вставка в начало
        
        // O(n)
        list.remove(0);    // медленно — удаление с начала
        
        // O(n)
        list.contains(500000);  // медленно — поиск
    }
}

Сравнение с другими коллекциями

Оптимизация производительности

Плохо: вставка в начало

ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
    list.add(0, i);  // O(n) каждый раз! Итого O(n^2)
}

Хорошо: добавление в конец

ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
    list.add(i);  // O(1) амортизированная. Итого O(n)
}
Collections.reverse(list);  // если нужен обратный порядок

Хорошо: указание начального capacity

ArrayList<Integer> list = new ArrayList<>(10000);  // избегаем ресайзов
for (int i = 0; i < 10000; i++) {
    list.add(i);
}

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

Используй ArrayList если:

• Часто нужен доступ по индексу (get)
• Добавляешь элементы в конец
• Нужна быстрая итерация

НЕ используй ArrayList если:

• Часто вставляешь/удаляешь в начало/середину (используй LinkedList)
• Нужна быстрая работа с поиском (используй TreeSet или HashSet)
• Нужны отсортированные элементы с быстрым поиском (используй TreeSet)