在数据结构中，我们说在单向链表中将元素推到节点之前是O(n(操作！ 由于没有向后指针，我们必须一直遍历元素才能到达要在新元素之前添加的键。因此，它具有线性运行时间。 然后，当我们引入双向链表时，我们说问题已经解决，现在因为我们在两个方向上都有指针推动，所以在成为常数时间操作 O(1( 之前。 我理解其中的逻辑，但仍然让我感到困惑！由于我们没有对列表元素的恒定时间访问，为了找到我们之前要添加的元素，我们必须遍历前一个元素才能到达那里！的确，在双向链表中，现在实现add-before命令的速度更快，但是，找到感兴趣的键的操作仍然是O(n(！那为什么我们说双链表之前 add 的操作变成 O(1(？
谢谢
在C++中，std：：list：：insert(( 函数采用迭代器来指示插入的位置。 这意味着调用方已经有这个迭代器，并且插入操作不执行搜索，因此在恒定时间内运行。
但是，find(( 算法是线性的，并且是搜索列表元素的常规方法。 如果需要查找+插入，则组合为 O(n(。
但是，不需要在插入之前进行搜索。 例如，如果您有一个缓存的(有效的(迭代器，则可以在常量时间内插入(或删除(与其对应的元素。