Compact Array (Fast List)

It is often tempting to pick List<T> as the data structure of choice because of its ease of use, particularly for dynamic size handling. However, lists tend to be sub-optimal in hot loops and can easily fragment the memory when removing elements.

Here are several ways to have the best of both worlds:

ValueList<T>

This is wrapper around an array of struct that keeps the data compact in memory and handles dynamic resizing.

using System;

public struct ValueList<T> where T : struct
{
    private T[] _data;
    private int _count;

    public int Length { get { return _data.Length; } }
    public int Count { get { return _count; } }

    public void Allocate (int size)
    {
        _data = new T[size];
    }

    public T this[int index]
    {
        get { return _data[index]; }
        set { _data[index] = value; }
    }

    public void Add (T element)
    {
        if (_count == Length) Grow ();
        _data[_count++] = element;
    }

    public void Grow ()
    {
        T[] newData = new T[Length * 2];
        if (_count > 0) Array.Copy (_data, 0, newData, 0, _count);
        _data = newData;
    }

    public void Remove (int index)
    {
        int last = --_count;
        _data[index] = _data[last];
    }
}

ObjectList<T>

This version is nearly identical to ValueList<T> except for the Remove method.

using System;

public struct ObjectList<T> where T : class
{
    // Same as ValueList<T>

    public void Remove (int index)
    {
        int last = --_count;
        T temp = _data[last];
        _data[last] = null;
        _data[index] = temp;
    }
}