java - 为什么我们说链表插入是常数时间？

Question

我知道由于指针的简单重新排列，链表插入是恒定时间的，但这不需要知道您要插入的元素吗？

访问该元素需要线性搜索。那么，为什么我们不说插入仍然首先受到线性搜索瓶颈的限制呢？

编辑:我不是在谈论头部或尾部追加，而是在两者之间的任何位置插入。

Answer 1

是的，它需要已经有一个您要插入的节点。

So why don't we say that inserts are still bound by a linear search bottleneck first?

因为这不是必然的情况，如果您可以安排您确实知道插入点(不仅是索引，还有节点)的事情。

显然你可以在前端或末尾“插入”，这似乎有点作弊，它稍微延伸了“插入”一词的含义。但请考虑另一种情况:当您向列表添加内容时，在某个时刻您记住了一个节点。只是您选择的任何节点，使用任何标准来选择您想要的节点。然后您可以稍后在该节点之后或之前轻松插入。

这听起来像是一个非常“构建”的情况，因为它确实如此。对于更像这样(但不完全是)的更实际的案例，您可以查看 Dancing Links 算法。