Максимальный список размеров в Java

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

В настоящий момент я реализую его так:

public class FixedSizeList<T> {

  private final int maxSize;
  private final LinkedList<T> list = new LinkedList<T>();

  public FixedSizeQueue(int maxSize) {
    this.maxSize = maxSize < 0 ? 0 : maxSize;
  }

  public T add(T t) {
    list.add(t);
    return list.size() > maxSize ? list.remove() : null;
  }

  // add remaining methods...

}

Существует ли (a) существующая структура данных, которая удовлетворяет мои потребности, или (б) лучший способ реализации этой структуры данных?

Ответ 1

Здесь Список с ограничением размера, основанным на Guava ForwardingList:

Список, который пересылает весь его метод звонки в другой список. Подклассы следует переопределить один или несколько методов для изменить поведение базы данных список по желанию на декоратор шаблон.

У Guava есть базовые классы, подобные этим для всех типов коллекции JDK-5. Каждый из них выполняет одну и ту же цель: упрощает добавление ценности, делегируя все функциональные возможности по умолчанию в базовую коллекцию.

public class LimitingList<E> extends ForwardingList<E> {

    private final class LimitingListIterator extends ForwardingListIterator<E> {

        private final ListIterator<E> innerListIterator;

        private LimitingListIterator(final ListIterator<E> innerListIterator) {
            this.innerListIterator = innerListIterator;
        }

        /**
         * {@inheritDoc}
         */
        @Override
        public void add(final E element) {
            if (inner.size() < maxSize)
                innerListIterator.add(element);
            else
                throw new IndexOutOfBoundsException();
        }

        @Override
        protected ListIterator<E> delegate() {
            return innerListIterator;
        }
    }

    public LimitingList(final int maxSize) {
        this(new ArrayList<E>(), maxSize);
    }

    public LimitingList(final List<E> inner, final int maxSize) {
        super();
        this.inner = inner;
        this.maxSize = maxSize;
    }

    @Override
    public boolean addAll(final Collection<? extends E> collection) {
        boolean changed = false;
        for (final E item : collection) {
            final boolean tmpChanged = add(item);
            changed = changed || tmpChanged;
            if (!tmpChanged)
                break;
        }
        return changed;
    }

    @Override
    public boolean add(final E e) {
        if (inner.size() < maxSize)
            return super.add(e);
        else
            return false;
    }

    @Override
    public ListIterator<E> listIterator() {
        return new LimitingListIterator(inner.listIterator());
    }

    @Override
    public void add(final int index, final E element) {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean addAll(final int index, final Collection<? extends E> elements) {
        throw new UnsupportedOperationException();
    }

    @Override
    public ListIterator<E> listIterator(final int index) {
        return new LimitingListIterator(inner.listIterator(index));
    }

    private final int maxSize;
    private final List<E> inner;

    @Override
    protected List<E> delegate() {
        return inner;
    }

}

Он делегирует всю реальную функциональность базовому списку, который является ArrayList для каждого по умолчанию (конструктор одиночных аргументов), но вы также можете предоставить (два конструктора аргументов)

Ответ 2

Я бы использовал массив и 2 индекса для головы и хвоста списка. Убедитесь, что голова всегда < хвост, и вы в безопасности.

Ответ 3

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

Лично я бы расширил один из существующих классов списка, чтобы получить функциональность, и переопределить методы добавления. Таким образом, вы получаете все остальные операции списка бесплатно. т.е. что-то вроде следующего...

public class FixedSizeArrayList<T> extends ArrayList<T> {
    private final int maxSize;
    public FixedSizeArrayList(int maxSize) {
        super();
        this.maxSize = maxSize
    }

    public boolean add(T t) {
        if (size() >= maxSize) {
            remove(0);
        }
        return super.add(t);
    }

    // implementation of remaining add methods....
}

Ответ 4

Если вы расширите класс LinkedList, у вас будет прямой доступ ко всем его методам. Вместо того, чтобы писать такие вещи, как

fixedList.getList().pop()

вы можете просто написать

fixedList.pop()

Затем вы можете переопределить методы, в которых вам нужно добавить критерии maxSize.