java - 像 .Net 一样将节点引用到链表中，以启用 O(1) 项插入

Question

.Net的LinkedList有一个 nice 基本链表特性，它允许我保留一个节点引用，可以说是一个指向链表的“指针”，并使用该引用从那里导航和操作链表O(1) 时尚。即:

LinkedList<string> linkedList = new LinkedList<string>();
LinkedListNode<string> cur = linkedList.First;
LinkedListNode<string> rememberThis = null;
do
{
    if (...)
        rememberThis = cur;
} while ((cur = cur.Next) != null);

if (rememberThis != null)
    linkedList.AddAfter(rememberThis, "added-value");

我看不出如何在 Java 中做同样的事情，即

1. 遍历LinkedList(这当然是O(n))
2. 记下列表节点
3. 即使在 O(1) 插入的进一步迭代之后也使用该节点引用

Java 做 give me access到 ListIterator ，这使我可以围绕我所在的项目对列表进行操作，但我似乎无法在保持上一个节点的同时进行迭代。

我错过了什么吗？

Answer 1

Am I missing something?

没有。 LinkedList#ListItr 类没有书签。因此，您不能在保留前一个节点的同时继续迭代。
LinkedList 中没有 O(1) 方法 addAfter(Node node, E element)，因为 LinkedList#Node 是私有(private)的。 add(int index, E element) 是 O(n)。太伤心了。

解决方法是使用 2 ListIterator。一个继续迭代，另一个停在你想记住的位置。然后最后就可以用 ListIterator#add(E e)了，也就是O(1)。但是第一个不能修改列表，否则它会破坏第二个。