Какая сложность операций вставки и удаления в ArrayList и LinkedList в Java

Что проверяют

Знаете ли вы оценки и понимаете ли, почему LinkedList на практике почти всегда проигрывает.

Как отвечать

ArrayList это массив:

• доступ по индексу O(1);
• добавление в конец O(1) амортизированно (при нехватке ёмкости массив увеличивается примерно в полтора раза и копируется, это O(n), но редко);
• вставка и удаление в середине O(n), потому что нужно сдвинуть хвост.

LinkedList это двусвязный список:

• доступ по индексу O(n): чтобы дойти до элемента, надо пройти по ссылкам;
• вставка и удаление по известному узлу O(1), например через итератор или в начало и конец;
• вставка и удаление по индексу O(n), потому что сначала нужно этот индекс найти.

Именно последний пункт и есть ловушка: list.add(i, x) у LinkedList не быстрее, чем у ArrayList, хотя «списки быстро вставляют» звучит убедительно.

Практика важнее теории: ArrayList почти всегда быстрее на реальных данных, потому что массив лежит в памяти подряд и отлично ложится на кэш процессора, а сдвиг элементов делается быстрым системным копированием. LinkedList тратит по два указателя на элемент и прыгает по памяти.

Когда LinkedList оправдан: почти никогда. Нужна очередь с двух концов, берут ArrayDeque, он быстрее и компактнее.

Где спотыкаются

Выбирают LinkedList ради «быстрой вставки», забывая про поиск позиции.

Считают доступ по индексу одинаковым.

Удаляют элементы в цикле по индексу и получают квадратичную сложность.

Не знают про ArrayDeque и используют LinkedList как очередь.