链表插入运行时间的混乱 [英] Linked List insertion running time confusion

问题描述

我试图确认的运行时间插入的链表好像有两种不同的答案。

I've tried to confirm the running time for the insertion for Linked List and it seems like there are two different answers.

有关在链表的末尾插入元素，我认为它会采取为O（n），因为它必须遍历到列表的末尾才能访问的尾巴。但一些我见过的答案说，O（1）？是他们假设所有链表执行的指针的尾？如果是的话，是可以接受的假设？

For inserting an element at the end of a Linked List, I would think that it would take O(n) since it has to traverse to the end of the list in order to access the tail. But some of the answers I've seen says O(1)? Are they assuming that all linked lists implementation of a pointer to the tail? If so, is that an acceptable assumption?

其次，有些地方还表明，插入一个链表中间的一个元素是O（1），我感到困惑，由于横向到列表中间同样的道理，将其插入。

Second, some places also suggest that insertion an element in the middle of a linked list is O(1) which I'm confused about due to the same reasoning of traverse to the middle of the list to insert it.

可能有人请澄清？谢谢你。

Could someone please clarify? Thanks.

推荐答案

插入到一个链表是O（1）如果你有一个指针到要插入项的节点。 查找的这个节点可能是为O（n），取决于你想要做什么。

Inserting to a linked list is O(1) if you have a pointer to the node where you want to insert the item. Finding this node may be O(n) depending on what you want to do.

如果你保持一个指向该列表的尾巴那么你就需要寻找它，然后插入为O（1）。

If you keep a pointer to the list's tail then you don't need to look for it and then insertion is O(1).

和无，不是所有的链表实现都有一个指针列表的末尾。

And no, not all linked list implementations have a pointer to the end of the list.

示例

假设你有向其中添加一个节点， X 空列表。然后添加 N 节点列表之前和之后 X 。您还可以通过简单地更新其接下来指针（和新节点的）插入后单节点x ，无论有多少个节点是列表中。

Suppose you have an empty list to which you add a single node, x. Then you add n nodes to the list before and after x. You can still insert a single node after x by simply updating its next pointer (and the new node's), regardless of how many nodes are were the list.

这篇关于链表插入运行时间的混乱的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！