哪种Collection类型最适合不断更新的固定大小的字符串数组？

I have come across a situation where I require a Collection type in Android that can hold String objects and meet the following criteria:

我遇到过一种情况，我需要Android中的Collection类型，它可以容纳String对象并满足以下条件：

• It has a fixed size (say 10) .
• 它有一个固定的大小（比如10）。
• Objects will only ever be added from one end of the Collection
• 只能从Collection的一端添加对象
• As a new object is added, all other objects automatically shuffle along one space to accommodate it.
• 添加新对象后，所有其他对象会自动沿着一个空间进行随机播放以适应它。
• If the Collection is full (all 10 spaces occupied), then as one object is added from one end, the object from the other end is removed.
• 如果Collection已满（占用所有10个空格），则从一端添加一个对象时，将删除另一端的对象。
• It is possible to iterate over the contents of the Collection in either direction at any time, and retrieve the object at each position.
• 可以随时在任一方向上迭代Collection的内容，并在每个位置检索对象。

From my experience with collection types, I felt something like a Queue or LinkedList would be suitable, although I have never used either one personally. However, some of the terminology in the Android Docs has me confused over whether they would meet my requirements.

根据我对集合类型的经验，我觉得像Queue或LinkedList这样的东西是合适的，尽管我从来没有亲自使用过任何一个。但是，Android Docs中的一些术语让我对它们是否符合我的要求感到困惑。

For instance, in the documentation for Queue, it is stated:

例如，在Queue的文档中，声明：

Queues typically, but do not necessarily, order elements in a FIFO (first-in-first-out) manner...

队列通常（但不一定）以FIFO（先进先出）方式对元素进行排序......

Which sounds ideal, but when I consider the add() and offer() methods, they both specify:

这听起来很理想，但是当我考虑add（）和offer（）方法时，它们都指定：

Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.

如果可以在不违反容量限制的情况下立即执行此操作，则将指定的元素插入此队列。

Which sounds like the opposite of what I am after.

这听起来与我所追求的相反。

For LinkedList, the description includes the following line:

对于LinkedList，描述包括以下行：

This class is primarily useful if you need queue-like behavior.

如果您需要类似队列的行为，则此类主要非常有用。

Which is perfect, but again later on it alludes to the fact that LinkedList is useful when a flexible size is required.

这是完美的，但后来再次强调，当需要灵活的大小时，LinkedList非常有用。

It may also be useful as a list if you expect your lists to contain zero or one element, but still require the ability to scale to slightly larger numbers of elements.

如果您希望列表包含零个或一个元素，但它仍然需要能够扩展到更大数量的元素，它也可能作为列表有用。

And on this tutorial site:

在本教程网站上：

The major benefit of linked lists is that you do not specify a fixed size for your list. The more elements you add to the chain, the bigger the chain gets.

链表的主要好处是您没有为列表指定固定大小。您添加到链中的元素越多，链就越大。

Would someone please be able to clarify whether one of these types would be suitable for my situation?

请有人能够澄清这些类型中的一种是否适合我的情况吗？

3 个解决方案

#1

There is a Collection that fits nearly all your requirements - it's the ArrayDeque!

有一个几乎符合您所有要求的Collection - 它就是ArrayDeque！

Unfortunately it falls short in one aspect, to quote:

不幸的是，它在一个方面不足，引用：

Array deques have no capacity restrictions; they grow as necessary to support usage.

阵列deques没有容量限制;他们根据需要增长以支持使用。

On the upside:

在好的方面：

This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

当用作堆栈时，此类可能比Stack快，并且在用作队列时比LinkedList更快。

Plus, if you base your design on an existing class, there is less space to make a mistake.

另外，如果您的设计基于现有的课程，那么出错的空间就会减少。

---

So, how do you change the ArrayDeque behavior to not resize when adding elements, but rather throw off old ones? Easy - all additions go through one of two methods: addFirst(E e) and addLast(E e). The methods are public, hence can be overriden.

那么，在添加元素时如何更改ArrayDeque行为以不调整大小，而是抛弃旧元素？简单 - 所有添加都通过以下两种方法之一：addFirst（E e）和addLast（E e）。这些方法是公开的，因此可以覆盖。

Thus, I present to you a version of ArrayDeque that does not resize:

因此，我向您展示了一个不调整大小的ArrayDeque版本：

private final int maxSize;
public MyArrayDeque(int maxSize) {
    super(maxSize);
    this.maxSize= maxSize;
}

@Override
public void addFirst(E e) {
    if (maxSize == size()) 
        removeLast();
    super.addFirst(e);
}

