我正在尝试遍历 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)
}
最佳答案
Iterator
没有 set
方法。幸运的是,您使用的是 LinkedList
,并且 ListIterator
does have a set
method .
ListIterator<String> it = list.listIterator();
while (it.hasNext()) {
it.set("new_" + it.next());
}
关于java - 如何在迭代时在常数时间内修改 Java 链表中的元素?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65101613/