应该使用哪个：数组vs链表？

我打算在不使用Queue类的情况下实现有界队列。 在阅读了Arrays和LinkedList优缺点之后，我更倾向于使用Array来实现队列function。 该系列将是固定尺寸。 我只想添加和删除队列中的项目。

就像是

 public class BoundedQueue { private T[] queue; int queueSize; public BoundedQueue(int size) { this.queueSize = size; queue = new T[size + 1]; } } 

代替

 public class BoundedQueue { private LinkedList queue; int queueSize; public BoundedQueue(int size) { this.queueSize = size; queue = new LinkedList(); } } 

由于效率和集合是固定大小的事实，我选择了Array。 想就此得到其他意见。 谢谢。

Answer 1

您当然应该使用Queue ，但在您提出的问题中，您说您不想使用队列而是自己实现队列。 您需要首先考虑此类的用例。 如果你想快速实现某些东西，你可以使用LinkedList但是对于通用库你可能想要更快的东西。

您可以使用.NET Reflector了解它是如何在.NET中实现的。 这些是它拥有的领域：

 private T[] _array; private const int _DefaultCapacity = 4; private static T[] _emptyArray; private const int _GrowFactor = 200; private int _head; private const int _MinimumGrow = 4; private const int _ShrinkThreshold = 0x20; private int _size; [NonSerialized] private object _syncRoot; private int _tail; private int _version; 

如您所见，它使用数组。 关于如何调整数组大小的许多领域也很复杂。 即使您正在实现有界数组，您也希望允许该数组大于容量，以避免不断地在内存中移动项目。

关于螺纹安全，两种类型都不提供任何保证。 例如，在LinkedList的文档中，它说：

此类型不是线程安全的。 如果需要多个线程访问LinkedList，则需要实现自己的同步机制。

Answer 2

嗯，这将是一个错误。 我猜你的是以前的C / C ++程序员，std :: list是王道。 从表面上看，它的内存非常节俭，不能使列表可能比仅分配你需要的内存更有效，对吗？ 是的，LinkedList就是这么做的。

但不，它与CPU缓存的工作方式非常不兼容，它们非常喜欢数组和仇恨指针。 将垃圾收集器置于其上，因此能够打包内存。

这里有读取和哭泣的基准测试。 斯塔克。

Answer 3

我不确定你为什么要排除在内部使用Queue ，特别是考虑到你要使用LinkedList （它们在同一个程序集中）。 Queue将为您提供最佳性能和内存使用率。 你的课可能看起来像这样：

 public class BoundedQueue { private Queue _queue; private int _maxSize; public BoundedQueue(int maxSize) { if (maxSize <= 0) throw new ArgumentOutOfRangeException("maxSize"); _queue = new Queue(maxSize); _maxSize = maxSize; } public int Count { get { return _queue.Count; } } /// 
 /// Adds a new item to the queue and, if the queue is at its /// maximum capacity, also removes the oldest item /// 
 ///  /// True if an item was dequeued during this operation; /// otherwise, false ///  public bool EnqueueDequeue(T value, out T dequeued) { dequeued = default(T); bool dequeueOccurred = false; if (_queue.Count == _maxSize) { dequeued = _queue.Dequeue(); dequeueOccurred = true; } _queue.Enqueue(value); return dequeueOccurred; } } 

但也许你有充分的理由排除我想不到的Queue课程？

Answer 4

您可以使用数组，只需要保持head元素的索引计数，或者每次添加内容时将所有内容都向下移动一下。 数组适合通过索引访问，链表适用于下一个/上一个和快速插入。

例如，如果你有[1,2,3,4,5]，并且头部是1，那么你加6，我猜你会减掉5，然后放6个。 6将是新头，但arrays的内容将是[1,2,3,4,6]。

Answer 5

所以这里是使用数组和链表的主要区别/优势/劣势：

数组： – 如果不在最后进行插入（以及删除），则向项目添加项目可能相对昂贵，因为必须移动所有数组元素。 – 如果在末尾添加对象，效率非常高 – 访问元素的速度非常快……只需指向地址即可！

LinkedList： – 在队列中的任何位置添加元素总是相同的成本，并且非常快 – 访问元素必须使用访问器（迭代器）。

所以你试图实现一个队列…但是什么样的队列？ 这一切都取决于你将用它做什么。

如果您实施先进先出（或后进先出）队列（如堆栈），最好使用链接列表，因为您始终可以使用相同的访问者访问列表的前端或后端。

但是如果你想要一个队列并且必须不断地在不同的地方访问你的元素，那就去找arrays吧！

从我对你的任务的理解，我会推荐一个链接列表…但你会知道最好的！

如果你开始在队列中有很多元素，这只会是一个问题。 如果你低于几千，它不会

希望能帮助到你

Answer 6

当元素超出其容量时，您的有界队列将如何表现？ 第一个项目会被推出，如[1, 2, 3] -> [2, 3, 4]还是最后一个项目会被替换为[1, 2, 3] -> [1, 2, 4] ？ 如果是前者，那么我建议使用LinkedList。 如果是后者，则数组或List 可以。 我只是想我会问，因为你的对象的行为将决定适当的行动方案，而这种行为从来没有被定义为我所知道的。 也许除了我之外的每个人都已经确切地知道你所谓的“有界队列”是什么意思，但我不想假设。