java - 如何在迭代时在常数时间内修改 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 does have a set method .

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