1

我觉得我的 Java 生锈了，所以我尝试了一个简单的问题：与只返回唯一值的链接列表的合并排序。以下是我的第一次尝试。这对我来说很有意义。问题是，无论我做什么，我总是得到一个ConcurrentModificationException.

我尝试过的事情包括：

  • 制作块或方法synchronized。
  • 用方法内的迭代器替换 LinkedLists sort。
  • 在单独的变量中跟踪列表的大小（该部分被保留）。

没有任何效果。ConcurrentModificationsException搬到了其他地方，但它仍然在原地。我真的不知道为什么。我怎样才能解决这个问题？

在此特定尝试中，异常发生在调用addAll. 我将列表中的所有操作都放在了它们自己的块中，但 Java 显然不在乎。

package com.regularoddity.dotcloud;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class Merge {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        List<Integer> myList = new LinkedList<Integer>();
        myList.add(2);
        myList.add(9);
        myList.add(1);
        myList.add(3);
        myList.add(8);
        myList.add(7);
        myList.add(1);
        myList = sort(myList);
        Iterator<Integer> lit = myList.iterator();
        while(lit.hasNext()) System.out.printf("%s ", lit.next());
    }

    private static List<Integer> merge(List<Integer> list1, List<Integer> list2) {
        List<Integer> result = new LinkedList<Integer>();
        int size1 = list1.size();
        int size2 = list2.size();
        {
            while (size1 > 0 && size2 > 0) {
                if (list1.get(0) == list2.get(0)) {
                    result.add(list1.remove(0));
                    list2.remove(0);
                    size1--; size2--;
                }
                else if (list1.get(0) <= list2.get(0))
                {
                    result.add(list1.remove(0));
                    size1--;
                }
                else
                {
                    result.add(list2.remove(0));
                    size2--;
                }
            }
        }
        result.addAll(list1);
        result.addAll(list2);
        return result;
    }

    private static List<Integer> sort(List<Integer> list) {
        int lsize = list.size();
        if (lsize <= 1) return list;
        int pivot = lsize / 2;
        List<Integer> list1 = list.subList(0, pivot);
        List<Integer> list2 = list.subList(pivot, lsize);
        list1 = sort(list1);
        list2 = sort(list2);
        return merge(list1, list2);
    }


}

最让我困惑的是，我从来没有明确地对列表进行过互动。必须进行隐式迭代，但我似乎无法将其分解。

编辑：我没有包括堆栈跟踪，因为我（愚蠢地）认为每次修复尝试都会改变它，它不会有用。但是，实际上，它并没有太大变化。这是当前实现的堆栈跟踪：

Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.SubList.checkForComodification(AbstractList.java:752)
    at java.util.SubList.size(AbstractList.java:625)
    at com.regularoddity.dotcloud.Merge.merge(Merge.java:30)
    at com.regularoddity.dotcloud.Merge.sort(Merge.java:64)
    at com.regularoddity.dotcloud.Merge.sort(Merge.java:62)
    at com.regularoddity.dotcloud.Merge.main(Merge.java:23)

com.regularoddity.dotcloud.Merge.main(Merge.java:23)

4

1 回答 1

4

状态的javadocsubList：

如果后备列表（即此列表）以除通过返回列表之外的任何方式进行结构修改，则此方法返回的列表的语义将变为未定义。

在您的情况下，您调用subList两次并通过两个子列表修改原始列表。那是您异常的根源。

在不更改太多代码的情况下，您只需制作副本即可避免该问题：

List<Integer> list1 = new LinkedList<> (list.subList(0, pivot));
List<Integer> list2 = new LinkedList<> (list.subList(pivot, lsize));
于 2013-05-27T22:20:52.633 回答