A linked list with multiple heads in Java

Question

I have a list in which I'd like to keep several head pointers. I've tried to create multiple ListIterators on the same list but this forbid me to add new elements in my list... (see Concurrent Modification exception).

I could create my own class but I'd rather use a built-in implementation ;)

To be more specific, here is an inefficient implementation of two basic operations and the one which doesn't work :

class MyList <E> {
    private int[] _heads;
    private List<E> _l;

    public MyList ( int nbHeads ) {
        _heads = new int[nbHeads];
        _l = new LinkedList<E>();
    }

    public void add ( E e ) {
        _l.add(e);
    }

    public E next ( int head ) {
        return _l.get(_heads[head++]); // ugly
    }
}


class MyList <E> {
    private Vector<ListIterator<E>> _iters;
    private List<E> _l;

    public MyList ( int nbHeads ) {
        _iters = new Vector<ListIterator<E>>(nbHeads);
        _l = new LinkedList<E>();

        for( ListIterator<E> iter : _iters ) iter = _l.listIterator(); 
    }

    public void add ( E e ) {
        _l.add(e);
    }

    public E next ( int head ) {
        // ConcurrentModificationException because of the add()
        return _iters.get(head).next();
    }
}

Answer 1

The cause for the exception is described in its javadoc:

For example, it is not generally permissible for one thread to modify a Collection while another thread is iterating over it. In general, the results of the iteration are undefined under these circumstances. Some Iterator implementations (including those of all the general purpose collection implementations provided by the JRE) may choose to throw this exception if this behavior is detected. Iterators that do this are known as fail-fast iterators, as they fail quickly and cleanly, rather that risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Note that this exception does not always indicate that an object has been concurrently modified by a different thread. If a single thread issues a sequence of method invocations that violates the contract of an object, the object may throw this exception. For example, if a thread modifies a collection directly while it is iterating over the collection with a fail-fast iterator, the iterator will throw this exception.

That is, for all collection classes in the JDK, a change to a collection invalidates all its iterators (except the one that performed the change).

You could work around this by using indices rather than iterators, but that requires a random access list, and linked lists do not offer efficient random access.

Therefore, if you really need such a data structure, you'll have to look beyond the JDK or implement one yourself.

Answer 2

I would approach this by hiding all the actual iterators to the list within a wrapper class, and hiding the list itself in its own wrapper. The list's wrapper would know about all of the iterator wrappers; on add(), it would need to force each iterator wrapper to record the current position, delete the inside iterator, then perform the actual add (which would avoid the ConcurrentModificationException, because all the actual iterator had been destroyed), then have all the iterator wrappers re-create their iterators and set them to the necessary position. Since you seem to be adding only to the end of the list, no fancy indexing will be necessary, but you will have to figure out what happens to iterators that had already advanced to the end - are they at the end, or at their original position in the list? Some of them, of course, may have already told their callers that hasNext() is false... One more thing: add() and get() should I think be synchronized.

Here's a test-driven solution along these lines. PureListWrapper and PureIteratorWrapper, as the names suggest, simply delegate all of their method calls to the element they wrap.

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Set;

import junit.framework.TestCase;

public class ConcurrentlyAddableListTest extends TestCase {


    public void testAdd() throws Exception {
        List<String> list = new ConcurrentlyAddableList<String>();
        list.add("apple");
        list.add("banana");
         Iterator<String> a = list.iterator();
         Iterator<String> b = list.iterator();
         b.next();
         Iterator<String> c = list.iterator();
         c.next();
         c.next();
         list.add("cherry");
         assertEquals("apple", a.next());
         assertEquals("banana", b.next());
         assertEquals("cherry", c.next());
    }


    private static class ConcurrentlyAddableList<T> extends PureListWrapper<T> {
        private final Set<WrappedIterator<T>> iterators = new HashSet<WrappedIterator<T>>();

        @Override
        public Iterator<T> iterator() {
            WrappedIterator<T> iterator = new WrappedIterator<T>(super.iterator());
            iterators.add(iterator);
            return iterator;
        }

        @Override
        public synchronized boolean add(T o) {
            final HashSet<WrappedIterator<T>> set = new HashSet<WrappedIterator<T>>(iterators);
            for (WrappedIterator<T> iterator : set)
                iterator.rememberPosition(this);
            boolean result = super.add(o);
            for (WrappedIterator<T> iterator : set)
                iterator.restorePosition(this);
            return result;
        }
    }

    private static class WrappedIterator<T> extends PureIteratorWrapper<T> {
        private int index = 0;

        public WrappedIterator(Iterator<T> iterator) {
            super(iterator);
        }

        @Override
        public T next() {
            index++;
            return super.next();
        }

        public void restorePosition(List<T> list) {
            setIterator(list.iterator());
            int prevIndex = index;
            index = 0;
            while (index < prevIndex)
                next();
        }

        public void rememberPosition(List<T> list) {
            setIterator(null);
        }

    }
}