@Override
public void addLast(E e) {
    if (maxSize == size()) 
        removeFirst();
    super.addLast(e);
}

And that's it. Of course you should also modify the behavior of clone() and the serialization methods and what not if you want to be really thorough, but that's optional for most use cases. Also, don't show this code to any OOP purists, this isn't very nice usage of inheritance =)

就是这样。当然，您还应该修改clone（）和序列化方法的行为，如果您想要非常彻底，则应该修改它们，但对于大多数用例来说，这是可选的。另外，不要将此代码显示给任何OOP纯粹主义者，这不是很好用于继承=）

---

If you're striving for performance, you may want to actually copy the code from the class and do the modifications in-place. That will allow you to remove several checks and methods that are redundant when resizing is impossible. It will also allow for quicker for-loops without creating an Iterator (by simply taking the code in the Iterator - it's close in spirit to @T.J. Crowder's version, but uses bitwise operators, since the array is a power of 2 length).

如果您正在努力提高性能，您可能希望实际复制该类中的代码并进行就地修改。这将允许您在无法调整大小时删除多个冗余的检查和方法。它还可以在不创建迭代器的情况下实现更快的for循环（通过简单地在迭代器中获取代码 - 它与@ T.J.Crowder的版本精神接近，但是使用按位运算符，因为数组是2长度的幂）。

#2

LinkedList would certainly work. The "add" logic is just:

LinkedList肯定会奏效。 “添加”逻辑只是：

list.add(newItem);
if (list.size() > MAX_SIZE) {
    list.remove(0);
}

If you need hyper-efficiency, a String[MAX_SIZE] might be appropriate, with a current index saying where you were in it (e.g., a ring buffer). "Add" logic for that is:

如果你需要超效率，String [MAX_SIZE]可能是合适的，当前索引说明你在哪里（例如，一个环形缓冲区）。 “添加”逻辑是：

buffer[current] = newItem;
current = (current + 1) % MAX_SIZE;

That last line moves to the next spot, wrapping around to 0 again if necessary.

最后一行移动到下一个位置，必要时再次回到0。

Assuming you pre-fill it (e.g., it's never empty or partially-empty), looping logic in order added is:

假设你预先填充它（例如，它从不为空或部分为空），添加顺序的循环逻辑是：

for (int index = (current + 1) % MAX_SIZE; index != current; index = (index + 1) % MAX_SIZE) {
    // ...
}

If it may be empty or partially-empty, and assuming null isn't a valid non-empty value, you'd do the same thing but skip nulls.

如果它可能为空或部分为空，并且假设null不是有效的非空值，则您将执行相同的操作但跳过空值。

#3

Don't be lazy do it yourself!

不要懒得自己动手吧！

public class Collection<T> implements Iterable<T>, RandomAccess{
    private final Object[] data;
    private int size = 0;

    public enum Direction{
        LEFT,
        RIGHT
    }

    private Direction direction = Direction.LEFT;

    public Collection(int capacity){
        data = new Object[capacity];
    }

    public void setDirection(Direction direction){
        this.direction = direction;
    }

    public void add(T item){
        if(size < data.length){
            switch (direction){
                case LEFT:
                    data[data.length - size] = item; 
                    break;
                case RIGHT:
                    data[size] = item;
                    break;
            }
            size++;
        }
        else {
            switch (direction) {
                case LEFT:
                    System.arraycopy(data, 1, data, 0, data.length - 1);
                    data[0] = item;
                    break;
                case RIGHT:
                    System.arraycopy(data, 1, data, 0, data.length - 1);
                    data[data.length - 1] = item;
                    break;
            }
        }
    }

    public void remove(){
        if(size == 0){
            return;
        }
        switch (direction){
            case LEFT:
                remove(data.length - size);
                break;
            case RIGHT:
                remove(size);
                break;
        }
    }

    public int size(){
        return size;
    }

    private void remove(int index) {
        System.arraycopy(data, index + 1, data, index, data.length - 1 - index);
        data[data.length - 1] = null;
    }


    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            private int current = direction == Direction.RIGHT ? 0 : data.length - 1;

            @Override
            public boolean hasNext() {
                switch (direction){
                    case LEFT:
                        return current > 0;
                    case RIGHT:
                    default:
                        return current < data.length;
                }
            }

            @Override
            public T next() {
                current += direction == Direction.RIGHT ? 1 : -1;
                Object result = data[current];
                //noinspection unchecked
                return (T) result;
            }

            @Override
            public void remove() {
                Collection.this.remove(current + (direction == Direction.RIGHT ? -1 : 1));
            }
        };
    }
}