Dynamic arrays: how List<T> grows

Arrays have a fixed size, but most of the time you do not know in advance how many items you will have. A dynamic array solves this. It keeps a normal array with some spare room, plus a count of how many slots are used. When the array is full, it allocates a bigger one and copies everything over. List<T> in .NET is exactly this.

Count vs Capacity

• Count: how many items you have added.
• Capacity: how many items fit in the hidden array before it must grow.

1var list = new List<int>();2Console.WriteLine($"Start: Count {list.Count}, Capacity {list.Capacity}");3 4for (int i = 1; i <= 9; i++)5{6    list.Add(i);7    Console.Write($"{list.Capacity} ");8}

Start: Count 0, Capacity 0
4 4 4 4 8 8 8 8 16 

The first Add allocates room for 4. The 5th finds it full, so a new array of 8 is created and the 4 items are copied over. The 9th grows it to 16. Try it, and compare with a list that grows by a fixed 4 slots each time:

Build your own List<T>

1public class SimpleList<T>2{3    private T[] _items = new T[4];4    private int _count;5 6    public int Count => _count;7    public int Capacity => _items.Length;8 9    public T this[int index]10    {11        get12        {13            if ((uint)index >= (uint)_count) throw new ArgumentOutOfRangeException(nameof(index));14            return _items[index];15        }16        set17        {18            if ((uint)index >= (uint)_count) throw new ArgumentOutOfRangeException(nameof(index));19            _items[index] = value;20        }21    }22 23    public void Add(T item)24    {25        if (_count == _items.Length)26            Grow();                       // rare: O(n)27        _items[_count++] = item;          // usual case: O(1)28    }29 30    public void RemoveAt(int index)31    {32        if ((uint)index >= (uint)_count) throw new ArgumentOutOfRangeException(nameof(index));33        _count--;34        // shift everything after index one slot left35        Array.Copy(_items, index + 1, _items, index, _count - index);36        _items[_count] = default!;        // let the GC free the old reference37    }38 39    private void Grow()40    {41        var bigger = new T[_items.Length * 2];42        Array.Copy(_items, bigger, _count);43        _items = bigger;                  // the old array becomes garbage44    }45}

Amortised O(1): why doubling works

A single Add that triggers a resize is O(n): it copies every item. So how can we say Add is O(1)? Look at the total work for n adds with doubling. Resizes happen at 4, 8, 16, 32… items, and copy 4 + 8 + 16 + … + n/2 items. That sum is less than n. So n adds cost at most n writes plus fewer than n copies: under 2n steps in total, about 2 per Add. The rare expensive Add is “paid for” by the many cheap ones. This is called amortised O(1).

Practical tips

• If you know roughly how many items you will add, say so: new List<Beam>(beamCount). No resizes at all.
• list.EnsureCapacity(n) grows once ahead of a big batch of adds.
• Capacity never shrinks on its own. After removing most items from a huge list, TrimExcess() gives the memory back.
• Removing many items with RemoveAt in a loop is O(n²). Use RemoveAll(predicate), which compacts the list in one O(n) pass.

1var readings = new List<int> { 5, -2, 7, -1, -9, 3 };2 3// Slow: each RemoveAt shifts the rest → O(n²)4// for (int i = readings.Count - 1; i >= 0; i--)5//     if (readings[i] < 0) readings.RemoveAt(i);6 7// Fast 1: one pass inside .NET8var a = new List<int>(readings);9a.RemoveAll(x => x < 0);10 11// Fast 2: compact by hand12var b = new List<int>(readings);13int write = 0;14for (int read = 0; read < b.Count; read++)15    if (b[read] >= 0) b[write++] = b[read];16b.RemoveRange(write, b.Count - write);   // drop the tail once17 18Console.WriteLine(string.Join(", ", a));19Console.WriteLine(string.Join(", ", b));

5, 7, 3
5, 7, 3