LinkedList is a sequential data structure. That’s why all linked list algorithms rely on iterators. In some cases, like remove(Object), iterator would be used implicitly, inside a library method, in other cases it must be used explicitly. For example, you have a LinkedList\u0026lt;String\u0026gt; and you need to remove all Strings after a specified string which are 5 characters long. If specified string is not present, you must process the full buffer. If this example looks a little artificial, replace strings with messages with a timestamp and other properties, and it will become more real.
This could be a first approach to this problem – find position of required string using indexOfmethod and use this position as an argument for listIterator(int) method (and, of course, add 1 to this position to cater for ‘after a specified string’/’specified string not found’ cases.
public static void cleanStringListSlow( final LinkedList\u0026lt;String\u0026gt; lst, final String first ){ final int startPos = lst.indexOf( first ) + 1; final ListIterator\u0026lt;String\u0026gt; iter = lst.listIterator( startPos ); while ( iter.hasNext() ) { if ( iter.next().length() == 5 ) iter.remove(); }} Unfortunately, we need to iterate 1.25 list length on the average in this example. First of all,indexOf method is iterating the list in order to find required string. In the best case required string is the first in the list, in the worst case it is not present in the list at all, so we need to check all elements of the list. So, on average indexOf call requires iterating 0.5 list length. After that we are passing start position to the listIterator(int) method. It was optimized (as well as other indexed access methods, like get(int), remove(int)), so if index belongs to the first half of the list, iterator will scroll from the beginning of the list internally, otherwise it will go back from the end. In our example, the best case would be if required string is the last element of the list – nothing would be done, because listIterator argument would be equal to length of the list. The worst case is an element from the first half of the list – first of all listIterator(int) will scroll to it from the beginning and then the method loop will scroll to the tail of the list, thus accessing all list elements.
The idea to rewrite such algorithm is to write your own version of indexOf method, which will return listIterator. Let’s agree that returned iterator should point to requested element if it is present in the list (next method will return this element). In case when requested element is not present in the list, iterator should point at the end of the list (hasNext() == false). Let’s also assume that required element is not equal to null.
public static \u0026lt;T\u0026gt; ListIterator\u0026lt;T\u0026gt; findElem( final List\u0026lt;T\u0026gt; lst, final T elem ){ final ListIterator\u0026lt;T\u0026gt; iter = lst.listIterator(); while ( iter.hasNext() ) { if ( elem.equals( iter.next() ) ) { iter.previous(); break; } } return iter;}