Коллекции trainee
Что такое Сравни ArrayList и LinkedList по сложности?
Ответ
Доступ по индексу: ArrayList O(1), LinkedList O(n) (нужно идти от головы или хвоста). Вставка в конец: ArrayList амортизированный O(1), LinkedList O(1). Вставка в середину: ArrayList O(n) (сдвиг элементов), LinkedList O(1), только если итератор уже стоит на нужном узле (иначе поиск позиции O(n)).
Разбор: ArrayList даёт доступ по индексу за O(1) (массив), но вставка в середину O(n) из-за сдвига; LinkedList — наоборот: доступ по индексу O(n) (обход от головы/хвоста), а вставка/удаление по уже найденной позиции O(1). Ловушка: у LinkedList вставка в середину сама по себе O(1), только если итератор уже стоит на нужном узле — поиск этой позиции всё равно O(n). Бинарный поиск к неотсортированному списку не применяется, и узлы LinkedList не хранят свои индексы.
Хочешь так же по своей компании — с вопросами по грейдам и задачами? Закажи гайд или забери свежее в Telegram.