Best .NET Array/List

Question

So, I need an array of items. And I was wondering which one would be the fastest/best to use (in c#), I'll be doing to following things:

1. Adding elements at the end
2. Removing elements at the start
3. Looking at the first and last element (every frame)
4. Clearing it occasionally
5. Converting it to a normal array (not a list. I'm using iTween and it asks a normal array.) I'll do this almost every frame.

So, what would be the best to use considering these things? Especially the last one, since I'm doing that every frame. Should I just use an array, or is there something else that converts very fast to array and also has easy adding/removing of elements at the start & end?

Answer 1

Requirements 1) and 2) point to a Queue<T>, it is the only standard collection optimized for these 2 operations.

3) You'll need a little trickery for getting at the Last element, First is Peek().
4) is simple (.Clear())
5) The standard .ToArray() method will do this.

You will not escape copying all elements (O(n)) for item 5)

Answer 2

You could take a look at LinkedList<T>.

It has O(1) support for inspecting, adding and removing items at the beginning or end. It requires O(n) to copy to an array, but that seems unavoidable. The copy could be avoided if the API you were using accepted an ICollection<T> or IEnumerable<T>, but if that can't be changed then you may be stuck with using ToArray.

If your list changes less than once per frame then you could cache the array and only call ToArray again if the list has changed since the previous frame. Here's an implementation of a few of the methods, to give you an idea of how this potential optimization can work:

private LinkedList<T> list = new LinkedList<T>();

private bool isDirty = true;

private T[] array;

public void Enqueue(T t)
{
    list.AddLast(t);
    isDirty = true;
}

public T[] ToArray()
{
    if (isDirty) 
    {
        array = list.ToArray();
        isDirty = false;
    }

    return array;
}

Answer 3

I'm assuming you are using classes (and not structs)? (If you are using structs (value type) then that changes things a bit.)

The System.Collections.Generic.List class lets you do all that, and quickly. The only part that could be done better with a LinkedList is removing from the start, but a single block memory copy isn't much pain, and it will create arrays without any hassle.

I wouldn't recommend using a Linked List, especially if you are only removing from the start or end. Each addition (with the standard LinkedList collection) requires a memory allocation (it has to build an object to reference what you actually want to add).

Lists also have lots of convenient functions, which you need to be careful when using if performance is an issue. Lists are essentially arrays which get bigger as you add stuff (every time you overfill them, they get much bigger, which saves excessive memory operations). Clearing them requires no effort, and leaves the memory allocated to be used another day.

In personal experience, .NET isn't suited to generic Linked Lists, you need to be writing your code specifically to work with them throughout. Lists:

• Are easy to use

• Do everything you want

• Won't leave your memory looking like swiss cheese (well, as best you can do when you are allocating a new array every frame - I recommend you give the garbage collector the chance to get rid of any old arrays before making a new one if these Arrays are going to be big by re-using any array references and nulling any you don't need).

The right choice will depend heavily on the specifics of the application, but List is always a safe bet if you ask me, and you won't have to write any structure specific code to get it working.

If you do feel like using Lists, you'll want to look into these methods and properties:

• ToArray() // Makes those arrays you want

• Clear() // Clears the array

• Add(item) // Adds an item to the end

• RemoveAt(index) // index 0 for the first item, .Count - 1 for the last

• Count // Retrieves the number of items in the list - it's not a free lookup, so try an avoid needless requests

Sorry if this whole post is overkill.