How a list grows

In the previous lesson the list grew by itself, however many elements were added to it. Yet inside it sits an ordinary array, and an array's length, as you remember, never changes. So how does a list grow?

Back to the shelf. A shelf has a length: how many books fit on it. And there are the books standing on it right now. When the shelf is full and more books arrive, it is swapped for a shelf twice as long, and all the books are moved onto it. A list does the same:

var nums = new List<int>();
Console.WriteLine(nums.Count);    // 0
Console.WriteLine(nums.Capacity); // 0
nums.Add(7);
Console.WriteLine(nums.Count);    // 1
Console.WriteLine(nums.Capacity); // 4

Let's go through the program line by line:

1. new List<int>() creates an empty list: it has neither elements nor places for them.
2. That is why both Count and Capacity are 0.
3. nums.Add(7) puts in the first element. There were no places, so the list sets up an internal array with four places at once.
4. Now Count is 1 and Capacity is 4: one element, four places.

A list's two numbers

A list has two different numbers, and they are often mixed up:

• Count is how many elements the list holds. These are the books on the shelf.
• Capacity is how many places the internal array has. This is the length of the shelf.

The number of places in the internal array is called the list's capacity. Count is never greater than the capacity. While Count is smaller, Add puts the element into a free place, and nothing is copied.

When the places run out

When Count equals Capacity and one more element is added, the list does what is done with the shelf:

1. It creates a new array twice as long.
2. It copies every element of the old array into it.
3. It puts the new element into the first free place and works with the new array from then on.

The first Add to an empty list sets up four places, and after that the capacity doubles: 4, 8, 16, 32 and so on.

In the widget, nums.Count and nums.Capacity are shown next to the variable nums. They are not separate variables but the list's own two numbers at the current step. Press "Next step" and watch which Add changes the capacity.

A new array was needed only at the fifth Add: the first four elements went into free places. And RemoveAt lowered Count but not Capacity: removing gives no places back, and the array of eight places stays.

Here the shelf and the list part ways. A real shelf can be extended by nailing a second one next to it. An array cannot be extended: its length is set when it is created. So the list always takes a new array and copies the elements into it, and the program no longer needs the old array.

Why twice as long

Interviewers often ask this: why does a list double instead of growing by one place? Let's add 1,000 elements to an empty list and count the copies, that is, how many times elements move from an old array to a new one:

• if every Add added one place, it would move all the earlier elements: 0 + 1 + … + 999, that is 499,500 copies;
• with doubling, copying happens only 8 times, at capacities 4, 8, 16, …, 512: 4 + 8 + … + 512 = 1,020 copies.

So for 1,000 elements there is about one copy per element, and for any number of elements fewer than two. That is why Add is fast on average, even though once in a while it copies the whole list.

Places in advance

If the number of elements is known in advance, the places are set up at once: new List<string>(100). Then the first hundred Add calls create no new array at all.

var names = new List<string>(100);
Console.WriteLine(names.Count);    // 0
Console.WriteLine(names.Capacity); // 100
List<int> nums = [1, 2, 3];
Console.WriteLine(nums.Capacity);  // 3
nums.Add(4);
Console.WriteLine(nums.Capacity);  // 6

What happens here:

1. new List<string>(100) creates an empty list with a hundred places: Count is 0, Capacity is 100.
2. The list made from [1, 2, 3] gets exactly three places, none to spare.
3. The fourth element does not fit, and the capacity doubles to 6.

Common mistake

Places were set up in advance, and then elements were written by index:

var nums = new List<int>(10);
nums[0] = 5; // ✗

Unhandled exception. System.ArgumentOutOfRangeException: Index was out of range. Must be non-negative and less than the size of the collection. (Parameter 'index')

The program compiles, but when it runs it stops with an ArgumentOutOfRangeException. A capacity of 10 is ten places, not ten elements: Count is still 0, and there is no element at index 0. An index in a list must be less than Count, not Capacity, so elements go into such a list through Add.

Do not confuse it with an array: new int[10] creates ten elements filled with zeros, while new List<int>(10) is an empty list with ten places.

Key points

• Count is how many elements a list holds, Capacity how many places its internal array has.
• When the places run out, the list creates an array twice as long and copies the elements into it; the capacity grows like this: 4, 8, 16 and on.
• Doubling keeps copying rare: on average each element is copied fewer than two times.
• new List<int>(10) sets up places but holds no elements: an index must be less than Count.