Связанный список с несколькими заголовками в Java

Question

У меня есть список, в котором я хотел бы сохранить несколько указателей головы.Я пытался создать несколько ListIterator в одном списке, но это запрещало мне добавлять новые элементы в мой список ... (см. Исключение одновременной модификации ).

Я мог бы создать свой собственныйкласс, но я бы предпочел использовать встроенную реализацию;)

Чтобы быть более конкретным, вот неэффективная реализация двух основных операций и одна, которая не работает:

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

Я хотел бы подойти к этому, спрятав все фактические итераторы в список в классе-обертке, и спрятав сам список в его собственной обертке. Оболочка списка будет знать обо всех обертках итератора; на 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);
        }

    }
}

Answer 2

Причина исключения описана в его javadoc :

Например, это не совсем допустимо для одного потока изменить Коллекция в то время как другая нить перебирая это. В общем, результаты итерации не определены при этих обстоятельствах. Немного Реализация итераторов (включая те из общего назначения реализации коллекций, предоставляемых JRE) может выбрать, чтобы бросить это исключение, если это поведение обнаружено. Итераторы, которые делают это известные как отказоустойчивые итераторы, так как они быстро и чисто провалиться, скорее риск произвольный, недетерминированный поведение в неопределенное время в будущее.

Обратите внимание, что это исключение не всегда указывать, что объект имеет был одновременно изменен другая нить. Если один поток выдает последовательность методов вызовы, нарушающие договор объекта, объект может бросить это исключение. Например, если поток изменяет коллекцию напрямую пока он перебирает сбор с использованием итератора, работающего без сбоев, итератор бросит это исключение.

То есть для всех классов коллекции в JDK изменение в коллекции делает недействительными все ее итераторы (кроме того, который выполнил изменение).

Вы можете обойти это, используя индексы, а не итераторы, но для этого требуется список произвольного доступа, а связанные списки не обеспечивают эффективный произвольный доступ.

Поэтому, если вам действительно нужна такая структура данных, вам придется выйти за рамки JDK или реализовать ее самостоятельно.