Как и Interface List осуществляется доступ к элементам

Как через Interface List осуществляется доступ к элементам

Java List — это интерфейс, определяющий упорядоченную коллекцию. Доступ к элементам реализуется по-разному в зависимости от конкретной реализации.

List Interface

public interface List<E> extends Collection<E> {
    // Основные методы доступа:
    
    E get(int index);                    // O(1) или O(n) в зависимости от реализации
    E set(int index, E element);         // Замена элемента
    void add(int index, E element);      // Вставка
    E remove(int index);                 // Удаление
    int indexOf(Object o);               // Поиск индекса
    int lastIndexOf(Object o);           // Поиск с конца
    ListIterator<E> listIterator();      // Итератор с обоими направлениями
    List<E> subList(int from, int to);   // Подсписок
}

Основные реализации List

1. ArrayList — динамический массив

public class ArrayList<E> {
    private Object[] elementData;  // Внутренний массив
    private int size;              // Количество элементов
    
    public E get(int index) {
        if (index >= size) throw new IndexOutOfBoundsException();
        return (E) elementData[index];  // O(1) — прямой доступ!
    }
    
    public void add(E element) {
        if (size == elementData.length) {
            // Переразмеры массива (обычно в 1.5 раза)
            Object[] newArray = new Object[elementData.length * 3 / 2 + 1];
            System.arraycopy(elementData, 0, newArray, 0, size);
            elementData = newArray;
        }
        elementData[size++] = element;
    }
}

// Использование
List<String> list = new ArrayList<>();
list.add("first");    // O(1) амортизированное
list.add("second");
list.get(0);         // O(1) — очень быстро
list.remove(0);      // O(n) — требует сдвига элементов!

Характеристики ArrayList:

• get(index): O(1) — быстро
• add(element): O(1) амортизированное
• add(index, element): O(n) — нужен сдвиг
• remove(index): O(n) — нужен сдвиг
• Память: непрерывный массив

Когда использовать: частое чтение, редкие вставки/удаления

2. LinkedList — двусвязный список

public class LinkedList<E> {
    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 E get(int index) {
        // O(n) — нужно пройти по ссылкам!
        Node<E> node = getNode(index);
        return node.item;
    }
    
    private Node<E> getNode(int index) {
        if (index < size / 2) {
            Node<E> x = first;
            for (int i = 0; i < index; i++) {
                x = x.next;  // ← Проходим от начала
            }
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--) {
                x = x.prev;  // ← Проходим с конца (оптимизация!)
            }
            return x;
        }
    }
    
    public void addFirst(E e) {
        // O(1) — просто создать новый node
        Node<E> newNode = new Node<>(e);
        newNode.next = first;
        first.prev = newNode;
        first = newNode;
        size++;
    }
}

// Использование
List<String> list = new LinkedList<>();
list.add("a");       // O(1)
list.add(0, "first");  // O(n) для поиска индекса, O(1) для вставки
list.get(0);         // O(1) если индекс 0
list.get(5000);      // O(n) — требует прохода

Характеристики LinkedList:

• get(index): O(n) — нужно пройти
• add(0, element): O(1) — добавление в начало
• remove(0): O(1) — удаление из начала
• add(index, element): O(n) для поиска + O(1) для вставки
• Память: распределена по памяти

Когда использовать: частые вставки/удаления в начале/конце

3. CopyOnWriteArrayList — thread-safe ArrayList

public class CopyOnWriteArrayList<E> {
    private volatile Object[] array;
    
    public E get(int index) {
        return (E) array[index];  // O(1) — просто чтение
    }
    
    public void add(E element) {
        // Дорого: создать новый массив и скопировать
        synchronized (this) {
            Object[] newArray = new Object[array.length + 1];
            System.arraycopy(array, 0, newArray, 0, array.length);
            newArray[array.length] = element;
            array = newArray;
        }
    }
}

// Использование
List<String> threadSafeList = new CopyOnWriteArrayList<>();
threadSafeList.add("a");  // O(n) — копирует весь массив!
threadSafeList.get(0);    // O(1) — просто чтение

Когда использовать: многопоточное чтение, редкие изменения

Сравнение реализаций

• амортизированное ** O(1) если известна ссылка на node

Практический пример: выбор реализации

// ✅ Хорошо: ArrayList для случайного доступа
List<String> names = new ArrayList<>();
for (String name : largeDataset) {
    names.add(name);  // O(1) в конце
}
for (int i = 0; i < names.size(); i++) {
    System.out.println(names.get(i));  // O(1) быстро
}

// ❌ Плохо: LinkedList для случайного доступа
List<String> names = new LinkedList<>();
for (String name : largeDataset) {
    names.add(name);  // O(1) в конце
}
for (int i = 0; i < names.size(); i++) {
    System.out.println(names.get(i));  // O(n) медленно!
}

// ✅ Лучше: LinkedList для операций в начале
Queue<String> queue = new LinkedList<>();
queue.addFirst("priority");  // O(1)
queue.removeFirst();         // O(1)

// ✅ Правильно: итератор вместо get
for (String name : list) {  // Итератор
    System.out.println(name);  // O(1) для обеих реализаций
}

Итераторы

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");

// Итератор — универсальный способ доступа
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String item = it.next();  // O(1) для ArrayList, O(1) для LinkedList
    // (итератор оптимизирован для каждой реализации)
}

// ListIterator — двусторонний
ListIterator<String> lit = list.listIterator();
while (lit.hasNext()) {
    System.out.println(lit.next());  // Вперёд
}
while (lit.hasPrevious()) {
    System.out.println(lit.previous());  // Назад
}

// For-each loop (рекомендуется)
for (String item : list) {
    System.out.println(item);  // Автоматически использует оптимальный итератор
}

Внутренний механизм доступа

// Когда ты вызываешь list.get(5):

// ArrayList:
E get(int index) {
    return (E) elementData[index];  // Просто массив
}
// array[5] = memory_address + (5 * size_of_element)

// LinkedList:
E get(int index) {
    Node<E> x = getNode(index);
    return x.item;
}
// node = first; node = node.next; node = node.next; ...
// Прохождение 5 ссылок!

Benchmarking

List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();

// Заполнение
for (int i = 0; i < 100000; i++) {
    arrayList.add(i);
    linkedList.add(i);
}

// Случайный доступ
long start = System.nanoTime();
for (int i = 0; i < arrayList.size(); i++) {
    arrayList.get(i);  // ~100мкс для 100k элементов
}
long arrayTime = System.nanoTime() - start;

start = System.nanoTime();
for (int i = 0; i < linkedList.size(); i++) {
    linkedList.get(i);  // ~200ms для 100k элементов!
}
long linkedTime = System.nanoTime() - start;

System.out.println(linkedTime / arrayTime);  // ~2000x медленнее!

Best Practices

// ✅ Хорошие практики
List<String> list = new ArrayList<>();  // Используй ArrayList по умолчанию

// Используй итератор для обхода
for (String item : list) {  // or iterator()
    process(item);
}

// Используй LinkedList если часто добавляешь/удаляешь в начале
Queue<Task> queue = new LinkedList<>();
queue.addFirst(new Task());

// ❌ Избегай
List<String> list = new LinkedList<>();  // Без необходимости
for (int i = 0; i < list.size(); i++) {  // Очень медленно!
    list.get(i);
}

Вывод: List интерфейс позволяет абстрагироваться от реализации, но для оптимизации важно понимать сложность операций каждой реализации.