Производительность удаления элемента в LinkedList Java
Всем привет! Все говорят,что удаление элемента в LinkedList происходит за константное время? Как это происходит?? С помощью метода remove(index) это явно не константное время,так как сначала надо найти этот индекс ,т.е.это уже O(n). Какой то блогер говорит ,что реализовать удаление за константное время можно только с использованием итератора.Но все же итератор ведь тоже проходит по всем элементам т.е.чем больше элементов ,тем больше времени требуется(опять O(n) ). Не могли бы объяснить?
Ответы (1 шт):
Автор решения: Nowhere Man
→ Ссылка
Вероятно, подразумеваются некие оговорки:
- либо удаление первого или последнего элемента в связанном списке
- либо не учитывая время поиска элемента по значению / индексу.
Итак, что следует помнить о LinkedList, решая, использовать ли данную коллекцию:
- не синхронизирована;
- позволяет хранить любые объекты, в том числе
nullи повторяющиеся;- за константное время O(1) выполняются операции вставки и удаления первого и последнего элемента, операции вставки и удаления элемента из середины списка (не учитывая время поиска позиции элемента, который осуществляется за линейное время);
- за линейное время O(n) выполняются операции поиска элемента по индексу и по значению.