Блог

Я пытаюсь выполнить итерацию по реализации связанного списка в 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 у вас есть set метод.

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