如何在Java中对链表使用两个不同的迭代器？

Question

我希望使用链表来执行元素的提取和插入操作，以试验所有启发式算法的组合方式。链表对于这种操作更加高效。
由于我想尝试提取/插入所有可能的元素对，因此我在列表上使用了两个不同的迭代器。这会引发“ConcurrentModificationException”错误。如何能够高效地执行此操作，而不需要每次重新遍历整个列表，否则这将打败使用列表的初衷？
以下是相关代码片段：

ListIterator<Integer> it1 = data.listIterator();
ListIterator<Integer> it2;

while(it1.hasNext()) {
    int i = it1.next();
    it2 = data.listIterator();

    while(it2.hasNext()) {
        if (i == it2.next()) continue; // continue right away when the indexes are equal
        it1.remove();
        it2.add(i);
        if (length() < best)
            return true;
        }

    // when the swap is not better/consistent
    it2.remove();
    it1.add(i);
}
return false;

谢谢

- David Blinder

---

如果您通过一个迭代器更改列表，则不能使用任何其他迭代器。 - Marko Topolnik

你可以使用ConcurrentLinkedQueue，因为它不会出现CME的问题。我怀疑在任何情况下都有更有效的方法来完成你正在做的事情。 - Peter Lawrey

请搜索以下内容：www.google.com/search?q=multi+dimensional+linked+list+java 并查看像http://www.dreamincode.net/forums/topic/282327-multi-dimensional-linked-list/这样的结果。 - K_B

我必须考虑一个特定的启发式算法中所有可能的重新插入组合，并评估所有组合。这是为了探索一个NP难问题的受限邻域O(n^2)。 - David Blinder

但是无论如何，您不能将所有重新插入操作都视为单个列表。您需要具有不同版本的列表。 - Marko Topolnik

为什么不可能呢？这比完全复制列表要高效得多（O(n)）。这只会交换两个元素。 - David Blinder

Answer 1

在LinkedList上不能同时使用多个迭代器，但是可以使用CopyOnWriteArrayList。

尝试这样做：

List<Integer> safeData = new CopyOnWriteArrayList(date);
// your code, but working with safeData rather than data

- Bohemian

---

谢谢，但这是作为一个数组实现的，而不是作为一个列表。这意味着插入操作将不会很高效；时间复杂度为O(n)，而不是O(1)。 - David Blinder

@DavidBlinder 插入操作的效率会降低，但并不是因为你所说的原因。列表内部使用数组，但这个特殊的类在更改时会在内部创建一个完整的副本以使其线程安全 - 请参见链接的 javadoc。 - Bohemian

Answer 2

如果我理解正确，您正在寻找一种数据结构，可以提供多个迭代器来操作列表。对于原始的java.util.LinkedList而言，这在技术上是困难的，因为它会为当前索引进行维护，只有在没有其他迭代器在列表中未知位置进行并行更改时，才能以有效的方式进行。但是，您可以轻松实现一个简单的LinkedList，它不需要进行此类维护，并支持通过多个迭代器添加/删除。然后，迭代器不知道其在列表中的位置，但我打赌您不在意。只需使用类似以下内容的东西：

public class MyList<T> {
private MyNode<T> first = null, last = null;

public MyNode<T> getFirst() {
    return first;
}

public MyNode<T> getLast() {
    return last;
}

public boolean contains(MyNode<T> n) {
    return n.list == this;
}

/**
 * If beforeMe is null, toInsert is inserted at the end of the list.
 * @return inserted node
 */
public void insertBefore(MyNode<T> beforeMe, MyNode<T> newNode) {
    if (newNode == null) {
        throw new IllegalArgumentException("toInsert must not be null!");
    }

    if (newNode.list != null) {
        throw new IllegalArgumentException("This node is already in the list " + newNode.list);
    }

    if (beforeMe == null) {
        if (last == null) {
            newNode.prev = newNode.next = null;
            first = last = newNode;
        } else {
            last.next = newNode;
            newNode.prev = last;
            newNode.next = null;
            last = newNode;
        }
    } else {
        newNode.prev = beforeMe.prev;
        newNode.next = beforeMe;

        if (beforeMe.prev != null) {
            beforeMe.prev.next = newNode;
        } else {
            first = newNode;
        }

        beforeMe.prev = newNode;
    }

    newNode.list = this;
}

/**
 * If beforeMe is null, t is inserted at the end of the list.
 * @return inserted node
 */
public MyNode<T> insertBefore(MyNode<T> beforeMe, T t) {
    MyNode<T> newNode = new MyNode<T>(t);
    insertBefore(beforeMe, newNode);
    return newNode;
}

public void remove(MyNode<T> n) {
    if (n == null || n.list != this) {
        throw new IllegalArgumentException("Node is not in the list!");
    }

    if (n.prev != null) {
        n.prev.next = n.next;
    } else {
        first = n.next;
    }

    if (n.next != null) {
        n.next.prev = n.prev;
    } else {
        last = n.prev;
    }

    n.prev = n.next = null;
    n.list = null;
}}

public class MyNode<T> {

private T t;
/**
 * written only by MyList
 */
MyNode<T> prev = null;
/**
 * written only by MyList
 */
MyNode<T> next = null;
/**
 * written only by MyList
 */
MyList<T> list = null;

public T get() {
    return t;
}

public void set(T t) {
    this.t = t;
}

public MyNode<T> previous() {
    return prev;
}

public MyNode<T> next() {
    return next;
}

public MyList<T> list() {
    return list;
}

/**
 * called only by MyList.
 * @param t
 */
MyNode(T t) {
    this.t = t;
}}

- user2618802

Answer 3

当您仅进行读取操作时，可以在列表上使用任意数量的迭代器。由于您正在进行删除/添加操作，因此不能使用两个不同的迭代器在同一列表上，否则会导致ConcurrentModificationException异常，就像您现在遇到的问题一样。

您想要实现什么？也许，人们可以为您提供不同的选项来帮助您。

- muruga

---

你不应该把注释写成答案。 - Marko Topolnik

同意。但由于我在stackoverflow上的初始状态，无法将其添加为评论。:( - muruga

两个小时前的情况已经不再是这样了 :) 阈值为50。 - Marko Topolnik