Когда вы зацикливаетесь, вы можете установить переменную с именем oldEntry, например (инициализируется в нуль) и использовать ее так, как вам нужно.
Map.Entry<Integer,String> oldEntry = null;
for (Map.Entry<Integer, String> entry: collection.entrySet()) {
if (oldEntry != null) doStuff(oldEntry, newEntry);
oldEntry = entry;
}