链表中删除的时间复杂度 [英] Time complexity of deletion in a linked list

问题描述

根据此网站，为什么理解链接列表的时间复杂度为何为O（1）有点麻烦。

据我了解，如果您确实要删除某个元素，则必须遍历列表以找出该元素的位置（如果它甚至存在）？据我了解，它不应该是O（n）还是我完全错过了什么？

I'm having a bit of trouble understanding why time complexity of link lists are O(1) according to this website. From what I understand if you want to delete an element surely you must traverse the list to find out where the element is located (if it even exists at all)? From what I understand shouldn't it be O(n) or am I missing something completely?

推荐答案

不，您不是缺少某些内容。

No, you are not missing something.

如果要删除特定元素，时间复杂度为 O（n）（其中 n 是元素数），因为您必须先找到该元素。

If you want to delete a specific element, the time complexity is O(n) (where n is the number of elements) because you have to find the element first.

如果要删除元素在特定索引 i 中的时间复杂度为 O（i），因为您必须遵循

If you want to delete an element at a specific index i, the time complexity is O(i) because you have to follow the links from the beginning.

如果您已经有对该节点的引用，则插入的时间复杂度仅为 O（1）您要在之后插入。如果双向引用列表的删除时间复杂度仅为 O（1）（如果您已经具有要删除的节点的引用）。如果您已经具有要删除的节点和之前的节点的引用，则仅删除 O（1）即可删除单链接列表。所有这一切都与基于数组的列表形成对比，在该列表中，插入和删除操作 O（n），因为您必须将元素往前移动。

The time complexity of insertion is only O(1) if you already have a reference to the node you want to insert after. The time complexity for removal is only O(1) for a doubly-linked list if you already have a reference to the node you want to remove. Removal for a singly-linked list is only O(1) if you already have references to the node you want to remove and the one before. All this is in contrast to an array-based list where insertions and removal are O(n) because you have to shift elements along.

使用链接列表而不是基于数组的列表的优点是，可以在对其进行迭代的同时有效地插入或删除元素。例如，这意味着筛选链接列表比筛选基于数组的列表更有效。

The advantage of using a linked list rather than a list based on an array is that you can efficiently insert or remove elements while iterating over it. This means for example that filtering a linked list is more efficient than filtering a list based on an array.

这篇关于链表中删除的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！