Java 中的最大大小列表

2022-09-04 03:15:12

对我来说,在Java中有一个数据结构很有用,它具有List的所有功能,但具有最大的存储容量,并且在添加较新的数据时会丢弃较旧的数据。可以想象,在某些时候,我可能希望实现一个固定大小的队列,它保持更一般的数据顺序,并将旧数据放在该顺序中的最低水平,但这是未来的。

目前,我正在像这样实现它:

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)满足我需求的现有数据结构,或者(b)实现此数据结构的更好方法?


答案 1

我会使用数组和2个索引作为列表的头部和尾部。确保头部始终<尾巴上,并且您是安全的。


答案 2

这是一个有大小限制的列表,基于番石榴转发列表

一个列表,它将其所有方法调用转发到另一个列表。子类应重写一个或多个方法,以根据装饰器模式根据需要修改后备列表的行为。

番石榴对于所有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(单个参数构造函数),但您也可以提供(两个参数构造函数)