Является ли сложность времени для вставки / удаления в двусвязном списке порядка O (n)?

Question

Чтобы вставить / удалить узел с определенным значением в DLL (двусвязный список), необходимо найти весь список, чтобы найти местоположение, следовательно, эти операции должны быть O (n).

Если это так, то почему список STL (наиболее вероятно, реализованный с использованием DLL) может обеспечивать эти операции в постоянное время?

Спасибо всем за разъяснения.

Answer 1

Вставка и удаление в известной позиции - это O (1).Тем не менее, нахождение этой позиции равно O (n), если только это не заголовок или конец списка.

Когда мы говорим о сложности вставки и удаления, мы обычно предполагаем, что уже знаем, где это произойдет.

Answer 2

Это не так.Методы STL переводят итератор в позицию, в которой должна быть вставка, поэтому, строго говоря, они O(1), потому что вы задаете им позицию.Тем не менее, вы все равно должны найти положение в O(n).

Answer 3

Удаление произвольного значения (а не узла) действительно будет O (n), так как потребуется найти значение.Удаление узла (т. Е. Когда вы начинаете, зная, что узел) - это O (1).

Вставка на основе значения - например, вставка в список sorted - будет O (n),Если вы вставляете после или до того, как существующий известный узел имеет значение O (1).

Вставка в начало или конец списка всегда будет O (1) - потому что это просто особые случаи выше.