Какие реализации интерфейса List в Java существуют и как они влияют на производительность сортировки и доступа по индексу?

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

Понимаете ли вы, как ArrayList и LinkedList лежат в памяти и почему учебная асимптотика расходится с реальными замерами. Частый уточняющий вопрос: как именно сортируется LinkedList и что будет с циклом get(i) по нему.

Как отвечать

• ArrayList: массив Object[], доступ по индексу O(1), помечен интерфейсом RandomAccess. Добавление в конец амортизированно O(1): при переполнении ёмкость растёт в полтора раза с копированием. Вставка и удаление в середине O(n) через System.arraycopy, но память непрерывна, и это быстро;
• LinkedList: двусвязный список, get(i) O(n), проход идёт от ближайшего конца. Вставка O(1) только при уже найденной позиции, через ListIterator. Каждый узел это отдельный объект с двумя ссылками, отсюда промахи кэша процессора;
• CopyOnWriteArrayList: запись копирует весь массив, чтение без блокировок. Подходит для редко меняемых списков вроде слушателей;
• Vector: устаревший синхронизированный ArrayList, в новом коде не нужен;
• неизменяемые: List.of, Stream.toList().

Про сортировку: List.sort и Collections.sort для объектов используют TimSort, стабильный алгоритм O(n log n), быстрый на частично упорядоченных данных. Реализация по умолчанию в интерфейсе копирует элементы в массив, сортирует его и записывает обратно через ListIterator. ArrayList переопределяет метод и сортирует свой массив на месте. Асимптотика одинакова, разница в лишнем копировании. Массив примитивов Arrays.sort сортирует dual-pivot quicksort, он нестабилен, но для примитивов это неважно.

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

Советуют LinkedList «для частых вставок». На практике ArrayList почти всегда быстрее даже при вставке в середину: поиск позиции в связном списке сам по себе O(n), да ещё с узлами, разбросанными по куче.

Обходят LinkedList циклом по индексу с get(i). Каждый вызов идёт от края, и обход становится квадратичным. Для любых списков используйте for-each или итератор.

Уверены, что LinkedList сортируется медленнее из-за «перестановки узлов». Узлы не переставляются вообще: элементы копируются в массив, сортируются там и записываются обратно.