C# collections optimised for index 0 insert?

Question

What C# collections are best optimised for both zero-index insert and append to end?

I guess the easy one is LinkedList, but given my interest is in large byte-buffers, I suspect the memory cost per node may be prohibitively expensive for my needs.

My understanding is that a normal List has a buffer backing with a capacity usually larger than the actual data. When the data fills the buffer, a new buffer is created and the contents of the old are transferred to the new. That's great for appending to end, but horrible for growth on the beginning. My tests, appending/inserting a million random integers to a List:

• List Append time 0.014sec.
• List Zero-Insert time 173.343sec

Answer 1

A data structure which has the form of a list but is optimized for insertion and removal on both ends -- but not the middle -- is called a deque, which is short for "Double Ended QUEue". I do not know whether the standard library contains a deque these days.

If you are interested in techniques for constructing immutable deques, I suggest you read, in order of increasing complexity:

• My series of articles on immutable data types, specifically this one: https://blogs.msdn.microsoft.com/ericlippert/2008/02/12/immutability-in-c-part-eleven-a-working-double-ended-queue/
• This awesome SO question and answers: Implement an immutable deque as a balanced binary tree?
• Chris Okasaki's book "Purely Functional Data Structures" describes how to create a deque that is O(1) in all operations by clever use of lazy construction and memoization

Should you wish to create a mutable deque it is pretty straightforward to do so using the same techniques that a list. A list is just a wrapper around an array where the array is "too big" on the far end. To make a mutable deque you can make an array that is too big but the data sits in the middle, not at the small end. You just have to keep track of what the top and bottom indices of the data are, and when you bump up against either end of the array, re-allocate the array and copy the data to the middle.

Answer 2

You could create your own IList<T> implementation that contains two lists: one for items added to the front (stored in reverse order), and one for items added to the back (in proper order). This would ensure that all your inserts to the very beginning or end of the list are O(1) (except for the few cases where the capacity needs to be increased).

public class TwoEndedList<T> : IList<T>
{
    private readonly List<T> front = new List<T>();
    private readonly List<T> back = new List<T>();

    public void Add(T item)
    {
        back.Add(item);
    }

    public void Insert(int index, T item)
    {
        if (index == 0)
            front.Add(item);
        else if (index < front.Count)
            front.Insert(front.Count - index, item);
        else
            back.Insert(index - front.Count, item);
    }

    public IEnumerator<T> GetEnumerator()
    {
        return front.Reverse<T>().Concat(back).GetEnumerator();
    }

    // rest of implementation
}