如何在Java的链表中遍历时常数时间内修改元素？

Question

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

我已经在自定义实现中多次完成了此操作，但我看不到在常数时间内完成此操作的方法。我尝试了下面的迭代，但我缺少某些东西。

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)
}

- Chigozie A.

---

@KevinAnderson 我本来想打 list.set()，但现在我知道了还有一种使用列表迭代器的 set() 方法。 - Chigozie A.

Answer 1

Iterator 没有 set 方法。幸运的是，你正在使用一个 LinkedList，而 ListIterator **确实** 有一个 set 方法。

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

- chrylis -cautiouslyoptimistic-

---

最佳答案，利用链表的优势。今天似乎没有人真正知道这是什么了。 - Ridcully

使用set()方法能否在链表中的一个节点内以常数时间替换内容（仅考虑单次迭代）？我希望能够使用循环以常数时间更改链表中每个节点的内容（因此总时间复杂度为O(n)）。 - Chigozie A.

是的，这就是“ListIterator”的全部意义：它直接处理（即在O(1)时间内）列表节点。 - Kevin Anderson