Para inserir / excluir um nó com um valor específico na DLL (lista duplamente vinculada), é necessário percorrer toda a lista para encontrar o local, portanto, essas operações devem ser O (n).

Se for esse o caso, como a lista STL (provavelmente implementada usando DLL) é capaz de fornecer essas operações em tempo constante?

Obrigado a todos por deixar claro para mim.