Почему к массивам всегда можно быстро обратиться?

Ответ: Быстрый доступ к элементам массива

Прямой ответ

Массивы позволяют быстро обратиться к любому элементу благодаря произвольному доступу (Random Access). Это возможно благодаря последовательному расположению элементов в памяти и формулировке адреса.

Как это работает на уровне памяти

Представление массива в памяти

Массив: int[] array = {10, 20, 30, 40, 50}

Память (адреса в байтах):
┌──────────┬──────────┬──────────┬──────────┬──────────┐
│ 0x1000   │ 0x1004   │ 0x1008   │ 0x100C   │ 0x1010   │
├──────────┼──────────┼──────────┼──────────┼──────────┤
│ 10       │ 20       │ 30       │ 40       │ 50       │
└──────────┴──────────┴──────────┴──────────┴──────────┘
 array[0]  array[1]  array[2]  array[3]  array[4]

Вычисление адреса элемента

Когда вы обращаетесь к элементу array[i], процессор вычисляет адрес:

Адрес элемента = base_address + (i * size_of_element)

Для int[] array = {10, 20, 30, 40, 50}:
base_address = 0x1000 (адрес первого элемента)
size_of_element = 4 байта (размер int)

array[0]: 0x1000 + (0 * 4) = 0x1000
array[1]: 0x1000 + (1 * 4) = 0x1004
array[2]: 0x1000 + (2 * 4) = 0x1008
array[3]: 0x1000 + (3 * 4) = 0x100C
array[4]: 0x1000 + (4 * 4) = 0x1010

Эта формула вычисляется процессором в одну операцию — O(1).

Временная сложность

Операция       Сложность   Время
─────────────────────────────────
Доступ array[i]   O(1)      1 операция
Поиск элемента    O(n)      линейное время
Вставка в конец   O(1)      1 операция
Вставка в середину O(n)     нужно сдвигать
Удаление          O(n)      нужно сдвигать

Пример доступа к элементам

int[] numbers = {10, 20, 30, 40, 50};

// ✅ Быстро - O(1), произвольный доступ
int first = numbers[0];      // Адрес = base + 0*4
int third = numbers[2];      // Адрес = base + 2*4
int last = numbers[4];       // Адрес = base + 4*4

// Все три обращения занимают одинаковое время
// независимо от позиции элемента

Сравнение с другими структурами

Массив - произвольный доступ (Random Access)

int[] array = {10, 20, 30, 40, 50};

// O(1) - мгновенно
int value = array[0];   // Быстро
value = array[100000];  // Тоже быстро (если в границах)

// Обращение к любому элементу занимает одинаковое время

Мемория:

┌───┬───┬───┬───┬───┐  ← Последовательно
│10 │20 │30 │40 │50 │  ← Доступ ко всем одинаково
└───┴───┴───┴───┴───┘

LinkedList - последовательный доступ (Sequential Access)

LinkedList<Integer> list = new LinkedList<>();
list.add(10); list.add(20); list.add(30); list.add(40); list.add(50);

// O(n) - нужно пройти от начала
int value = list.get(0);      // Быстро (уже там)
value = list.get(1);          // Чуть медленнее (прошли 1 шаг)
value = list.get(4);          // Самое медленное (прошли 4 шага)

Мемория:

10 → 20 → 30 → 40 → 50  ← Связанные узлы
↑                   ↑
Быстро            Медленно (нужно пройти 4 ссылки)

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

              │ Массив      │ LinkedList   │ HashMap
──────────────┼─────────────┼──────────────┼─────────────
Доступ [i]    │ O(1)        │ O(n)         │ O(1) avg
Поиск         │ O(n)        │ O(n)         │ O(1) avg
Вставка начало│ O(n)        │ O(1)         │ O(1) avg
Вставка конец │ O(1)        │ O(1)         │ O(1) avg
Удаление      │ O(n)        │ O(n)         │ O(1) avg
Память        │ Компактна   │ Больше       │ Больше

Почему именно быстро?

1. Непрерывный блок памяти

// Массив занимает одный непрерывный блок памяти
int[] array = new int[1000000];
// Память: 0x1000 - 0x3D0900 (4 МБ подряд)

// LinkedList - разбросана по памяти
LinkedList<Integer> list = new LinkedList<>();
// Узел 1: адрес 0x1000
// Узел 2: адрес 0x5000
// Узел 3: адрес 0x2000
// Нужно прыгать по памяти

2. Прямая формула вычисления адреса

// Процессор вычисляет за 1 операцию
array[i] → address = baseAddress + i * elementSize

// Это ассемблерный код:
// mov eax, [baseAddress + i * 4]  // Одна инструкция!

3. Кеширование процессора

Когда вы обращаетесь к array[0], процессор:
1. Загружает data в кеш L1
2. array[1], array[2], ... уже в кеше
3. Доступ к ним еще быстрее

Для LinkedList:
1. Загружает узел в кеш
2. Ссылка на следующий узел указывает на другой адрес
3. Cache miss, нужно снова из памяти
4. Медленнее

Практический пример производительности

public class ArrayVsListPerformance {
    public static void main(String[] args) {
        int size = 1000000;
        
        // Создание массива
        int[] array = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = i;
        }
        
        // Создание LinkedList
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
        
        // Тест доступа к случайным элементам
        long startArray = System.nanoTime();
        for (int i = 0; i < 100000; i++) {
            int index = (int) (Math.random() * size);
            int value = array[index];  // O(1)
        }
        long timeArray = System.nanoTime() - startArray;
        
        long startList = System.nanoTime();
        for (int i = 0; i < 100000; i++) {
            int index = (int) (Math.random() * size);
            int value = list.get(index);  // O(n)
        }
        long timeList = System.nanoTime() - startList;
        
        System.out.println("Array access: " + timeArray + " ns");
        System.out.println("List access: " + timeList + " ns");
        System.out.println("Ratio: " + (timeList / (double) timeArray) + "x");
        // LinkedList медленнее в 100+ раз!
    }
}

Выводы производительности

Для миллиона операций доступа:
- Массив: ~50 ms
- LinkedList: ~5000 ms (в 100 раз медленнее!)

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

Используйте Array когда:

• Нужен быстрый доступ по индексу
• Много операций доступа
• Размер известен и стабилен
• Критична производительность

int[] scores = new int[100];  // Быстрый доступ
for (int i = 0; i < scores.length; i++) {
    scores[i] = i * 10;
}

Используйте List когда:

• Нужны вставки/удаления в начало
• Размер часто меняется
• Доступ по индексу редкий

LinkedList<Integer> queue = new LinkedList<>();
queue.addFirst(1);   // O(1) в начало
queue.removeFirst(); // O(1) удаление с начала

Резюме

Массивы позволяют быстро (O(1)) обратиться к любому элементу благодаря:

1. Непрерывному расположению в памяти - все элементы подряд
2. Простой формуле адреса - адрес = base + index * size
3. Оборудованию процессора - формула вычисляется за одну операцию
4. Кешированию - элементы уже в кеше процессора

Это основная причина, почему массивы так быстры для доступа, но медленнее для вставки/удаления по сравнению с LinkedList.