CODEWITHSUNDEEP
javalinked-listapplet
Volken
Volken

Reputation: 255

Removing all occurrencs of a word in a LinkedList

Im trying to get a method that remove's all occurrences of a word from a Linked List (words). The method I have made removes all occurrences, but not the first one? Here is my remove method:

public void removeAll(){
    for(int x = 0; x < words.size(); x++){
        if(words.get(x).equalsIgnoreCase(inputWord)){
            words.remove(x);
        }
    }
    out2.setText("Word '" + inputWord + "' all occurrence's have been removed.");
    System.out.println(words);
}

If words was: 

 words = "add","hello","add","add"

the output after running the removeAll for "add" would be:

 words = "add","hello"

Anyone have an idea as to why the first occurrence would not have been removed? Thanks!

Upvotes: 2

Views: 380

Answers (1)

Andy Turner
Andy Turner

Reputation: 140319

If you iterate forwards through a list like this and, remove items, you won't remove all adjacent matching items.

For example, if your list is [add, add] and you are removing add:

  • Index is 0 initially, list is [add, add].
  • You find add at index 0.
  • Remove element 0, now the list is [add].
  • Increment index, now index == 1.
  • Index is now greater than or equal to the list size, so you break the loop
  • Final list is [add].

So effectively you "skipped over" the second add.

One way to fix this is to decrement index after you've removed an element. Some people (citation needed) frown upon changing the iteration variable inside the body of the for loop. It makes the correctness a bit harder to reason about.

Another way is to iterate the list in reverse, which works because you're not changing the part of the list which you are yet to check:

for(int x = words.size() - 1; x >= 0; x--){

However, the best approach is to use an Iterator:

Iterator<String> it = words.iterator();
while (it.hasNext()) {
  if (it.next().equalsIgnoreCase(inputWord)) {
    it.remove();
  }
}

Note that LinkedList.get(int) is an O(list.size()) operation, so you don't really want to be using that to access your elements in sequence. An Iterator can be implemented to exploit knowledge of the internal implementation of the list to allow efficient iteration and removal.

Upvotes: 3

Related Questions