Поиск изменений в двух коллекциях

Оптимальным — по какому параметру? По размеру юзер-кода — наверное, да. Но там у вас используется indexOf по одному из списков, так что вряд ли по времени исполнения (на больших списках).

Посмотрите, как работает diff. По сути — это решение для вашей задачи. Это если строки в списках не перемешаны. Если перемешаны, то нужны конечно дополнительные финты ушами.

Страх и ужас:

• модификация входных данных (oldData, newData) — явный code smell;
• updated = 0 всегда, т. к. если newData.indexOf(oldItem) >= 0, то либо oldItem == null, либо oldItem.equals(newData.get(index));
• непонятно зачем нужная нагрузка на GC, если используются ArrayList'ы (засчёт oldDataIterator.remove() и newData.remove(index), а если используется LinkedList — то вообще убиться веником;

Если списки сортированы, то можно не использовать квадратичный алгоритм (итерация по oldData + List#indexOf), а сделать линейный проход двумя итераторами/по индексам. Если нет, то использовать два HashSet'а:

Set<T> insertedData = new HashSet<>(newData);
insertedData.removeAll(oldData);
inserted = insertedData.size();

Set<T> removedData = new HashSet<>(oldData);
removedData.removeAll(newData);
removed = removedData.size();