Какая сложность получения элемента в середине в ArrayList?

Какая сложность получения элемента в середине в ArrayList

Доступ к элементу в середине ArrayList имеет O(1) временную сложность — точно так же как доступ к первому или последнему элементу.

Почему O(1)?

Это фундаментальное свойство массивов — random access. ArrayList хранит элементы в обычном Java массиве с индексированным доступом:

ArrayList<String> list = new ArrayList<>();
list.add("A");  // index 0
list.add("B");  // index 1
list.add("C");  // index 2 — середина
list.add("D");  // index 3

String middle = list.get(2); // O(1)

Вычисление:

1. Вычисляется адрес: baseAddress + (index * elementSize)
2. Данные считываются из памяти Обе операции — O(1), независимо от индекса!

Все доступы в ArrayList — O(1)

ArrayList<String> list = new ArrayList<>();
for (int i = 0; i < 1_000_000; i++) {
    list.add("item" + i);
}

String first = list.get(0);         // O(1)
String middle = list.get(500_000);  // O(1)
String last = list.get(999_999);    // O(1)
String any = list.get(12345);       // O(1)

Сравнение со структурами данных

• ArrayList: O(1) для любого индекса
• LinkedList: O(n) для доступа к элементу в середине
• Array: O(1) для любого индекса
• HashMap: O(1) average case

LinkedList — ужас

LinkedList имеет O(n) для доступа к элементу в середине:

LinkedList<String> list = new LinkedList<>();
for (int i = 0; i < 1_000; i++) {
    list.add("item" + i);
}

// Плохо — O(n)!
String middle = list.get(500);

// Внутренний алгоритм:
// 1. Начать с head (index 0)
// 2. Пройти 500 ссылок
// 3. Получить значение
// Сложность: O(n) где n = 500

Практическое сравнение

public class AccessPerformanceTest {
    
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        LinkedList<Integer> linkedList = new LinkedList<>();
        
        for (int i = 0; i < 100_000; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }
        
        testAccess("ArrayList", arrayList);
        testAccess("LinkedList", linkedList);
    }
    
    static void testAccess(String name, List<Integer> list) {
        int[] indices = {0, 50_000, 99_999};
        
        for (int index : indices) {
            long start = System.nanoTime();
            Integer value = list.get(index);
            long duration = System.nanoTime() - start;
            
            System.out.printf("%s[%d]: %d ns%n", name, index, duration);
        }
    }
}

// Результаты:
// ArrayList[0]: ~50 ns
// ArrayList[50000]: ~50 ns (тот же результат!)
// ArrayList[99999]: ~50 ns (тот же результат!)
//
// LinkedList[0]: ~100 ns
// LinkedList[50000]: ~1000000 ns (O(n))
// LinkedList[99999]: ~2000000 ns (O(n))

Почему именно O(1)?

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

ArrayList:
elementData = [item0, item1, item2, item3, item4, ...]
адреса:      [1000,  1008,  1016,  1024,  1032,  ...]

Для доступа к item2:
1. Адрес = baseAddress + (2 * sizeof(reference))
2. Адрес = 1000 + (2 * 8) = 1016
3. Прочитать данные по адресу 1016
4. Всё это — константное время O(1)

LinkedList в памяти:

LinkedList:
item0 → item1 → item2 → item3 → item4 → ...

Для доступа к item2:
1. Начать с head = item0
2. Перейти по ссылке → item1
3. Перейти по ссылке → item2
4. Требует проход, O(n)

Вывод: используй ArrayList для случайного доступа

// Плохо
LinkedList<String> list = new LinkedList<>();
for (int i = 0; i < list.size(); i++) {
    String element = list.get(i); // O(n) для каждого доступа
    // Полная сложность: O(n²)
}

// Хорошо
ArrayList<String> list = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
    String element = list.get(i); // O(1) для каждого доступа
    // Полная сложность: O(n)
}

// Или итератор для LinkedList
LinkedList<String> list = new LinkedList<>();
for (String element : list) {
    // Обработка — O(n) всего
}

Практические рекомендации

• ArrayList для случайного доступа по индексу — O(1)
• LinkedList только если нужны частые вставки/удаления в начало/конец
• Никогда не используй LinkedList.get(i) в циклах
• Используй итераторы для LinkedList если нужна итерация