I'm trying to iterate through Java's implementation of a linked list and modify each element of the linked list in constant time. I'm aware of the set() method of linked list but that operation is O(n). So if I used the set() method in a loop it would be O(n^2) which isn't what I want. Since I'm iterating through the linked list, I already know the position of the node of which I want to modify it's contents. Is there a way for me to do this in constant time using Java's Linked List?
I've done this many times with custom implementations but I don't see a way to do this in constant time. I tried iterating below but I'm missing something.
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 does not have a set method. Fortunately, you're working with a LinkedList, and ListIterator does have a set method.
ListIterator<String> it = list.listIterator();
while (it.hasNext()) {
it.set("new_" + it.next());
}