An immutable list for readers that allows appends at the end and removal at the front.

ImmutableAppendOnlyList.cs

    /// <summary>
    /// A list that can be used by readers as a true immutable read-only list 
    /// and that supports relatively efficient "append to the end" and "remove 
    /// from the front" operations, by sharing the underlying array whenever 
    /// possible. Implemented as a class so it can be used to "CAS" when making 
    /// changes in order to allow lockless immutability.
    /// </summary>
    public class ImmutableAppendOnlyList<T> : IReadOnlyList<T>
    {
        private delegate void RangeCopier(IEnumerable<T> source, T[] dest, int destOffset, int count);
        private readonly T[] _values;
        private readonly int _head;
        private readonly int _count;

        private ImmutableAppendOnlyList(T[] values, int head, int count)
        {
            _values = values;
            _head = head;
            _count = count;
        }

        /// <summary>
        /// A "new" empty instance of a list.
        /// </summary>
        public static readonly ImmutableAppendOnlyList<T> Empty = new ImmutableAppendOnlyList<T>(new T[0], 0, 0);

        /// <summary>
        /// Creates a new list with the given items as the initial content.
        /// </summary>
        public static ImmutableAppendOnlyList<T> CreateFrom(IEnumerable<T> items)
        {
            if (items == null)
                return Empty;
            var values = items.ToArray();
            return values.Length == 0 ? Empty : new ImmutableAppendOnlyList<T>(values, 0, values.Length);
        }

        /// <summary>
        /// Creates a new list with the given initial capacity.
        /// </summary>
        public static ImmutableAppendOnlyList<T> Create(int initialCapacity)
        {
            return initialCapacity > 0 ? new ImmutableAppendOnlyList<T>(new T[initialCapacity], 0, 0) : Empty;
        }

        /// <summary>
        /// Returns the item at the given index.
        /// </summary>
        public T this[int itemIndex]
        {
            get
            {
                if ((uint)itemIndex > (uint)_count)
                    throw new IndexOutOfRangeException("itemIndex");
                return _values[_head + itemIndex];
            }
        }

        /// <summary>
        /// Returns the number of items in the list.
        /// </summary>
        public int Count
        {
            get { return _count; }
        }

        /// <summary>
        /// Returns whether the collection is empty, i.e. contains no items
        /// </summary>
        public bool IsEmpty
        {
            get { return _count == 0; }
        }

        /// <summary>
        /// Returns an enumerator over the items in the collection.
        /// </summary>
        public IEnumerator<T> GetEnumerator()
        {
            for (var i = _head; i < _count; i++)
                yield return _values[i];
        }

        /// <summary>
        /// Returns an enumerator over the items in the collection.
        /// </summary>
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return ((IReadOnlyList<T>)this).GetEnumerator();
        }

        /// <summary>
        /// Returns a new list with the given item appended to the end.
        /// </summary>
        public ImmutableAppendOnlyList<T> Append(T item)
        {
            var newCount = _count + 1;
            var tail = _head + _count;
            if (tail == _values.Length)
            {
                var newArray = GrowTo((newCount) * 2);
                newArray[_count] = item;
                return new ImmutableAppendOnlyList<T>(newArray, 0, newCount);
            }
            _values[tail] = item;
            return new ImmutableAppendOnlyList<T>(_values, _head, newCount);
        }

        /// <summary>
        /// Returns a new list with the given set of items appended to the end.
        /// </summary>
        public ImmutableAppendOnlyList<T> AppendRange(IEnumerable<T> items)
        {
            var nToAdd = 0;
            RangeCopier copier = CopyEnumerable;
            if (items != null)
            {
                var collectionType = items.GetType();
                if (collectionType.IsArray)
                {
                    nToAdd = ((T[])items).Length;
                    copier = CopyArray;
                }
                else if (typeof(System.Collections.ICollection).IsAssignableFrom(collectionType))
                {
                    nToAdd = ((System.Collections.ICollection)items).Count;
                    if (typeof(List<T>).IsAssignableFrom(collectionType))
                        copier = CopyList;
                }
                else
                    nToAdd = items.Count();
            }
            if (nToAdd == 0)
                return this;

            var newCount = _count + nToAdd;
            var tail = _head + _count;
            if (tail + nToAdd > _values.Length)
            {
                var newArray = GrowTo(_count + nToAdd * 2);
                copier(items, newArray, _count, nToAdd);
                return new ImmutableAppendOnlyList<T>(newArray, 0, newCount);
            }
            copier(items, _values, tail, nToAdd);
            return new ImmutableAppendOnlyList<T>(_values, _head, newCount);
        }

        /// <summary>
        /// Returns a new list from which the first element is removed.
        /// </summary>
        public ImmutableAppendOnlyList<T> RemoveFront()
        {
            return _count == 1 
                ? Empty 
                : new ImmutableAppendOnlyList<T>(_values, _head + 1, _count - 1);
        }

        /// <summary>
        /// Returns a new list from which the first element is removed, where
        /// this element is provided as output in <paramref name="removed"/>.
        /// </summary>
        public ImmutableAppendOnlyList<T> RemoveFront(out T removed)
        {
            removed = _values[_head];
            return _count == 1
                ? Empty 
                : new ImmutableAppendOnlyList<T>(_values, _head + 1, _count - 1);
        }

        /// <summary>
        /// Returns a new list from which the given number of first elements
        /// are removed.
        /// </summary>
        public ImmutableAppendOnlyList<T> RemoveFront(int nToRemove)
        {
            return nToRemove >= _count 
                ? Empty 
                : new ImmutableAppendOnlyList<T>(_values, _head + nToRemove, _count - 1);
        }

        /// <summary>
        /// Returns a new list from which the given number of first elements
        /// are removed and stored as output in the given list.
        /// </summary>
        public ImmutableAppendOnlyList<T> RemoveFront(int nToRemove, List<T> removed)
        {
            var remove = nToRemove > _count ? _count : nToRemove;
            if (removed != null)
                removed.AddRange(_values.Skip(_head).Take(remove));
            return remove == _count 
                ? Empty 
                : new ImmutableAppendOnlyList<T>(_values, _head + nToRemove, _count - 1);
        }

        /// <summary>
        /// Returns a new list from which all first elements that meet the 
        /// given predicate are removed and stored as output in the given list.
        /// </summary>
        public ImmutableAppendOnlyList<T> RemoveUntil(Predicate<T> shouldRemove, List<T> removed)
        {
            var newHead = _head;
            var tail = _head + _count;
            while (shouldRemove(_values[newHead]) && newHead < tail)
                newHead++;
            return newHead == _head
                ? this
                : (newHead == tail ? Empty : RemoveFront(newHead - _head, removed));
        }

        private T[] GrowTo(int newLength)
        {
            //newLength = Memory.Bits.NextPowerOf2(newLength);
            var newArray = new T[newLength];
            Array.Copy(_values, _head, newArray, 0, _count);
            return newArray;
        }

        private static void CopyArray(IEnumerable<T> source, T[] dest, int destOffset, int count)
        {
            Array.Copy((T[])source, 0, dest, destOffset, count);
        }

        private static void CopyList(IEnumerable<T> source, T[] dest, int destOffset, int count)
        {
            ((List<T>)source).CopyTo(0, dest, destOffset, count);
        }

        private static void CopyEnumerable(IEnumerable<T> source, T[] dest, int destOffset, int count)
        {
            // We want to guard against the source enumerable changing from 
            // under us. We do not add more than the given count, and throw 
            // if there is less.
            using (var enumerator = source.GetEnumerator()) 
            {
                for (int i = 0; i < count; i++)
                {
                    enumerator.MoveNext(); // should throw if we attempt to advance past the end.
                    dest[destOffset++] = enumerator.Current;
                }
            }
        }
    }

