which should be used: array vs linked list?

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.queue开发者_开发知识库Size = 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.

---

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.

---

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.

---

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?

---

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].

---

So here are the main difference/avantages/disavantages of using both arrays and linked-lists:

Arrays: - Adding items to arrays can be relatively costly if the insertion is not made at the end (as well as deleting) because all the array elements have to be moved. - Very efficient if object are added at the end - Access to the elements is very fast... Simply point to the adress!

LinkedList: - Adding elements anywhere in the queue is always the same cost in time, and is very fast - Accessing the elements has to be done with an accessor (iterator).

So your trying to implement a queue... but what kind of queue? It all depends on what you will do with it.

If your implementing First In First Out (or Last In Last Out) queue (like a stack), you are better off using a Linked-List, since you can always use the same accessor to access the front or back-end of your list.

But if you want a queue and have to constantly access your elements at different places, go for the array!

From what I understood of your task, I would have recommended a Linked List... but you will know best!

This will only be a problem if you start having ALOT of elements in your queue. If you stay below the few thousands, it doesn

hope it helps

---

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.