我已经尝试确认链接列表插入的运行时间,似乎有两个不同的答案.
为了在链接列表的末尾插入一个元素,我认为它需要O(n),因为它必须遍历到列表的末尾才能访问尾部.但我见过的一些答案是O(1)？他们是否假设所有链表都实现了指向尾部的指针？如果是这样,这是可接受的假设吗？
其次,有些地方还建议在链表中间插入一个元素是O(1),由于遍历到列表中间插入它的相同推理,我很困惑.
有人可以澄清一下吗？谢谢.
language-agnostic algorithm big-o
algorithm ×1
big-o ×1
language-agnostic ×1