在O(1)中从双重LinkedList中删除

Question

我知道从双链表中删除一个元素的时间复杂度是O(1)，这似乎是显而易见的，但如果我们没有收到一个元素来删除它，而是由元素包装的元素，会发生什么?

例如，如果定义一个类Element来包装字符串(提供指向下一个和上一个元素的指针)，如果方法接收到该元素作为输入而不是字符串，则可以在0(1)内执行删除操作!

如果remove方法接收到字符串，它必须在列表中搜索以找到相应的元素，对吗?所以这种情况下的时间复杂度是O(n)而不是O(1)

  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 !
    }
  }

Answer 1

你完全正确。

Remove被认为是O(1)(当您执行remove(Element)时)，但通常它与查找操作(即remove(String)或remove(find(String)))一起，即O(n)。

Answer 2

这个链表(循环，双链表，如何管理节点到对象的关系?)使用了一个非常可疑的方法，将属性插入到要添加到列表的对象中。它可以在不搜索对象的情况下删除O(1)，但是如果您向列表中添加基本类型，则有属性名称冲突和性能损失的风险(在添加属性时它们会被装箱)。