Tro*_*roy 8 language-agnostic algorithm big-o
我已经尝试确认链接列表插入的运行时间,似乎有两个不同的答案.
为了在链接列表的末尾插入一个元素,我认为它需要O(n),因为它必须遍历到列表的末尾才能访问尾部.但我见过的一些答案是O(1)？他们是否假设所有链表都实现了指向尾部的指针？如果是这样,这是可接受的假设吗？
其次,有些地方还建议在链表中间插入一个元素是O(1),由于遍历到列表中间插入它的相同推理,我很困惑.
有人可以澄清一下吗？谢谢.
Amn*_*non 14
如果您有指向要插入项目的节点的指针,则插入到链接列表是O(1).查找此节点可能是O(n),具体取决于您要执行的操作.
如果你保留一个指向列表尾部的指针,那么你不需要查找它然后插入是O(1).
不,并非所有链表实现都有指向列表末尾的指针.
例
假设您有一个添加单个节点的空列表,x.然后n在之前和之后将节点添加到列表中x.无论列表中有多少个节点,您仍然可以x通过简单地更新其next指针(和新节点)来插入单个节点.