How to use two different iterators on a Linked List in Java?

Question

I would like to use a linked list in order to perform extractions and insertions of elements, trying out all combinations for a heuristic. Linked lists are more efficient for this type of operations. Since I would want to try all possible pairs of extractions/inserts, I used two different iterators over the list. This raises a "ConcurrentModificationException". How could I perform this operation efficiently, without re-traversing the list every time, as this would defeat the whole purpose of using a list in the first place?

Here is the relevant part of the code:

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;

Thanks

Answer 1

You can't use multiple iterators simultaneously on a LinkedList, however you can with a CopyOnWriteArrayList

Try this:

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

Answer 2

If I get you right, you look for a data structure that offers several iterators for manipulating the list. This is technically difficult for the original java.util.LinkedList because it does housekeeping for the current index and this is only possible in an efficient way if there are no parallel changes at unknown positions in the list by other iterators. But, you can easily implement a simple LinkedList that does not do this housekeeping and supports adding/removing through several iterators. Then, an iterator does not know its position in the list, but I bet you do not care. Just use something like this:

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;
}}