C# · Course navigation

C#: watching List<T> grow geometrically

Observe the capacity of a List<int> as items are added and see that reallocations become rarer.

On this page

Before you start

C# generic collections.

Observe the capacity of a List<int> as items are added and see that reallocations become rarer.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

List<T> keeps its items in an array. Count is the number of items and Capacity is the size of the underlying array. When Count would exceed Capacity, the list allocates a new array with twice the capacity and copies the items into it.

Because the capacity doubles, the number of reallocations over n additions is only about log2(n), and the total copying work is proportional to n. Each Add is therefore amortized O(1), even though an individual Add occasionally costs O(n). The exact growth pattern (0, then 4, then doubling) is an implementation detail of .NET, so rely on the idea, not on the specific numbers.

Code example

using System;
using System.Collections.Generic;

class Program {
  static void Main() {
    var list = new List<int>();
    int last = list.Capacity;
    Console.WriteLine("capacity " + last + " after 0 items");
    for (int i = 1; i <= 33; i++) {
      list.Add(i);
      if (list.Capacity != last) {
        last = list.Capacity;
        Console.WriteLine("capacity " + last + " after " + i + " items");
      }
    }
  }
}

Output

capacity 0 after 0 items
capacity 4 after 1 items
capacity 8 after 5 items
capacity 16 after 9 items
capacity 32 after 17 items
capacity 64 after 33 items

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1using System;

2using System.Collections.Generic;

4class Program {

5 static void Main() {

6 var list = new List<int>();

7 int last = list.Capacity;

8 Console.WriteLine("capacity " + last + " after 0 items");

9 for (int i = 1; i <= 33; i++) {

10 list.Add(i);

11 if (list.Capacity != last) {

12 last = list.Capacity;

13 Console.WriteLine("capacity " + last + " after " + i + " items");

14 }

15 }

16 }

17}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
A new list starts with capacity 0 and allocates nothing.	`Capacity = 0`	capacity 0 after 0 items
Most additions just write into spare capacity.	`Count rises by 1`	capacity 0 after 0 items
A line is printed only when the array is reallocated: at items 1, 5, 9, 17, and 33.	`Capacity doubles each time`	capacity 0 after 0 items capacity 4 after 1 items capacity 8 after 5 items capacity 16 after 9 items capacity 32 after 17 items capacity 64 after 33 items

Behind the scenes

How C# processes this code

C# compiles to code for the .NET runtime, which invokes the program entry point.

Cost and common mistakes

Add is amortized O(1); n additions cost O(n) total time and O(n) space.

Growth rules are not part of the language contract. Do not depend on exact capacities in real programs.
If you know the final size, pass it to the List constructor to avoid all intermediate copies.

Try it yourself

Why does capacity jump at 5 items rather than 4?

Reveal answer and reasoning

Capacity is 4 after the first Add, so four items fit. The fifth item does not fit, so the array is doubled to 8.