应该使用哪个：数组vs链表？(which should be used: array vs linked list?)

应该使用哪个：数组vs链表？(which should be used: array vs linked list?)

我打算在不使用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>(); } }

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

I am planning to implement a bounded queue without using the Queue<T> class. After reading pros and cons of Arrays and LinkedList<T>, I am leaning more towards using Array to implement queue functionality. The collection will be fixed size. I just want to add and remove items from the queue.

something like

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

instead of

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

I have selected Array because of efficiency and due to the fact that collection is fixed size. Would like to get other opinions on this. Thanks.

最满意答案

您当然应该使用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，则需要实现自己的同步机制。

You should of course use a Queue<T>, but in the question you said that you don't want to use queue and instead implement the queue yourself. You need to consider first your use case for this class. If you want to implement something quickly you can use a LinkedList<T> but for a general purpose library you would want something faster.

You can see how it is implemented in .NET by using .NET Reflector. These are the fields it has:

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;

As you can see it uses an array. It is also quite complicated with many fields concerned with how the array should be resized. Even if you are implementing a bounded array you would want to allow that the array can be larger than the capacity to avoid constantly moving items in memory.

Regarding thread safety, neither type offers any guarantees. For example in the documentation for LinkedList<T> it says this:

This type is not thread safe. If the LinkedList needs to be accessed by multiple threads, you will need to implement their own synchronization mechanism.