Introduction

I wrote a post on the Iterator Design Pattern in Java. In that, I explained how an Iterator is useful for iterating over the elements of an aggregate (or simply a Collection). An Iterator only allows us to iterate in one direction (forward). In this post, we will learn about a sub-interface of Iterator called the ListIterator. A ListIterator in Java will enable us to move (iterate) in both directions (forward and backward).

A Quick recap of the Java Iterator

The Iterator Design Pattern post explains about the Java Iterator. This section gives a quick introduction to the Iterator interface in Java. If you are familiar with this, feel free to skip this section. If not, I recommend you to read the Iterator Design Pattern post too.

An Iterator has two important methods

  • hasNext
  • next

The hasNext method returns a boolean and hence it returns true if there are more elements available to be returned (and false otherwise).

The next method returns the next element from the collection. If we call next() when there are no elements in the collections available (i.e., when hasNext returns false), it will throw a NoSuchElementException.

Apart from the above two methods, an Iterator also provides a remove method. Calling a remove method after calling the next will remove the element returned by the next method. Hence, it can only be called once per call to next(). In other words, you cannot have two successive remove calls.

ListIterator - A subinterface of Iterator

Let us dive into the ListIterator in Java.

A ListIterator is an Iterator that allows us to traverse a list (or iterate the list) in either direction. It also allows to modify the list when iterating. Yes, it supports the remove method of an Iterator (because a ListIterator is an Iterator). In addition to this (as we will see soon), it supports adding a new element into the list. It also supports changing(replacing) the element at a position.

The Current Position of a ListIterator

A ListIterator does not have a current element. In other words, it does not point to any element to quote it as the “current element”. Instead, its cursor position lies between the element that would be returned by the previous() method and the element returned by the call to the next() method (We will look at these methods in just a bit).

Let us look into the methods of a ListIterator in Java.

The hasNext and next methods

These methods behave the same way as in an Iterator (as described earlier). As long as we have elements left, we get the next element and print it.

List<String> list = Arrays.asList("a", "b", "c", "d", "e");
ListIterator<String> listIterator = list.listIterator();
while (listIterator.hasNext()) {
    System.out.println(listIterator.next());
}

Prints,

a
b
c
d
e

The nextIndex method

The nextIndex method returns the index of the element that would be returned by a subsequent call to next(). But unlike next(), calling nextIndex() does not move the cursor forward. If the iterator has already reached the end of the list, calling nextIndex would return the list size.

listIterator = list.listIterator();
while (listIterator.hasNext()) {
    int index = listIterator.nextIndex();
    String element = listIterator.next();//this call moves the iterator forward
    System.out.println(String.format("The element at index %d is %s", index, element));
}

The element at index 0 is a
The element at index 1 is b
The element at index 2 is c
The element at index 3 is d
The element at index 4 is e

The hasPrevious, previous and previousIndex

These methods are specific to a ListIterator as it allows to traverse backwards too. The hasPrevious method is similar to the hasNext method but in the backward sense. It returns true if there is at least one element if we traverse backward from the current position. Hence, it always returns false when starting the iteration.

The previousIndex returns the index of the previous element. If we have already reached the start of the list, it returns -1.

listIterator = list.listIterator();
while (listIterator.hasNext()) {
    listIterator.next(); //Iterate till the end
}
//Start iterating backwards
while (listIterator.hasPrevious()) {
    int index = listIterator.previousIndex();
    String element = listIterator.previous();//this call moves the iterator backward
    System.out.println(String.format("The element at index %d is %s", index, element));
}
System.out.println(listIterator.previousIndex());//We are at the beginning now - hence returns -1

Outputs,

The element at index 4 is e
The element at index 3 is d
The element at index 2 is c
The element at index 1 is b
The element at index 0 is a
-1

Calling next() when the cursor is the end of the list or calling previous() when at the start of the list will throw a NoSuchElementException.

Calling next() and previous() one after the other will return the same element

listIterator = list.listIterator();
System.out.println(listIterator.next());
System.out.println(listIterator.previous());
System.out.println(listIterator.next());
System.out.println(listIterator.previous());

Prints,

a
a
a
a

Adding to the collection when iterating - The add method

By using the add method of a ListIterator, we can add an element to the underlying list from which the ListIterator was created.

