当我们确定时间复杂度时我们总是考虑到最坏的情况。那么为什么我们不假设在单链表中删除的最坏情况(不知道值在哪里，因此需要遍历整个链表)???
我将其用作“真实来源”http://bigocheatsheet.com/
例如，删除一个数组被认为是 O(n)，因为如果我们删除第一个项目，那么我们将需要重新分配数组中所有其他项目的索引。如果我们只是删除数组中的最后一项，那么它将是常数时间。但我们假设最坏的情况，这是有道理的。
那么为什么我们不对链表做同样的事情，并假设最坏的情况呢？在那种情况下，在我看来应该是 O(n) 对吗？
最佳答案
从链表中删除意味着你知道你删除了什么元素。您所做的就是将引用从该元素重新分配给下一个元素。因此这个操作是 O(1)。 当然，在链表中搜索是 O(n) 以及在数组中。但是在数组中，即使你知道你的元素，你也必须在那之后重新分配所有元素。
关于algorithm - 为什么单链表中的删除运行时间被认为是常数 O(1)？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/50864205/