program.cs

    class Program
    {
        static void Main(string[] args)
        {
            BenchList();
            Console.ReadLine();
        }

        static void BenchList()
        {
            var nAppend = 10 * 1000 * 1000;
            var nRemoveImmutable = 1 * 1000 * 1000;
            var nRemoveList = 500;
            var nIndexSeq = 25;
            var nIndexRnd = 5;
            var nEnumerate = 25;
            var nRuns = 6;

            Time("Append    - Immutable List",
                nAppend, nRuns,
                (r, ops) => ImmutableAppendOnlyList<object>.Empty,
                (list, r, ops) => ImmutableListInsert(list, i => i, ops),
                null);
            Time("Append    - BCL List      ", 
                nAppend, nRuns, 
                (r, ops) => new List<object>(), 
                (list, r, ops) => ListInsert(list, i => i, ops), 
                (list, r, ops) => list.Clear());
            Time("Seq Index - Immutable List",
                nIndexSeq, nRuns,
                (r, ops) => ImmutableListInsert(ImmutableAppendOnlyList<object>.Empty, i => i, nAppend),
                (list, r, ops) => ListIndexSeq(list, ops),
                null);
            Time("Seq Index - BCL List      ",
                nIndexSeq, nRuns,
                (r, ops) => ListInsert(new List<object>(), i => i, nAppend),
                (list, r, ops) => ListIndexSeq(list, ops),
                (list, r, ops) => list.Clear());
            Time("Rnd Index - Immutable List",
                nIndexRnd, nRuns,
                (r, ops) => ImmutableListInsert(ImmutableAppendOnlyList<object>.Empty, i => i, nAppend),
                (list, r, ops) => ListIndexRnd(list, ops),
                null);
            Time("Rnd Index - BCL List      ",
                nIndexRnd, nRuns,
                (r, ops) => ListInsert(new List<object>(), i => i, nAppend),
                (list, r, ops) => ListIndexRnd(list, ops),
                (list, r, ops) => list.Clear());
            Time("Enumerate - Immutable List",
                nEnumerate, nRuns,
                (r, ops) => ImmutableListInsert(ImmutableAppendOnlyList<object>.Empty, i => i, nAppend),
                (list, r, ops) => ListEnumerate(list, ops),
                null);
            Time("Enumerate - BCL List      ",
                nEnumerate, nRuns,
                (r, ops) => ListInsert(new List<object>(), i => i, nAppend),
                (list, r, ops) => ListEnumerate(list, ops),
                (list, r, ops) => list.Clear());
            Time("Remove    - Immutable List", 
                nRemoveImmutable, nRuns, 
                (r, ops) => ImmutableListInsert(ImmutableAppendOnlyList<object>.Empty, i => i, nAppend), 
                (list, r, ops) => ImmutableListRemove(list, ops), 
                null);
            Time("Remove    - BCL List      ",
                nRemoveList, nRuns,
                (r, ops) => ListInsert(new List<object>(), i => i, nAppend),
                (list, r, ops) => ListRemove(list, ops),
                (list, r, ops) => list.Clear());
        }

        static void Time<TSut>(string operation, int nOps, int nRuns, Func<int, int, TSut> beforeRun, Action<TSut, int, int> performRun, Action<TSut, int, int> afterRun)
        {
            var times = new double[nRuns];
            var sp = new Stopwatch();
            for (var r = 0; r < nRuns; r++)
            {
                var sut = default(TSut);
                if (beforeRun != null)
                    sut = beforeRun(r, nOps);

                GC.Collect();
                GC.WaitForPendingFinalizers();
                Thread.SpinWait(10);

                sp.Restart();
                performRun(sut, r, nOps);
                sp.Stop();
                times[r] = sp.Elapsed.TotalMilliseconds;

                if (afterRun != null)
                    afterRun(sut, r, nOps);

                sut = default(TSut);
            }
            var avgMs = (times.Sum() - (times.Max() + times.Min())) / (nRuns - 2);
            var avgMsPerOp = avgMs / nOps;
            var avgOpsPerMs = nOps / avgMs;
            Console.WriteLine("{0}\t: {1:0.0} ms ({2:0.00000000} ms/op, {3:0.000} ops/ms)", operation, avgMs, avgMsPerOp, avgOpsPerMs);
        }

        static ImmutableAppendOnlyList<T> ImmutableListInsert<T>(ImmutableAppendOnlyList<T> list, Func<int, T> itemFactory, int nOps)
        {
            for (int i = 0; i < nOps; i++)
                list = list.Append(itemFactory(i));
            return list;
        }

        static List<T> ListInsert<T>(List<T> list, Func<int, T> itemFactory, int nOps)
        {
            for (int i = 0; i < nOps; i++)
                list.Add(itemFactory(i));
            return list;
        }

        static ImmutableAppendOnlyList<T> ImmutableListRemove<T>(ImmutableAppendOnlyList<T> list, int nOps)
        {
            for (int i = 0; i < nOps; i++)
                list = list.RemoveFront();
            return list;
        }

        static List<T> ListRemove<T>(List<T> list, int nOps)
        {
            for (int i = 0; i < nOps; i++)
                list.RemoveAt(0);
            return list;
        }

        static void ListIndexSeq<T>(IReadOnlyList<T> list, int nOps)
        {
            var val = default(T);
            for (var op = 0; op < nOps; op++)
            {
                for (var i = 0; i < list.Count; i++)
                    val = list[i];
            }
        }

        static void ListIndexRnd<T>(IReadOnlyList<T> list, int nOps)
        {
            var val = default(T);
            var rnd = new Random(1337 ^ 13);
            var count = list.Count;
            for (var op = 0; op < nOps; op++)
            {
                for (var i = 0; i < count; i++)
                    val = list[rnd.Next(count)];
            }
        }

        static void ListEnumerate<T>(IReadOnlyList<T> list, int nOps)
        {
            var val = default(T);
            for (var op = 0; op < nOps; op++)
            {
                foreach (var item in list)
                    val = item;
            }
        }
    }