Что будет, если вставить элемент в начало в ArrayList

Что будет, если вставить элемент в начало в ArrayList?

Вставка элемента в начало ArrayList — это дорогостоящая операция, которая требует перемещения всех существующих элементов на одну позицию вперёд. Это имеет серьёзные последствия для производительности.

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

ArrayList основан на массиве, поэтому для вставки элемента нужно:

// Упрощённое представление ArrayList
public class ArrayList<E> {
    private Object[] elementData; // Внутренний массив
    private int size;              // Текущее количество элементов
    
    public void add(int index, E element) {
        // 1. Проверяем место в массиве
        ensureCapacity(size + 1);
        
        // 2. Перемещаем элементы на одну позицию вперёд
        System.arraycopy(elementData, index, 
                        elementData, index + 1, 
                        size - index);
        
        // 3. Вставляем новый элемент
        elementData[index] = element;
        size++;
    }
}

2. Визуальный пример вставки в начало

Исходный ArrayList (size=5):
[10, 20, 30, 40, 50]
 
0   1   2   3   4

--- Хотим вставить элемент 100 в начало (index=0) ---

Шаг 1: Проверяем место, если нужно расширяем массив
Шаг 2: Перемещаем все элементы на одну позицию вперёд

[10, 20, 30, 40, 50, ?]
 ↓   ↓   ↓   ↓   ↓
[10, 20, 30, 40, 50]  → Копируем в:
     [10, 20, 30, 40, 50, ?]

Шаг 3: Вставляем 100 в позицию 0

[100, 10, 20, 30, 40, 50]
  0   1   2   3   4   5

3. Полный процесс вставки в начало

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

// Текущее состояние: [10, 20, 30, 40, 50]
// size = 5

list.add(0, 100); // Вставляем в начало

// Что происходит:
// 1. ensureCapacity(6) — проверяем, хватает ли места
// 2. System.arraycopy(array, 0, array, 1, 5)
//    Копируем элементы от позиции 0 на 5 позиций
//    array[1..5] = array[0..4]
// 3. array[0] = 100
// 4. size = 6

// Результат: [100, 10, 20, 30, 40, 50]

4. Сложность операции: O(n)

Вставка в начало имеет линейную сложность, что означает, что время выполнения пропорционально количеству элементов:

public class ArrayListPerformanceTest {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        
        // Тест 1: Вставка в конец (быстро)
        long start = System.nanoTime();
        for (int i = 0; i < 100_000; i++) {
            list.add(i); // Добавляем в конец: O(1) амортизированная
        }
        long endTime = System.nanoTime();
        System.out.println("Add at end: " + (endTime - start) / 1_000_000 + "ms");
        // Результат: ~5-10ms
        
        // Тест 2: Вставка в начало (медленно)
        start = System.nanoTime();
        for (int i = 0; i < 10_000; i++) { // Только 10_000, а не 100_000!
            list.add(0, i); // Добавляем в начало: O(n)
        }
        endTime = System.nanoTime();
        System.out.println("Add at start: " + (endTime - start) / 1_000_000 + "ms");
        // Результат: ~500-1000ms (!)
    }
}

5. Анализ сложности для разных позиций

Вставка элемента в ArrayList размером N:

Позиция 0 (начало):     O(n)     Нужно сдвинуть N элементов
Позиция N/2 (середина): O(n/2)   Нужно сдвинуть N/2 элементов
Позиция N (конец):      O(1)     Не нужно ничего сдвигать

Время выполнения:

[████████████] ← O(1)   (конец)
[██████]      ← O(n/2)  (середина)
[□]           ← O(n)    (начало)

6. Проблемы с вставкой в начало

Проблема 1: Создание лишних копий данных

ArrayList<String> names = new ArrayList<>();
names.add("Alice");
names.add("Bob");
names.add("Charlie");
names.add("Diana");

// Нужно добавить в начало 1000 новых элементов
for (int i = 0; i < 1000; i++) {
    names.add(0, "Person" + i);
    // Каждая вставка перемещает существующие элементы!
    // После 1000 итераций, original 4 элемента скопированы тысячи раз
}

// Это ОЧЕНЬ неэффективно!

Проблема 2: Деградация памяти

Вставляем в начало 10 000 раз в цикле:

