Why an exception is thrown when removing an item via iterator while running over the list?

Question

I invetigate the code of remove method of class ListIterator and i can't understand why after removing an item while running over the list, an exception is thrown when trying to get the next element after the remove. Here is the source I have read:

   public void remove() {

                if (lastRet < 0)


                    throw new IllegalStateException();


                checkForComodification();

                try {
                    SubList.this.remove(lastRet);

                    cursor = lastRet;
                    lastRet = -1;
                    expectedModCount = ArrayList.this.modCount;


                } catch (IndexOutOfBoundsException ex) {


                    throw new ConcurrentModificationException();
                }
            }

The things I can't understand:

1. Why remove method gets lastRet and not cursor. We want to remove current item and not the one we have already passed on?

2.Why lastRet is set to -1?

3.The following line: expectedModCount = ArrayList.this.modCount; set *expectedModCount * to be equal to modCount, so in next iteration when both variable will be checked for equality, the if will "say" true and everything ok. I read a lot of article over the net, and some answers in SO, but still can't understand

Since I have got response that says the code isn't cause a run time exception, here is the code which caused it:

    public class Testing
{
    public static void main(String[] args)
    {
        List <String> list = new ArrayList<String>();
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("e");

        Iterator<String> iterator = list.listIterator();
        while (iterator.hasNext())
        {
            String st = iterator.next();
            if (st.equals("c"))
            {
                list.remove(index);
            }

            else
            {
                System.out.println(st);
            }
        }
}

Answer 1

1. The javadoc for Iterator.remove() says:

Removes from the underlying collection the last element returned by this iterator

So the cursor is pointing to the next element by the time this method is called, hence lastRet is used.

2. -1 means not found. It's set to -1 because you just removed lastRet hence it doesn't exist any more. This means you can't call remove() again without calling next() first: if you look at next(), it will update lastRet

3. Calling ArrayList.this.remove() changes the modCount (modCount is managed by AbstractList, a superclass of the ArrayList iterator that you are looking at). Since this change is caused by the method itself, we know that this is a valid change (in other words, we just requested to change the list). So the local variable (expectedModCount) is updated. If this list is modified by another instance of the iterator, then AbstractList's modCount will change, but expectedModCount, which belongs to the current instance won't. This way the current instance will know that there has been a concurrent modification.

---

Extra question:

I understand. just small question please.. If I have two different thread that are running with for/while loop on the same list (not with an Iterator). And one of them removing an item, in this case exception won't occur? Only when using Iterators system is "safe"?

Multi-threading is not a 'small' question :)

The short answer is that no, it's not safe in either case. Whatever loop you use, as 1 thread is checking if it's safe to do another loop (whether it is .hasNext(), or i < size()), another thread could be at the same time removing/adding elements. So while you won't get a concurrent modification exception if you are using a for loop, you may get an index out of bounds exception.

You should try yourself. Here are some hacky examples (I am using LinkedList for quick removal operations, since using an iterator to remove objects from the beginning of the list is very slow)

Iterator (throws ConcurrentModificationException):

import java.util.*;
import java.util.concurrent.*;

public class Main {

    public static void main(String[] args) throws ExecutionException, InterruptedException {

        List<Long> list = new LinkedList<>();
        for (long i1 = 0; i1 < 1_000_000; i1++) {
            list.add(i1);
        }

        ExecutorService executorService = Executors.newFixedThreadPool(10);
        List<Callable<Integer>> tasks = new ArrayList<>();
        Iterator<Long> iterator = list.iterator();
        for (int i = 0; i < 10; i++) {
            tasks.add(() -> {
                int count = 0;
                while (iterator.hasNext()) {
                    iterator.next();
                    iterator.remove();
                    count++;
                }
                System.out.println("Thread " + Thread.currentThread() + " removed " + count + " items");
                return count;
            });
        }
        List<Future<Integer>> results = executorService.invokeAll(tasks);
        int sum = 0;
        for (Future<Integer> result : results) {
            sum += result.get();
        }
        System.out.println("sum of removed items = " + sum);
        executorService.shutdown();
    }

}

Replacing with a for i loop (throws IndexOutOfBoundsException):

        List<Long> list = new ArrayList<>();
        for (long i1 = 0; i1 < 1_000_000; i1++) {
            list.add(i1);
        }

        ExecutorService executorService = Executors.newFixedThreadPool(10);
        List<Callable<Integer>> tasks = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            tasks.add(() -> {
                int count = 0;
                for (int j = 0; j < list.size(); j++) {
                    list.remove(list.size() - 1);
                    count++;
                }
                System.out.println("Thread " + Thread.currentThread() + " removed " + count + " items");
                return count;
            });
        }
        List<Future<Integer>> results = executorService.invokeAll(tasks);
        int sum = 0;
        for (Future<Integer> result : results) {
            sum += result.get();
        }
        System.out.println("sum of removed items = " + sum);
        executorService.shutdown();

