Java中具有多个头的链表

Question

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

我可以创建自己的类,但我宁愿使用内置的实现;)

更具体地说,这是两个基本操作的低效实现,以及不起作用的操作:

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

我将通过将所有实际迭代器隐藏到包装类中的列表，并将列表本身隐藏在其自己的包装中来解决此问题。列表的包装器将了解所有迭代器包装器；on add()，需要强制每个迭代器包装器记录当前位置，删除内部迭代器，然后执行实际的添加（这将避免 ConcurrentModificationException，因为所有实际的迭代器都已被销毁），然后让所有迭代器包装器重新-创建它们的迭代器并将它们设置到必要的位置。由于您似乎只添加到列表的末尾，因此不需要花哨的索引，但是您必须弄清楚已经前进到末尾的迭代器会发生什么 - 它们是在末尾还是在原始位置在列表中的位置？当然，他们中的一些人可能已经告诉他们的来电者这是错误的……还有hasNext()一件事：我认为应该是…… 。add()get()synchronized

这是一个沿着这些思路的测试驱动的解决方案。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);
        }

    }
}