Итерация 1:  [x]              Перемещение 0 элементов
Итерация 2:  [x, x]           Перемещение 1 элемента
Итерация 3:  [x, x, x]        Перемещение 2 элементов
...
Итерация 10000: [x, x, ..., x] Перемещение 9999 элементов

Общее количество копирований:
0 + 1 + 2 + ... + 9999 = (9999 * 10000) / 2 = ~50 миллионов операций!

7. Правильный способ: LinkedList

Для частых вставок в начало нужно использовать LinkedList, который имеет O(1) вставку в начало:

// ❌ Плохо: ArrayList
ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 10_000; i++) {
    arrayList.add(0, i); // O(n) каждый раз
}
// Время: ~500ms для 10_000 элементов

// ✅ Хорошо: LinkedList
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 10_000; i++) {
    linkedList.addFirst(i); // O(1) каждый раз
}
// Время: ~1ms для 10_000 элементов

// Разница: 500x раз быстрее!

8. Внутреннее устройство LinkedList

public class LinkedList<E> {
    private class Node {
        E data;
        Node next;
        Node prev;
        
        Node(E data) {
            this.data = data;
        }
    }
    
    private Node first; // Указатель на первый узел
    private Node last;  // Указатель на последний узел
    private int size;
    
    // Вставка в начало: O(1)
    public void addFirst(E element) {
        Node newNode = new Node(element);
        
        if (first == null) {
            first = last = newNode;
        } else {
            newNode.next = first;   // Один из указателей
            first.prev = newNode;   // Два из указателей
            first = newNode;        // Один из указателей
        }
        
        size++;
        // Всего 3-4 операции, независимо от размера списка!
    }
}

// Визуально:
//
// Было:  first → [10] → [20] → [30] → last
//
// Добавляем 5 в начало:
//
// Стало:  first → [5] → [10] → [20] → [30] → last
//                  ↑
//             Только обновляем указатели!

9. Сравнение ArrayList vs LinkedList

public class ListPerformanceComparison {
    public static void main(String[] args) {
        int iterations = 10_000;
        
        // ArrayList
        long start = System.nanoTime();
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < iterations; i++) {
            arrayList.add(0, i);
        }
        long arrayListTime = System.nanoTime() - start;
        
        // LinkedList
        start = System.nanoTime();
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < iterations; i++) {
            linkedList.addFirst(i);
        }
        long linkedListTime = System.nanoTime() - start;
        
        System.out.println("ArrayList: " + (arrayListTime / 1_000_000) + "ms");
        System.out.println("LinkedList: " + (linkedListTime / 1_000_000) + "ms");
        System.out.println("Ratio: " + (arrayListTime / linkedListTime) + "x");
    }
}

// Типичный результат:
// ArrayList: 800ms
// LinkedList: 2ms
// Ratio: 400x раз медленнее!

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

// Сценарий 1: Много вставок в начало
if (needsFrequentPrependOperations) {
    list = new LinkedList<>(); // Используем LinkedList
} else {
    list = new ArrayList<>();  // Используем ArrayList
}

// Сценарий 2: Нужно добавить элементы в начало один раз
ArrayList<Integer> result = new ArrayList<>();

// ❌ Плохо: вставляем в начало 100 раз
for (int i = 0; i < 100; i++) {
    result.add(0, i);
}

// ✅ Хорошо: добавляем в конец, потом разворачиваем
ArrayList<Integer> temp = new ArrayList<>();
for (int i = 0; i < 100; i++) {
    temp.add(i);
}
Collections.reverse(temp);
result.addAll(temp);

// ✅ Или используем LinkedList для построения
LinkedList<Integer> temp2 = new LinkedList<>();
for (int i = 0; i < 100; i++) {
    temp2.addFirst(i); // O(1)
}
result.addAll(temp2);

// ✅ Или используем ArrayDeque (очень быстро)
ArrayDeque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < 100; i++) {
    deque.addFirst(i); // O(1)
}
result.addAll(deque);

11. Таблица сравнения операций

Итоговое резюме

Что происходит при вставке элемента в начало ArrayList:

1. Все существующие элементы перемещаются на одну позицию вперёд
2. Используется System.arraycopy() — дорогостоящая операция
3. Сложность O(n) — зависит от размера списка
4. Для вставок в начало используйте LinkedList — O(1) вместо O(n)
5. Для случайного доступа используйте ArrayList — O(1) вместо O(n) в LinkedList

Выбор структуры данных критичен для производительности приложения!