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