5

我想使用链表来执行元素的提取和插入，尝试所有组合以进行启发式。链表对于这种类型的操作更有效。因为我想尝试所有可能的提取/插入对，所以我在列表上使用了两个不同的迭代器。这会引发“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;

谢谢

4

3 回答 3

1

如果我没听错的话，你会寻找一种数据结构，它提供了几个用于操作列表的迭代器。这对于原始的 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;
}}
于 2013-07-25T13:03:39.550 回答
1

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

尝试这个：

List<Integer> safeData = new CopyOnWriteArrayList(date);
// your code, but working with safeData rather than data
于 2012-11-15T14:44:08.050 回答
0

当您只执行读取操作时，您可以在 LIST 上使用任意数量的迭代器。由于您在此处执行删除/添加，因此您不能将同一个列表与两个不同的迭代器一起使用，因为它会导致您现在遇到的 ConcurrentModificationException。

你想达到什么目标？可能，人们可以为您提供不同的选择。

于 2012-11-15T14:23:59.763 回答