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

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

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