List<String> myList; // Объявление переменной интерфейсного типа
myList = new ArrayList<>(); // Работаем с динамическим массивом
// ... позже в коде ...
myList = new LinkedList<>(); // Теперь работаем со связным списком

// Примерно так выглядит внутри ArrayList
public class ArrayList<E> {
    private Object[] elementData; // Внутренний массив
    private int size; // Текущее количество реальных элементов
    // ...
}

// Примерная структура узла
private static class Node<E> {
    E item;        // Данные
    Node<E> next;  // Ссылка на следующий узел
    Node<E> prev;  // Ссылка на предыдущий узел
    // ...
}

// Внутренняя логика ArrayList.get(index)
public E get(int index) {
    // ... проверка индекса ...
    return (E) elementData[index]; // Прямое обращение по индексу массива
}

// Примерная логика (упрощенно). Чтобы найти узел с индексом 5:
Node<E> x = first;
for (int i = 0; i < 5; i++) { // Нужно сделать 5 итераций
    x = x.next;
}
return x.item;

// При вставке в середину/начало в ArrayList
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = newElement;
size++;

// Вставка `newNode` между `prevNode` и `currentNode`
newNode.prev = prevNode;
newNode.next = currentNode;
prevNode.next = newNode;
currentNode.prev = newNode;

// Упрощенная логика расширения
private void ensureCapacity(int minCapacity) {
    if (minCapacity > elementData.length) {
        int newCapacity = elementData.length + (elementData.length >> 1); // Увеличение на 50%
        if (newCapacity < minCapacity) {
            newCapacity = minCapacity;
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}
Эта стратегия гарантирует, что хотя отдельные операции добавления могут быть дорогими (при необходимости расширения), средняя стоимость большого количества операций добавления остается O(1).

System.arraycopy(elementData, index, elementData, index + 1, size - index);