为什么插入链表O（1）的中间？
根据链接列表上的维基百科文章 ，插入链表中间被认为是O（1）。 我会认为这将是O（n）。 你不需要find可能接近列表末尾的节点吗？
这个分析是否不考虑节点操作的发现（尽pipe这是必需的），而只是插入本身？
编辑 ：
链接列表比数组有几个优点。 在列表的特定位置插入元素是一个常量操作，而在数组中插入可能需要移动一半或更多的元素。
上述说法对我有点误导。 纠正我，如果我错了，但我认为结论应该是：
arrays：
- find插入/删除的地方O（1）
- 执行插入/删除O（n）
链接列表：
- find插入/删除的地方O（n）
- 执行插入/删除操作（1）
我认为你唯一不需要find位置的方法就是保持某种指针（就像某些情况下的头部和尾部一样）。 所以我们不能断然地说链表总是为插入/删除选项敲数组。
你是对的，文章认为“索引”是一个单独的操作。 所以插入本身是O（1），但是到达中间节点是O（n）。
不，如果您决定插入，则认为您已经在迭代列表中间。
链接列表上的操作通常是这样做的，它们不是真的被当作通用的“列表”，而是作为节点的集合 – 把节点本身看作是主循环的迭代器。 所以，当你浏览列表时，你注意到作为你的业务逻辑的一部分，需要添加一个新节点（或者删除一个旧节点），并且你这样做了。 您可以在一次迭代中添加50个节点。
编辑：男人，你键入第二段，突然间，而不是第一响应者，你是第五个说与前4个相同的事情！
插入本身是O（1）。 节点查找是O（n）。
为了与一个数组进行比较，就是图表所示，它是O（1），因为您不必移动新节点之后的所有项目。
所以是的，他们假设你已经有了指向该节点的指针，或者获取指针是微不足道的。 换句话说，问题是这样的：“ 给定节点在X上 ，这个节点之后插入的代码是什么？” 你开始在插入点。
因为它不涉及任何循环。
插入就像：
- 插入元素
- 链接到以前
- 链接到下一个
- DONE
无论如何，这是恒定的时间。
因此，一个接一个地插入n个元素是O（n）。
这个分析是否不考虑节点操作的发现（尽pipe这是必需的），而只是插入本身？
你说对了。 在给定点的插入假定您已经持有一个指向您想要插入的项目的指针：
InsertItem(item * newItem, item * afterItem) 插入链表不同于遍历它。 你没有find该项目，你正在重置指针，把项目放在那里。 无论是要插入到前端还是附近，插入仍然包含指针被重新分配。 这取决于它是如何实现的，当然，这是列表的优点 – 你可以很容易地插入。 通过索引访问是arrays发光的地方。 然而，对于一个列表来说，它通常是O（n）find第n个项目。 至less这是我从学校记得的。
插入是O（1），一旦你知道你要把它放在哪里。
不，它不考虑search。 但是如果你已经拥有了一个指向列表中间一个项目的指针，那么在这个点插入O（1）。
如果你必须search它，你必须添加search时间，这应该是O（n）。
这篇文章是关于比较arrays与列表。 查找数组和列表的插入位置是O（N），所以文章忽略它。
O（1）取决于你有一个项目，你将插入新项目的事实。 （之前或之后）。 如果你不这样做，那是因为你必须find那个东西。
我认为这只是你selectO（）表示法的一个例子。 在插入正常操作计数的情况下是复制操作。 对于一个数组，中间插入涉及将所有位置上的内容复制到内存中。 用链表，这个变成了两个指针。 无论插入什么内容，都需要find位置。
如果在链接列表的操作是O（1）之后有插入节点的引用。
对于一个数组，它仍然是O（n），因为你必须移动所有的节点。
最常见的情况可能是插入到列表的开头或结尾（并且列表的末尾可能没有时间find）。
与在数组的开头或结尾处插入项目（如果数组在最后需要resize，或者在开始时resize并移动所有元素的大小）相反。
