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

Question

我计划实现一个有界队列，而不使用Queue<T>类。在阅读Arrays和LinkedList<T>的优缺点后，我更倾向于使用Array来实现队列功能。集合大小将是固定的，我只想从队列中添加和删除项目。

例如：

public class BoundedQueue<T>
{
   private T[] queue;
   int queueSize;

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

替代

public class BoundedQueue<T>
{
   private LinkedList<T> queue;
   int queueSize;

   public BoundedQueue(int size)
   {
      this.queueSize = size;
      queue = new LinkedList<T>();
   }
}

我选择使用数组是因为它的效率高，而且集合大小是固定的。希望能听到其他人的意见。谢谢。

- stackoverflowuser

---

经典的速度与效率之争。对于计算机来说，数组会更快，但链表很可能需要更少的代码行数。决定权完全掌握在你手中！ - virstulte

Answer 1

嗯，这是一个错误。我猜你以前是C/C++程序员，std::list是王者。表面上看，它非常节省内存，只分配所需的内存，不能使列表更有效率，对吧？是的，LinkedList就是这样。

但实际上，它与CPU缓存的工作方式非常不兼容，它们非常喜欢数组，不喜欢指针。再加上垃圾收集器，因此可以很好地压缩内存。

阅读并哭泣的基准测试在这里。明显。

- Hans Passant

---

不幸的是，链接已经失效。这是我在网络档案馆上能找到的最后一篇文章。 - StuartLC

Answer 2

当然，你应该使用 Queue<T>，但在问题中，你说你不想使用队列，而是要自己实现队列。首先需要考虑这个类的使用情况。如果你想快速实现某些功能，可以使用 LinkedList<T>，但对于一个通用的库，你需要更快的东西。

你可以通过使用 .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<T> 的文档中，它说：

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

- Mark Byers

---

设置容量如何使用更少的内存？它正在执行相同的操作（保留内存）。 - SoapBox

@Mark：谢谢。你知道 .net 类 Queue<T> 是使用数组还是链表 LinkedList<T> 实现的吗？ - stackoverflowuser

@stackoverflowuser：是的，你可以在.NET Reflector中看到。它是一个T类型的数组。 - Mark Byers

@Mark：关于“但是依赖IndexOutOfRangeException来使你的代码正确运行是不好的风格”，我们不能在入队或出队项目之前检查数组是否已满或为空吗？我不明白依赖IndexOutOfRangeException背后的意义。您能否详细解释一下？ - stackoverflowuser

@stackoverflowuser：在入队或出队前，我们不能只检查数组是否已满或是空的吗？是的，你应该这样做。“我不明白为什么要依靠IndexOutOfRangeException。” 关键在于你不应该这样做。 - Mark Byers

Answer 3

我不确定为什么你会排除在内部使用 Queue<T>，特别是考虑到你要使用 LinkedList<T>（它们在同一个程序集中）。Queue<T> 将为您提供最佳的性能和内存使用率。您的类可能如下所示：

public class BoundedQueue<T>
{
    private Queue<T> _queue;
    private int _maxSize;

    public BoundedQueue(int maxSize)
    {
        if (maxSize <= 0)
            throw new ArgumentOutOfRangeException("maxSize");

        _queue = new Queue<T>(maxSize);
        _maxSize = maxSize;
    }

    public int Count
    {
        get { return _queue.Count; }
    }

    /// <summary>
    /// Adds a new item to the queue and, if the queue is at its
    /// maximum capacity, also removes the oldest item
    /// </summary>
    /// <returns>
    /// True if an item was dequeued during this operation;
    /// otherwise, false
    /// </returns>
    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<T>类？

- Dan Tao

---

谢谢。我也不能使用LinkedList<T> :) 但是为了比较Array和LinkedList<T>的实现时间，我使用了它。我发现Array的实现更快。如果LinkedList<T>更快，我会在不使用.net类的情况下实现它。希望这解释了我的情况。 - stackoverflowuser

Answer 4

你可以使用数组，只需保持头元素索引的计数，或每次添加元素时将所有元素向下移动一位。 数组适用于按索引访问，链表适用于下一个/上一个和快速插入。

例如，如果你有[1,2,3,4,5]，并且头部是1，你添加6，你会把5放在后面，然后把6放在它的位置。 6将成为新的头部，但数组的内容将是[1,2,3,4,6]。

- gtrak

Answer 5

那么这里是使用数组和链表的主要区别/优点/缺点：

数组： - 如果插入（以及删除）不在末尾，则向数组添加项可能相对昂贵，因为必须移动所有数组元素。 - 如果对象添加在末尾，则非常高效 - 访问元素非常快...只需指向地址！

链表： - 在队列中任何位置添加元素始终具有相同的时间成本，并且非常快 - 访问元素必须使用访问器（迭代器）。

所以你正在尝试实现一个队列...但是什么样的队列呢？ 这完全取决于您将如何使用它。

如果您正在实现先进先出（或后进先出）队列（例如堆栈），则最好使用链表，因为您始终可以使用相同的访问器来访问列表的前端或后端。

但是，如果您想要一个队列并且必须不断地访问不同位置的元素，请选择数组！

根据我对您任务的理解，我会推荐使用链表...但是您最了解自己的需求！

只有在队列中有大量元素时，才会出现这个问题。如果你保持在几千以下，就不会有问题。

希望能帮到你。

- David Menard

---

这是一个具有先进先出（FIFO）特性的有界队列。 - stackoverflowuser

由于它是有界限的，您可以在不移动所有内容的情况下添加元素。只需跟踪头索引，并通过添加head + index并使用模运算来计算任何元素的真实索引。 - gtrak

Answer 6

当元素添加到有界队列中时，它的容量是否会被超出？第一个元素将像这样被推出 [1, 2, 3] -> [2, 3, 4] 还是最后一个元素将被替换成这样 [1, 2, 3] -> [1, 2, 4]？如果是前者，则建议使用 LinkedList。如果是后者，则可以使用数组或 List<T>。我只是想问一下，因为您的对象的行为将决定适当的操作，而且我无法确定该行为是否已经定义好了。也许除了我之外，每个人都已经知道您所说的“有界队列”的确切含义，但我不想做任何假设。

- mattmc3

---

超出容量后，它将抛出QueueFullException异常。 - stackoverflowuser