which should be used: array vs linked list?

Question

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.

Answer 1

Well, it would be a mistake. I'm going to guess your are a former C/C++ programmer, std::list is king. On the surface, it is incredibly frugal with memory, can't make a list possibly more efficient than only allocating the memory you need, right? Yes, LinkedList does that.

But no, it is incredibly incompatible with the way CPU caches work, they really like arrays and hate pointers. Put the garbage collector on top of that, so quite capable of packing memory.

The read-them-and-weep benchmarks are here. Stark.

Answer 2

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.