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

}

是否有现有的数据结构可以满足我的需求，或者有更好的实现该数据结构的方法？

- Chris Taylor

---

@Fabrizio 我在过去的问题中搜索了一下，但没有找到与我的规格相同的问题。我想除了实际解决方案外，我还在寻找“规范”或“最佳可能”的解决方案。 - Chris Taylor

听起来像是你想要一个循环缓冲区。这比从开始删除或使用ArrayList或LinkedList更高效。 - Peter Lawrey

我认为你的方法很不错，因为你使用了聚合，但考虑实现List接口。 - Rrr

我认为这不是重复的问题，因为他明确要求“列表具有最大存储容量，并在添加新数据时删除旧数据”，而在其他问题中并不清楚他想要什么，所有答案都创建了一个固定大小的列表，这些答案对于这个问题来说是不可接受的。 - Gavriel

我认为你想在这个问题上留下这个评论。 - Chris Taylor

Answer 1

我建议使用数组和两个索引来表示列表的头和尾。确保头部始终小于尾部，这样就能保证安全。

- jdevelop

---

一个循环访问的数组，我猜？ - Harry Lime

在这种情况下，添加操作将是O(n)，为了将所有元素移动到右侧。 - Rrr

@RuslanDzhabbarov 不需要移动循环缓冲区中的任何内容，只需移动指针即可 ;) - jdevelop

@jdevelop，现在我明白了你的意思，除非答案被编辑，否则无法点赞。 - Rrr

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

- Tom Jefferys

---

这个操作的复杂度将会是O(N)，所以我怀疑它是否可接受。 - jdevelop

由于相同的原因，不建议使用继承的方式，请使用“组合”模式。实现List接口，并添加一个私有字段List<T>innerList=new ArrayList<T>();(就像Chris在他的问题中一样)。 - Andreas Dolk

为什么在这个特定的例子中？是的，我同意通常组合比继承更好。然而，我认为这是一个特殊情况，在这种情况下，您需要利用继承带来的好处。 - Tom Jefferys

Chris已经使用了组合——建议用继承替换它应该附带一份解释。 - Andreas Dolk

Answer 3

这是一个基于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（单参数构造函数），但你也可以提供两个参数来指定其他类型的列表。

- Sean Patrick Floyd

---

@Andreas ??? 我确实在使用组合，但我使用了一个适配器类来简化事情。为什么要重复造轮子呢？List接口非常庞大，而ForwardingList为我提供了大多数方法的合理默认值，同时将所有逻辑委托给内部List。 - Sean Patrick Floyd

抱歉，你的声明在代码末尾，需要往下滚动查看。 ;) - Andreas Dolk

@Andreas 好的，我猜我可以召回我的黑帮杀手指令了 :-) - Sean Patrick Floyd

（嗯 - 也许我应该给你点个踩，因为你在类主体末尾声明字段，只是为了迎合你的坏人 fg） - Andreas Dolk

使用 Guava 的高级实现而不是 LinkedList，与原始提议的解决方案有什么区别？ - Rrr

add方法不会丢弃最旧的元素，一旦达到最大容量，它只是不再添加任何内容！您想修复它吗？ - Dave Moten

Answer 4

如果您扩展LinkedList类，您将直接访问所有其方法。而不是编写像这样的东西：

fixedList.getList().pop() 

你可以直接写

fixedList.pop()

你可以覆盖需要添加 maxSize 条件的方法。

- vichle

---

抱歉给你点踩，但我认为像他那样使用组合比你建议的继承更好。 - Andreas Dolk

请详细说明一下。他的方式为什么更好？ - vichle

这个主题有很多问答，以下是一个不错的起点：https://dev59.com/hG865IYBdhLWcg3wHKzu - Andreas Dolk

@Andreas_D 谢谢您澄清这个问题！听起来非常合理 :) - vichle