从O（1）中删除双重链接列表 [英] Removing from Doubly LinkedList in O(1)

问题描述

我知道这是从双重链接列表中删除元素的时间复杂度是O（1），它似乎很明显，但是如果我们没有收到一个元素来删除它，而是由元素包裹的那个，会发生什么例如，如果我们定义一个类元素来包装一个String（为了提供指向下一个和上一个元素的指针），我们可以在O（1）中执行删除）如果方法接收到该元素作为输入而不是字符串！

如果remove方法接收到字符串，则必须通过列表搜索找到相应的元素，右？所以这种情况下的时间复杂度将是O（n），而不是O（1）

  class Element {
字符串内容; 
元素下一个; 
元素上一个; 
} 
 
 class LinkedList {
 ... 
 public remove（String s）{
 //它必须首先找到与此对应的元素字符串！ 
} 
} 
  

解决方案

你完全正确。

删除被认为是 O（1）（当你做删除（元素）），但通常与find操作（即 remove（String）或 remove（find （String））），它是 O（n）。

I know that's the time complexity to remove an element from doubly linkedlist is O(1) and it seems obvious and clear BUT what happens if we don't receive an element to remove it but the one which is wrapped by the element?

for example if we define a class Element to wrap a String (To provide pointer pointing to the next and previous element) , we can do the removal in O(1) if the method receives that element as input not the string !

if the remove method receives the string , it has to search through the list to find the corresponding element , right ? so the time complexity in this case would be O(n) , not O(1) anymore

  class Element{
    String content;
    Element next;
    Element previous;
  }

  class LinkedList{
    ...
    public remove(String s){
        //it has to first find the element corresponding to this String !
    }
  }

解决方案

You are exactly right.

Remove is considered O(1) (when you do remove(Element)), but usually this goes together with a find operation (i.e. remove(String) or remove(find(String))), which is O(n).

这篇关于从O（1）中删除双重链接列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！