最近在计算循环路径时使用了List的subList方法，在运行时会报java.util.ConcurrentModificationException错误：

一、场景

大概场景如图所示，需要找出图中的循环路径，代码如下：

public static void main(String[] args) {
	//next node map
	Map<String, List<String>> map = new HashMap<>();
	map.put("A", Arrays.asList(new String[]{"B"}));
	map.put("B", Arrays.asList(new String[]{"C"}));
	map.put("C", Arrays.asList(new String[]{"D"}));
	map.put("D", Arrays.asList(new String[]{"B", "E"}));
	map.put("E", Arrays.asList(new String[]{"C"}));

	List<List<String>> cyclePaths = new ArrayList<>();
	Stack<String> paths = new Stack<>();
	
	//Start from the first node
	findCyclePaths(map, cyclePaths, paths, "A");
	
	System.out.println("The loop path is：");
	System.out.println(cyclePaths);
}

private static void findCyclePaths(Map<String, List<String>> nextNodesMap, List<List<String>> cyclePaths, Stack<String> paths, String node){
	List<String> nextNodes = nextNodesMap.get(node);
	if(nextNodes == null || nextNodes.isEmpty()){
		return;
	}
	for(String nextNode : nextNodes){
		int index = paths.indexOf(nextNode);
		if(index > -1){
			//cycle
			cyclePaths.add(paths.subList(index, paths.size()));
		}else{
			paths.add(nextNode);
			findCyclePaths(nextNodesMap, cyclePaths, paths, nextNode);
			paths.pop();
		}
	}
}

运行时在System.out.println(cyclePaths);行报错：

The loop path is：
Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.SubList.checkForComodification(Unknown Source)
	at java.util.SubList.listIterator(Unknown Source)
	at java.util.AbstractList.listIterator(Unknown Source)
	at java.util.SubList.iterator(Unknown Source)
	at java.util.AbstractCollection.toString(Unknown Source)
	at java.util.Collections$SynchronizedCollection.toString(Unknown Source)
	at java.lang.String.valueOf(Unknown Source)
	at java.lang.StringBuilder.append(Unknown Source)
	at java.util.AbstractCollection.toString(Unknown Source)
	at java.lang.String.valueOf(Unknown Source)
	at java.io.PrintStream.println(Unknown Source)
	at com.test.CyclePathTest.main(CyclePathTest.java:28)

二、解决方式

  • 原因

由于subList方法返回的是fromIndex(包含)和toIndex(不包括)之间的列表视图，对返回的列表的更改将反映在原列表中；调试时可以看到第二次走到cyclePaths.add()方法时会报com.sun.jdi.InvocationException occurred invoking method.错误：

  • 解决方式

将subList的结果创建一个新的List：

cyclePaths.add(paths.subList(index, paths.size()));

改为：

List<String> cyclePath = paths.subList(index, paths.size());
cyclePaths.add(new ArrayList<>(cyclePath));

再次运行，输出结果为：

The loop path is：
[[B, C, D], [C, D, E]]
参考资料：