C# 数据结构，可以动态调整大小到给定限制的列表，并允许快速访问任何索引

如果希望队列是固定长度，可以使用循环缓冲区，该缓冲区启用 O(1( 排队、取消排队和索引操作，并在队列已满时自动覆盖旧条目。

尝试使用带有LinkedList的Dictionary。Dictionary的键是LinkedList节点的索引，Dictionary的值是 LinkedListNode 类型;即LinkedList节点。

字典会给你一个关于其操作的几乎O(1)，删除/添加LinkedListNode(s)到LinkedList的开头或结尾也是O(1)。

另一种选择是使用 HashTable .但是，在这种情况下，您必须事先知道表的容量(请参阅Hashtable.Add Method(才能获得O(1)性能：

如果 Count 小于哈希表的容量，则此方法为 O(1( 操作。如果需要增加容量以容纳新元素，则此方法将成为 O(n( 操作，其中 n 是 Count。

在第一个解决方案中，无论LinkedList或Dictionary的容量如何，您仍然可以从Dictionary和LinkedList中获得几乎O(1)。当然，这将是一个O(3)或O(4)，具体取决于您在内存类中执行Dictionary和LinkedList执行的操作总数，以执行添加或删除操作。搜索访问将始终是一个O(1)，因为您将仅使用Dictionary。

HashMap 适用于 Java，因此最接近的等价物是 Dictionary。C# Java HashMap 等效。但我不会说这是最终的答案。

• 如果将其实现为 Dictionary，哪个键 == 内容，那么您可以使用 O(1( 搜索内容。但是，您不能使用相同的密钥。另外，由于它不是订购的，您可能不知道第一个内容是什么。
• 如果将其实现为字典，哪个键==索引，值==内容，搜索内容仍然需要O(n(，因为您不知道内容的位置。
• 如果按索引引用搜索内容，列表或数组将花费 O(1(。因此，请仔细检查您的陈述，它需要 O(n(
• 如果您按索引搜索就足够了，那么@Lee提到的循环数组/缓冲区就足够了。
• 否则，与 DB 类似，您可能希望维护 2 个单独的数据：1 个用于存储数据(循环数组(，另一个用于搜索(哈希(。

编辑：@Lee说得对。循环缓冲区似乎可以为您提供所需的内容。不过答案留在原地。

我认为您想要的数据结构可能是优先级队列 - 这取决于您所说的"快速访问任何项目"是什么意思。如果您的意思是"能够枚举 O(N( 中的所有项目"，那么优先级队列符合要求。如果您的意思是"按历史顺序枚举列表"，那么它不会。

假设您需要这些操作;

• 添加项目并与时间关联
• 删除最旧的项目
• 以任意顺序枚举所有现有项

然后，您可以轻松扩展我不久前编写的这个优先级队列实现。

• 您需要将 IEnumerable 实现为从 0 到 cursor 的T[] data数组循环。这将为您提供枚举。
• 实现一个 GetItem(i( 函数，只要返回this.data[i] i <= cursor .

• 通过将其放入 Push(( 方法来实现自动大小限制;

  如果(队列。大小 => 10000( { 奎维尔啪((;}

我认为这是 O(ln n( 用于推送和弹出，O(N( 用于枚举所有项目，或 O(i( 用于查找任何项目，只要您不需要按顺序排列它们。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Mindfire.DataStructures
{
    public class PiorityQueue<T>
    {
        private int[] priorities;
        private T[] data;
        private int cursor;
        private int capacity;
        public int Size
        {
            get
            {
                return cursor+1;
            }
        }
        public PiorityQueue(int capacity)
        {
            this.cursor = -1;
            this.capacity = capacity;
            this.priorities = new int[this.capacity];
            this.data = new T[this.capacity];
        }
        public T Pop()
        {
            if (this.Size == 0)
            {
                throw new InvalidOperationException($"The {this.GetType().Name} is Empty");
            }
            var result = this.data[0];
            this.data[0] = this.data[cursor];
            this.priorities[0] = this.priorities[cursor];
            this.cursor--;
            var loc = 0;
            while (true)
            {
                var l = loc * 2;
                var r = loc * 2 + 1;
                var leftIsBigger = l <= cursor && this.priorities[loc] < this.priorities[l];
                var rightIsBigger = r <= cursor && this.priorities[loc] < this.priorities[r];
                if (leftIsBigger)
                {
                    Swap(loc, l);
                    loc = l;
                }
                else if (rightIsBigger)
                {
                    Swap(loc, r);
                    loc = r;
                }
                else
                {
                    break;
                }
            }
            return result;
        }
        public void Push(int priority, T v)
        {
            this.cursor++;
            if (this.cursor == this.capacity)
            {
                Resize(this.capacity * 2);
            };
            this.data[this.cursor] = v;
            this.priorities[this.cursor] = priority;
            var loc = (this.cursor -1)/ 2;
            while (this.priorities[loc] < this.priorities[cursor])
            {
                // swap
                this.Swap(loc, cursor);
            }
        }
        private void Swap(int a, int b)
        {
            if (a == b) { return; }
            var data = this.data[b];
            var priority = this.priorities[b];
            this.data[b] = this.data[a];
            this.priorities[b] = this.priorities[a];
            this.priorities[a] = priority;
            this.data[a] = data;
        }
        private void Resize(int newCapacity)
        {
            var newPriorities = new int[newCapacity];
            var newData = new T[newCapacity];
            this.priorities.CopyTo(newPriorities, 0);
            this.data.CopyTo(newData, 0);
            this.data = newData;
            this.priorities = newPriorities;
            this.capacity = newCapacity;
        }
        public PiorityQueue() : this(1)
        {
        }
        public T Peek()
        {
            if (this.cursor > 0)
            {
                return this.data[0];
            }
            else
            {
                return default(T);
            }
        }
        public void Push(T item, int priority)
        {
        }
    }
}