Sea*_*ill 1 java algorithm linked-list time-complexity
我知道链接列表插入是由于指针的简单重新排列而导致的常量时间,但这不需要知道您正在进行插入的元素吗？
访问该元素需要线性搜索.那么为什么我们不首先说插入仍然受到线性搜索瓶颈的约束？
编辑:我不是在谈论头部或尾部附加,而是介于两者之间的插入.
是的,它需要已经有一个节点,您要在其旁边插入.
那么为什么我们不首先说插入仍然受到线性搜索瓶颈的约束？
因为不一定是这种情况,如果你可以安排一些事情,你实际上知道插入点(不仅仅是索引,而是节点).
显然你可以在前面或末尾"插入",这似乎有点像作弊,它延伸了"插入"一词的含义.但考虑另一种情况:当你附加到列表时,在某些时候你会记住一个节点.您选择的任何节点,使用任何标准来选择您想要的节点.然后,您可以稍后在该节点之后或之前轻松插入.
这听起来像是一个非常"建构"的情况,因为它是.对于更像这样的实际情况(但不完全相同),您可以查看Dancing Links算法.