One thing you can do to avoid these exceptions is to use a synchronized block, which makes sure only 1 thread is allowed to execute inside at a time - it is necessary to check again after entering the synchronized block whether the condition is still true:

        List<Long> list = new LinkedList<>();
        for (long i1 = 0; i1 < 1_000_000; i1++) {
            list.add(i1);
        }

        ExecutorService executorService = Executors.newFixedThreadPool(10);
        List<Callable<Integer>> tasks = new ArrayList<>();
        Iterator<Long> iterator = list.iterator();
        Object lock = new Object();
        for (int i = 0; i < 10; i++) {
            tasks.add(() -> {
                int count = 0;
                while (iterator.hasNext()) {
                    synchronized (lock) {
                        if (iterator.hasNext()) {
                            iterator.next();
                            iterator.remove();
                            count++;
                        }
                    }
                }
                System.out.println("Thread " + Thread.currentThread() + " removed " + count + " items");
                return count;
            });
        }
        List<Future<Integer>> results = executorService.invokeAll(tasks);
        int sum = 0;
        for (Future<Integer> result : results) {
            sum += result.get();
        }
        System.out.println("sum of removed items = " + sum);
        executorService.shutdown();

Java also has concurrent collections that you can use to enable multiple threads to do parallel computations.

Giving each thread its own iterator requires changing to something like ConcurrentLinkedQueue to avoid concurrent modification exceptions. However, the code gives a very wrong result:

        Collection<Long> list = new ConcurrentLinkedQueue<>();
        for (long i1 = 0; i1 < 1_000_000; i1++) {
            list.add(i1);
        }

        ExecutorService executorService = Executors.newFixedThreadPool(10);
        List<Callable<Integer>> tasks = new ArrayList<>();
        Object lock = new Object();
        for (int i = 0; i < 10; i++) {
            tasks.add(() -> {
                int count = 0;
                Iterator<Long> iterator = list.iterator();
                while (iterator.hasNext()) {
                    synchronized (lock) {
                        if (iterator.hasNext()) {
                            iterator.next();
                            iterator.remove();
                            count++;
                        }
                    }
                }
                System.out.println("Thread " + Thread.currentThread() + " removed " + count + " items");
                return count;
            });
        }
        List<Future<Integer>> results = executorService.invokeAll(tasks);
        int sum = 0;
        for (Future<Integer> result : results) {
            sum += result.get();
        }
        System.out.println("sum of removed items = " + sum);
        executorService.shutdown();

Which prints out

sum of removed items = 1105846

So it seems like iterator is not very thread-safe :)

If we get rid of iterator:

        Queue<Long> list = new ConcurrentLinkedQueue<>();
        for (long i1 = 0; i1 < 1_000_000; i1++) {
            list.add(i1);
        }

        ExecutorService executorService = Executors.newFixedThreadPool(10);
        List<Callable<Integer>> tasks = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            tasks.add(() -> {
                int count = 0;
                while (!list.isEmpty()) {
                    list.poll();
                    count++;
                }
                System.out.println("Thread " + Thread.currentThread() + " removed " + count + " items");
                return count;
            });
        }
        List<Future<Integer>> results = executorService.invokeAll(tasks);
        int sum = 0;
        for (Future<Integer> result : results) {
            sum += result.get();
        }
        System.out.println("sum of removed items = " + sum);
        executorService.shutdown();

This is better:

sum of removed items = 1000007

Putting back the lock:

        Queue<Long> list = new ConcurrentLinkedQueue<>();
        for (long i1 = 0; i1 < 1_000_000; i1++) {
            list.add(i1);
        }

        ExecutorService executorService = Executors.newFixedThreadPool(10);
        List<Callable<Integer>> tasks = new ArrayList<>();
        Object lock = new Object();
        for (int i = 0; i < 10; i++) {
            tasks.add(() -> {
                int count = 0;
                while (!list.isEmpty()) {
                    synchronized (lock) {
                        if (!list.isEmpty()) {
                            list.poll();
                            count++;
                        }
                    }
                }
                System.out.println("Thread " + Thread.currentThread() + " removed " + count + " items");
                return count;
            });
        }
        List<Future<Integer>> results = executorService.invokeAll(tasks);
        int sum = 0;
        for (Future<Integer> result : results) {
            sum += result.get();
        }
        System.out.println("sum of removed items = " + sum);
        executorService.shutdown();

Seems to work

sum of removed items = 1000000