CODEWITHSUNDEEP
javadata-structureslinked-list
TheDev88
TheDev88

Reputation: 335

How to modify elements in Java's Linked List in constant time while iterating through it?

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

Upvotes: 3

Views: 1289

Answers (1)

chrylis -cautiouslyoptimistic-
chrylis -cautiouslyoptimistic-

Reputation: 77226

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

Upvotes: 6

Related Questions