The element that is added will be inserted immediately before the element that would be returned by a call to the next() and after the element that would be returned by a call to the previous() (if one exists).

An important point to note here is that even though the added element is inserted before the next element, calling next() will not return the newly added element. What happens here is that after adding the new element, the cursor is internally moved forward by one position. Hence, a subsequent call to next() would not be affected - in other words, calling next() returns the same element if we had not added any new element using the add() method. This implies that calling previous() would return the new element.

If this sounds confusing, let us look at an example. Re-read the above paragraph after seeing the example.

Adding to the beginning of the list

List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c", "d", "e"));
ListIterator<String> listIterator = list.listIterator();

System.out.println(listIterator.nextIndex()); //0

Now, the listIterator’s position is before the first element (“a"). Let us add a new string now

listIterator.add("before_a");

As said earlier, this would be added before the element that would be returned by next(). Hence, it will be before “a”.

System.out.println(list);
System.out.println(listIterator.nextIndex());
System.out.println(listIterator.next());

Prints,

[before_a, a, b, c, d, e]
1
a
before_a

The list content confirms that “before_a" is added before “a". The nextIndex is no longer 0 - it has been internally moved forward by one position and hence it is 1. Thus, calling next() returns “a” and not “before_a”.

However, if we had called previous() (instead of next()) immediately adding the new element, it would return the newly added element (“before_a”).

Adding to the (somewhere in the) middle of the list

Let us look at another example where we will add the new element as the 2nd element in the list.

list = new ArrayList<>(Arrays.asList("a", "b", "c", "d", "e"));
listIterator = list.listIterator();
listIterator.next();//move forward by one
System.out.println(listIterator.nextIndex()); //1

Now, the cursor points between elements “a” and “b”. Let us add a new element.

listIterator.add("before_b");

System.out.println(list);
System.out.println(listIterator.nextIndex());

Prints,

[a, before_b, b, c, d, e]
2

“before_b” is added before “b”. The nextIndex is 2.

System.out.println(listIterator.previous());
System.out.println(listIterator.next());
System.out.println(listIterator.next());

before_b
before_b
b

Calling previous() returns “before_b”. Now, the cursor is between “before_b” and “b”. Hence, calling next() two times prints “before_b” and “b”.

Removing an element from the list using the iterator - The remove method

As we saw earlier, the remove() method was present in the Iterator interface itself. It is used to remove the element returned by next(). The remove method in a ListIterator is a bit involved.

The remove method removes the last element that was returned by either calling next() or previous(). This call can be made only once per call to next() or previous(). It doesn’t remove an element by the virtual cursor position. It just removes whatever element was returned previously by either next() or previous() method. Hence, for this next() or previous() had to be called first.

List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c", "d", "e"));
ListIterator<String> listIterator = list.listIterator();
listIterator.remove();

Calling remove without calling next() in the above case throws an IllegalStateException (since we are at the start of the list, we anyway cannot call previous())

Removing does not depend on cursor position

Example 1

To demonstrate that removing does not depend on the cursor position, I will show two examples where the cursor position is the same in both examples i.e., nextIndex() and previousIndex() would return the same value. But calling remove() removes different elements in the two examples.

list = new ArrayList<>(Arrays.asList("a", "b", "c", "d", "e"));
listIterator = list.listIterator();
//Move by two positions forward
listIterator.next();
listIterator.next();

System.out.println(listIterator.nextIndex()); //2
System.out.println(listIterator.previousIndex()); //1
        
listIterator.remove();
System.out.println(list);

We create a ListIterator and move two positions forward. Now the cursor position is between “b” and “c”. The nextIndex is 2 and previousIndex is 1.

Let us call the remove method.

The remove would remove the element that was returned by either next() or previous(). In this case, the last call made was next() and it returned “b”. Hence, remove() will remove “b” from the list.

Printing the list confirms this.

[a, c, d, e]

If we call listIterator.next() after removing, it would continue iterating printing “c” in this case i.e, cursor position is not affected.

Example 2

list = new ArrayList<>(Arrays.asList("a", "b", "c", "d", "e"));
listIterator = list.listIterator();
listIterator.next();
listIterator.next();
listIterator.next();
listIterator.previous();
System.out.println(listIterator.nextIndex()); //2
System.out.println(listIterator.previousIndex()); //1

listIterator.remove(); //Remove
System.out.println(list);
System.out.println(listIterator.next());
System.out.println();

The setup here involves moving forward by 3 elements and moving back. Hence, the cursor position is the same as in the previous example (between “b” and “c”).

But calling remove now would remove “c” and not “b” (as in the last example). This is because of the last call made was previous() and this returned “c”.

Printing the list gives us,

[a, b, d, e]

Now, if we continue moving forward (listIterator.next()), it prints “d”, the next element in the list.

Thus, it is clear that remove solely works by removing the element that was returned previously by either the next() or the previous() method.

Subsequent Remove calls

As we have learnt, the remove depends on the call to next() or previous(). Hence, we cannot have two subsequent remove() calls.

list = new ArrayList<>(Arrays.asList("a", "b", "c", "d", "e"));
listIterator = list.listIterator();
listIterator.next();
listIterator.previous();

listIterator.remove();
listIterator.remove(); //Oops

The 2nd remove call in the above snippet would throw a java.lang.IllegalStateException

Interleaving add calls

There must be no add calls done before the next() or previous() and the remove() call.

list = new ArrayList<>(Arrays.asList("a", "b", "c", "d", "e"));
listIterator = list.listIterator();
listIterator.next();
listIterator.previous();

listIterator.add("new");
listIterator.remove(); //Oops

In the above code, after calling next(), we added a new element before calling remove(). This is not allowed and would throw a IllegalStateException.

Replacing an element at a position when iterating - The set method

The set method is used to replace the last element that was returned by the next() or the previous() method with the specified element.

This call can only be made only if neither remove() nor add() have been called after the last call to next() or previous() - no interleaving remove or add calls must be made after a next/previous call.

This method is very similar to the remove except that instead of removing an element, it replaces it with a new one.

Let us look at examples

Calling set() without next() or previous() calls

List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c", "d", "e"));
ListIterator<String> listIterator = list.listIterator();

listIterator.set("new");

The above will throw an IllegalStateException as neither next() nor previous() has been called.

Calling set() after a next()

list = new ArrayList<>(Arrays.asList("a", "b", "c", "d", "e"));
listIterator = list.listIterator();
listIterator.next();

listIterator.set("new_a");
System.out.println(list);

Calling next(), returns the first element “a”. Now calling set replaces it with the element we pass (“new_a”). The list is now

[new_a, b, c, d, e]

System.out.println(listIterator.nextIndex()); //1
System.out.println(listIterator.next()); //b

The listIterator does not move as an effect of the set method. The nextIndex is 1 and the next element would be “b"

Calling set() after a previous()

list = new ArrayList<>(Arrays.asList("a", "b", "c", "d", "e"));
listIterator = list.listIterator();
listIterator.next();
listIterator.next();
listIterator.next();
listIterator.previous();

We called next() three times and we go back one step. The cursor position is between “b” and “c”. Now, calling set will replace the element returned by previous() (“c”)

listIterator.set("new_c");
System.out.println(list);
System.out.println(listIterator.nextIndex());
System.out.println(listIterator.next());

Prints,

[a, b, new_c, d, e]
2
new_c

Interleaving add and remove calls

As said earlier, there must be no calls to remove() or add() between the next()/previous() calls and the call to the set() method. If we did, it would throw an IllegalStateException (the below two cases).

list = new ArrayList<>(Arrays.asList("a", "b", "c", "d", "e"));
listIterator = list.listIterator();
listIterator.next();
listIterator.next();
listIterator.remove(); 

listIterator.set("some_val"); ////Oops - throws java.lang.IllegalStateException

list = new ArrayList<>(Arrays.asList("a", "b", "c", "d", "e"));
listIterator = list.listIterator();
listIterator.next();
listIterator.add("before_b");
System.out.println(list); //[a, before_b, b, c, d, e]

listIterator.set("some_val"); //Oops - java.lang.IllegalStateException

Conclusion

We learnt about the ListIterator in Java in this post. We looked at the methods that will help us in iterating forward and backwards (next and previous), the methods to return the previous and next index. Then we looked at the remove, add and set methods in great detail with examples.

I hope this would have been helpful to you. I will be happy to hear your comments.

Check out the Iterator Design Pattern if you haven’t already did so.

Other resources to check out: