1

我知道从双向链表中删除一个元素的时间复杂度是 O(1) 并且看起来很明显但如果我们没有收到删除它的元素但被元素包裹的元素会发生什么？

例如，如果我们定义一个类 Element 来包装一个字符串（以提供指向下一个和上一个元素的指针），如果方法接收该元素作为输入而不是字符串，我们可以在 O(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 !
    }
  }
4

2 回答 2

1

你完全正确。

考虑删除O(1)（当你这样做时），但通常这与查找操作（即或）remove(Element)一起使用，即.remove(String)remove(find(String))O(n)

于 2013-05-11T14:16:47.613 回答
0

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

于 2014-03-02T14:09:05.523 回答