指向Java LinkedList节点的指针
我正在LinkedList
O(1)将n个条目推入Java 。
我想在以后的O(1)删除一些独特的项目。
我虽然要保留指向“”的唯一节点的数组,LinkedList
以便稍后再删除它们。
有没有办法在LinkedList
其他任何Java类上执行此操作?
我尝试将迭代器存储到项目。这样我就可以使用iter.remove()
。但我知道当时列表上只能有一个迭代器。
我知道一个简单的解决方案可以自己实现链接列表。但是我宁愿使用LinkedList
或已经实施的其他一些Java类。
回答:
Java List
实现不提供O(1)
removes
*的性能。使用迭代器,您必须遍历索引(O(n)),使用遍历ArrayList
后移(O(n)),即使它LinkedList
是双向链接列表,也不会在其中公开节点您只需简单地重新分配下一个/最后一个引用就可以直接删除它们的列表-
需要遍历才能找到要删除的节点(O(n))。
您可以编写自己的代码MyDoublyLinkedList<MyNode<T>>
,公开节点而不是其中包含的值,如果保留对节点的引用,则可以删除O(1)。索引当然是O(n)以便按索引从列表中获取内容。根据您的使用模式,这可能是一个可行的设计选择。
简而言之,如果您要使用Java提供的数据结构,请使用提供该性能的数据结构:
如果排序不重要并且没有重复的项目,请使用HashSet(但是请注意,这根本不允许直接索引)
否则,重新编写代码以使用Map
实现可能是最好的选择。
[*] LinkedList
和Deque
实现为O(1)用于去除头/尾。
如上所述,没有,没有O(1)时间复杂度删除操作。
其 原因 是,除了在最极端的情况下,它是无关紧要的。
在我5岁的3Ghz台式机上LinkedList
,通过索引(即index = length / 2)对100,000个条目的a
进行最坏情况的O(n)移除需要0.2ms(第二点)。
如果将此盒中的Windows内存管理到1,000,000个条目,由于该窗口上的Windows内存管理,我开始进入Windows交换磁盘I / O。
简而言之,您正在尝试解决大多数情况下不存在的问题。通常称为“过早优化”
以上是 指向Java LinkedList节点的指针 的全部内容, 来源链接: utcz.com/qa/412557.html