ArrayList vs LinkedList

ArrayList построен на основе динамического массива. Он обеспечивает очень быстрый доступ к элементам по индексу — O(1), так как нужный элемент вычисляется по его позиции в памяти. Добавление в конец обычно выполняется за O(1) (амортизированно), но при переполнении массива создаётся новый большего размера и все элементы копируются. Вставка или удаление в начале и середине требуют сдвига элементов, поэтому имеют сложность O(n).

LinkedList реализован как двусвязный список: каждый элемент хранит ссылки на предыдущий и следующий узлы. Добавление или удаление в начале и конце выполняются за O(1). Однако поиск элемента по индексу требует последовательного обхода списка, поэтому доступ к началу — O(1), а к середине и концу — O(n). Из-за дополнительных ссылок LinkedList расходует больше памяти и хуже использует кэш процессора, поэтому в большинстве современных приложений предпочтение отдают ArrayList.