链表删除的时间复杂度 [英] 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屋！