Какие знаешь структуры, которые позволяют эффективно добавлять элементы в конец коллекции?

Структуры данных для эффективного добавления элементов в конец коллекции

Добавление элементов в конец коллекции — одна из самых частых операций. Разные структуры данных предоставляют разную производительность для этой операции.

1. ArrayList (O(1) amortized)

ArrayList — самая распространённая структура для добавления элементов в конец.

List<String> list = new ArrayList<>();

// Добавление в конец (O(1) amortized)
list.add("A");      // O(1)
list.add("B");      // O(1)
list.add("C");      // O(1)

// Время от времени ArrayList растёт (копирование)
// Когда capacity = 10, следующий элемент вызывает resize на 15

Как это работает:

private static final int DEFAULT_CAPACITY = 10;
private Object[] elementData;
private int size;

public boolean add(E e) {
    ensureCapacityInternal(size + 1); // Проверка и resize при необходимости
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (minCapacity > elementData.length) {
        // Resize: новый размер = old * 1.5
        int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5x growth
        Object[] newArray = new Object[newCapacity];
        System.arraycopy(elementData, 0, newArray, 0, size);
        elementData = newArray;
    }
}

Производительность:

// Добавление 1,000,000 элементов
List<Integer> list = new ArrayList<>();
long start = System.currentTimeMillis();
for (int i = 0; i < 1_000_000; i++) {
    list.add(i); // O(1) amortized
}
long end = System.currentTimeMillis();
// Примерно 10-20 ms

Минусы:

• Удаление элементов из середины — O(n) (требует сдвига)
• Резкие "скачки" при resize (пусть и редко)

2. LinkedList (O(1) гарантировано)

LinkedList использует двусвязный список, добавление в конец всегда O(1).

LinkedList<String> list = new LinkedList<>();

// Добавление в конец (O(1) всегда)
list.add("A");      // O(1)
list.add("B");      // O(1)
list.add("C");      // O(1)

list.addLast("D");  // O(1) — явно в конец
list.addFirst("Z"); // O(1) — в начало

Как это работает:

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    // ...
}

private Node<E> first;
private Node<E> last;
private int size;

public boolean add(E e) {
    linkLast(e); // Просто создаёшь новый Node
    return true;
}

private void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(e, null, l);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
}

Минусы:

• Доступ по индексу — O(n) (нужно пройти по цепочке)
• Больше памяти (два pointer на каждый узел)
• Хуже с кэшем (nodes разбросаны по памяти)

LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 1_000_000; i++) {
    list.add(i);        // O(1) ✅
}
int value = list.get(500_000); // O(n) ❌ — очень медленно!

3. ArrayDeque (O(1), лучше чем LinkedList)

ArrayDeque — двусторонняя очередь на основе массива (резиновый массив).

Deque<String> deque = new ArrayDeque<>();

// Добавление в конец (O(1) amortized)
deque.add("A");        // O(1)
deque.addLast("B");    // O(1)
deque.push("Z");       // O(1) — в начало

// Быстрый доступ (в отличие от LinkedList)
String first = deque.getFirst(); // O(1)
String last = deque.getLast();   // O(1)

Как это работает:

private transient Object[] elements;
private transient int head;  // Индекс первого элемента
private transient int tail;  // Индекс последнего элемента

public void addLast(E e) {
    if (e == null) throw new NullPointerException();
    Object[] es = elements;
    es[tail] = e;              // Добавляем элемент
    tail = (tail + 1) & (es.length - 1); // Циклический сдвиг
    if (head == tail)          // Если массив полный
        doubleCapacity();      // Растяжение
}

Преимущества:

• O(1) добавление в начало и конец
• O(1) удаление из начала и конца
• O(1) доступ к первому и последнему элементу
• Лучше с кэшем чем LinkedList (всё в одном массиве)

4. Vector (устаревший, но похож на ArrayList)

Vector — синхронизированный ArrayList (потокобезопасный).

Vector<String> vector = new Vector<>();
list.add("A"); // O(1) amortized, но потокобезопасно

Минусы:

• Синхронизация замедляет операции
• Устаревший класс (используй Collections.synchronizedList())

List<String> syncList = Collections.synchronizedList(new ArrayList<>());
syncList.add("A"); // Потокобезопасное добавление

5. CopyOnWriteArrayList (для массивов с частым чтением)

List<String> list = new CopyOnWriteArrayList<>();

// Добавление (O(n) — копирует весь массив)
list.add("A"); // Медленно

// Чтение (O(1))
String s = list.get(0); // Быстро

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

• Частые чтения, редкие записи
• Небольшие коллекции

6. Собственная реализация с буфером

Для специальных нужд можно написать свою структуру:

public class RingBuffer<E> {
    private Object[] data;
    private int head = 0;
    private int tail = 0;
    private int size = 0;
    
    public RingBuffer(int capacity) {
        data = new Object[capacity];
    }
    
    // Добавление в конец (O(1))
    public void add(E element) {
        if (size == data.length) {
            resize();
        }
        data[tail] = element;
        tail = (tail + 1) % data.length;
        size++;
    }
    
    // Удаление из начала (O(1))
    public E remove() {
        if (size == 0) throw new NoSuchElementException();
        E element = (E) data[head];
        head = (head + 1) % data.length;
        size--;
        return element;
    }
    
    private void resize() {
        Object[] newData = new Object[data.length * 2];
        for (int i = 0; i < size; i++) {
            newData[i] = data[(head + i) % data.length];
        }
        data = newData;
        head = 0;
        tail = size;
    }
}

7. Сравнение производительности

public class CollectionBenchmark {
    public static void main(String[] args) {
        int iterations = 1_000_000;
        
        // ArrayList
        long start = System.nanoTime();
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < iterations; i++) {
            arrayList.add(i);
        }
        long arrayListTime = System.nanoTime() - start;
        
        // LinkedList
        start = System.nanoTime();
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < iterations; i++) {
            linkedList.add(i);
        }
        long linkedListTime = System.nanoTime() - start;
        
        // ArrayDeque
        start = System.nanoTime();
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < iterations; i++) {
            deque.addLast(i);
        }
        long dequeTime = System.nanoTime() - start;
        
        System.out.println("ArrayList: " + arrayListTime + " ns");
        System.out.println("LinkedList: " + linkedListTime + " ns");
        System.out.println("ArrayDeque: " + dequeTime + " ns");
    }
}
// Примерный результат:
// ArrayList: 5,000,000 ns (самый быстрый)
// ArrayDeque: 6,500,000 ns
// LinkedList: 15,000,000 ns

8. Таблица сравнения

*Из начала/конца **getFirst/getLast только

Рекомендации

1. Для добавления в конец: используй ArrayList (95% случаев)
2. Для двусторонней очереди: используй ArrayDeque
3. Для частых удалений из середины: рассмотри LinkedList
4. Избегай LinkedList если нужен случайный доступ по индексу
5. Потокобезопасность: используй Collections.synchronizedList(new ArrayList<>())
6. High performance: рассмотри собственную реализацию с ring buffer

Выводы

1. ArrayList — оптимальный выбор для добавления в конец (O(1) amortized)
2. ArrayDeque если нужна работа с обеими концами
3. LinkedList переоценен и медленнее ArrayList в большинстве случаев
4. ArrayDeque лучше LinkedList для очередей
5. Всегда профилируй, если перформанс критичен