如何在迭代的同时以恒定的时间修改Java的链表中的元素？

Question

我试图迭代 Java 的链表实现，并在恒定时间内修改链表的每个元素。我知道链表的 set() 方法，但该操作是 O(n) 。因此，如果我在循环中使用 set() 方法，它将是 O(n^2) 这不是我想要的。由于我正在遍历链表，因此我已经知道要修改其内容的节点的位置。有没有办法让我使用 Java 的链表在恒定时间内完成此操作？

我已经通过自定义实现多次执行此操作，但我没有找到在恒定时间内执行此操作的方法。我尝试在下面进行迭代，但我遗漏了一些东西。

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");
Iterator iterator = list.iterator();

while (iterator.hasNext()) {
    iterator.remove();
    iterator.set(); // using set() wouldn't be O(1)
}

Answer 1

Iterator没有set方法。幸运的是，您正在使用LinkedList, 并且ListIterator 确实有一个set方法。

ListIterator<String> it = list.listIterator();
while (it.hasNext()) {
  it.set("new_" + it.next());
}