Почему Time Complexity для add() в sorted LinkedList - O(n)?
Столкнулся с сайтом вопрос-ответ. Нашел вот такую цитату:
Какое худшее время работы метода add() для LinkedList?
Ответ
O(N) - будет при добавление элемента в отсортированный список, а также при добавлении элемента с помощью метода add(index, value).
Абсолютно не понял, какой отсортированный список может быть в LinkedList? Только если мы сами его будем сортировать, но как наша сортировка тогда вливает на метод add()? Выходит, добавление элементов в LinkedList ( кроме add(index, value ) будет всегда O(1).
Буду очень рад, если вы меня поправите.
Ответы (1 шт):
Автор решения: Igor
→ Ссылка
Для добавления нового элемента в сортированный связанный список нужно найти место куда его добавлять, то есть в худшем случае - пройти по всему списку.