Java中包含多个头的链表

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).

我有一个列表，其中我想保留几个头指针。我试图在同一个列表中创建多个ListIterators，但这禁止我在列表中添加新元素...（请参阅并发修改例外）。

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

2 个解决方案

#1

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.

我会通过将所有实际迭代器隐藏到包装类中的列表中，并将列表本身隐藏在自己的包装器中来实现此目的。列表的包装器将知道所有迭代器包装器;在add（）上，它需要强制每个迭代器包装器记录当前位置，删除内部迭代器，然后执行实际添加（这将避免ConcurrentModificationException，因为所有实际迭代器都已被销毁），然后拥有所有迭代器包装器重新创建它们的迭代器并将它们设置到必要的位置。因为你似乎只是添加到列表的末尾，所以不需要花哨的索引，但是你必须弄清楚已经提前到最后的迭代器会发生什么 - 它们是最后的，还是它们的原始在列表中的位置？当然，他们中的一些人可能已经告诉他们的调用者hasNext（）是假的......还有一件事：add（）和get（）我应该认为是同步的。

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.

这是沿着这些方向的测试驱动解决方案。正如名称所示，PureListWrapper和PureIteratorWrapper只是将所有方法调用委托给它们包装的元素。

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

    }
}

#2

The cause for the exception is described in its javadoc:

该异常的原因在其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.

例如，一个线程通常不允许修改Collection，而另一个线程正在迭代它。通常，在这些情况下，迭代的结果是不确定的。如果检测到此行为，某些Iterator实现（包括JRE提供的所有通用集合实现的实现）可能会选择抛出此异常。执行此操作的迭代器称为故障快速迭代器，因为它们快速且干净地失败，而不是在未来的未确定时间冒着任意的，非确定性行为的风险。

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).

也就是说，对于JDK中的所有集合类，对集合的更改会使其所有迭代器失效（执行更改的迭代器除外）。

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.

因此，如果您确实需要这样的数据结构，则必须超越JDK或自己实现。