我知道链表插入是常量时间由于指针的简单重排，但这不需要知道你正在做插入的元素吗?
并且访问该元素需要线性搜索。那么为什么我们不先说插入仍然受到线性搜索瓶颈的约束呢?
编辑:我不是在谈论头部或尾部附加，而是在两者之间的任何地方插入。
是的，它需要已经有一个节点，你要插入旁边。
那么为什么我们不首先说插入仍然受到线性搜索瓶颈的约束呢?
因为这并不一定是的情况，如果你能安排一些事情，使你实际上知道插入点(不仅仅是索引，还有节点)
显然你可以"插入"在前面或后面，这似乎有点作弊，它延伸了单词"插入"的意思。但是考虑另一种情况:当您向列表添加时，在某个时刻您记住了一个节点。就是你选择的任何节点，使用任何条件选择你想要的节点。然后，您可以轻松地在该节点之后或之前插入。
这听起来像是一个非常"构造"的情况，因为它是。对于一个更实际的情况，与此非常相似(但不完全相同)，您可以查看Dancing Links算法。
为什么我们说链表插入是常数时间?
因为插入操作是常数时间。
注意定位插入的位置并不被认为是insert操作本身的一部分。这将是一个不同的操作，它可能是也可能不是常数时间，例如，如果包含搜索时间，则得到:
- 插入:Constant
- 在尾部插入:Constant
- 插入到当前元素之前，同时迭代1: Constant
- 插入索引位置:线性
1)假设你正在迭代
相比之下，ArrayList的插入操作是线性时间。如果包含搜索时间，则得到:
- 插入头:线性
- 尾部插入:常数(平摊)
- 插入到当前元素之前，同时迭代1: 线性
- 插入索引位置:线性
以下两个操作不同:
-
操作A:插入链表
-
操作B:在链表中的特定位置插入
操作A可以在O(1)中实现。新元素可以插入head(或tail，如果维护和需要)。
操作B包括查找，然后插入。查找部分是O(n)。插入方法如上所述，即O(1)。但是，如果将查找结果作为输入提供，例如，如果有像
Node * Find(Node * head, int find_property);
Node * InsertAfter(Node * head, Node * existing_node, Node * new_node);
则操作的插入部分为O(1)