应使用：阵列VS链表？ [英] which should be used: array vs linked list?

问题描述

我打算实现一个界队列无需使用队列＆LT; T＆GT; 类。读阵列的优点和缺点后，和的LinkedList＆LT; T＆GT; ，我扶着更倾向于使用数组来实现队列功能。该系列将是固定大小。我只是想从队列中添加和删除的项目。

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.

像

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>();
   }
}

我选择，因为效率因这样的事实，集合是固定大小和数组。想获得这个其他人的意见。谢谢你。

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.

推荐答案

您当然应该使用队列＆LT; T＆GT; ，但在这个问题你说你不'T想用队列和自己，而不是执行队列。您需要首先考虑该类您的使用情况。如果你想实现的东西很快就可以使用的LinkedList＆LT; T＆GT; 但对于通用库，你会想要的东西更快

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.

您可以看到它是如何在.NET中通过使用.NET反射来实现。这些都是它具有以下字段：

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.

关于线程安全的，既不型提供任何保证。例如，文档在的LinkedList＆LT; T＆GT; 就这样说：

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

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

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.

这篇关于应使用：阵列VS链表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！