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

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.

Answer 2

You can use an array, you just have to keep count of the index of the head element, or move everything down by one each time you add something. Arrays are good for accessing by an index, linked lists are good for next/previous and fast insertion.

for instance, if you have [1,2,3,4,5], and the head is 1, you add 6, you'd drop 5 off the back I guess and put six in its place. 6 would be the new head, but the contents of the array would be [1,2,3,4,6].

Answer 3

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 4

How will your bounded queue behave when an element is added beyond its capacity? Will the first item be pushed out like this [1, 2, 3] -> [2, 3, 4] or will the last item be replaced like this [1, 2, 3] -> [1, 2, 4]? If the former, then I'd recommend a LinkedList. If the latter, an array or List<T> is fine. I just thought I'd ask since the behavior of your object will determine the appropriate course of action, and that behavior was never defined as far as I can tell. Maybe everyone but me just already knows exactly what you meant by a "bounded queue", but I didn't want to assume.

Answer 5

I'm not sure why you'd rule out using a Queue<T> internally, especially considering you're up for using a LinkedList<T> (they're in the same assembly). A Queue<T> would give you the greatest performance and memory usage. Your class could look something like this:

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

But maybe you had a good reason for ruling out the Queue<T> class that I just can't think of?