Java中的最大大小列表

Question

在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)实现此数据结构的更好方法？

Answer 1

我会使用数组和2个索引作为列表的头部和尾部.确保头部总是<尾部,你是安全的.

Answer 2

除非您想使用实际的数组,否则我不相信您可以使用的列表类型数据结构.

我个人会扩展一个现有的列表类来获取功能,并覆盖添加方法.这样您就可以免费获得所有其他列表操作.即如下所示......

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

Answer 3

这里有一个大小限制的基础上,列出番石榴的ForwardingList:

将所有方法调用转发到另一个列表的列表.子类应覆盖一个或多个方法,以根据装饰器模式根据需要修改支持列表的行为.

对于所有JDK-5 Collection类型,Guava都有这样的基类.它们中的每一个都实现了相同的目的:在将所有默认功能委派给底层集合时,可以轻松增加价值.

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(单个参数构造函数),但您也可以提供(两个参数构造函数)