我正在尝试编写自己的（尽可能接近标准）单链表实现。但是我想知道人们对这样一个列表的期望时间复杂度是多少？
特别是对于插入，我想知道我应该如何实现它。我读过互联网上的一些地方，有人说插入是 O(1)，而另一些人说 O(n) - 都同意双链表是 O(1)。但是我认为 O(1) 也是单链表的情况吗？
只要您知道前一个节点，您只需让前一个节点指向新的新节点，新节点将指向前一个节点最初指向的位置。
这让我想知道人们期望insert如何表现？通常它在给定的迭代器之前插入元素。然而，使用单链表很难做到这一点（必须O(n)花费时间来获取前面的元素，然后使用上述方法）。insert在这样的列表中，在当前迭代器后面放置项目是否很常见？或者 - 可能更好 - 是否有另一个常见的功能？
插入的复杂性取决于您需要做什么。如果您知道前一个节点（实际上，您只需要一个合适的句柄来更改前一个节点的“下一个指针”），那么复杂度是O(1). 如果你需要找到插入的位置，复杂度是O(n).
关于期望，我希望它的insert()行为与双向链表的行为相同，但我也意识到你无法做到这一点：你要么需要不同的时间复杂度（找到前导节点），要么需要不同的迭代器失效语义（即，其他节点的迭代器失效）。我认为 C++ 2011std::forward_list类模板采用了不同的接口，但保留了迭代器有效性的保证。
简要解释为什么可以影响迭代器有效性：迭代器不必只知道当前节点。相反，它可以，例如，指向前任的next指针。当解引用迭代器时，它会首先解引用指向指针的next指针，然后解引用 this 指针以获取实际节点。作为回报，可以在迭代器前面插入，因为迭代器知道next要更新哪个指针。不幸的是，这意味着迭代器可能会失效，因为它们指向的指针可能已更改并且它们将引用不同的节点（当擦除节点时，迭代器可能已被移动为完全无效，尽管引用的节点仍然存在）。