List
An array that grows
An array has a fixed length, so a program that collects an unknown number of items cannot use one without counting first. List<T> is an array with a length that grows: it holds a buffer, keeps the number of used slots in Count, and allocates a bigger buffer when the slots run out.
var list = new List<string> { "a", "b" };
list.Add("c");
list.Insert(0, "z");
list.Remove("b");
Console.WriteLine(string.Join(",", list));
Console.WriteLine($"count: {list.Count} capacity: {list.Capacity}");
Console.WriteLine(list.Contains("c"));
list.Sort();
Console.WriteLine(string.Join(",", list));
Console.WriteLine(list[^1]);
dotnet run
z,a,c
count: 3 capacity: 4
True
a,c,z
z
The output is the history of the list in order. It started as
a, b, gained c at the end,
gained z at the front, lost
b, and was then sorted.
Remove takes the first equal element and returns
whether it found one; a value that is not there leaves the list alone.
Sort orders the elements with the default comparison
of the type, which for string is the culture-aware
order of the current culture. A list of a type with no comparison throws
InvalidOperationException at that call.
Add, Remove, Insert and Sort
The operations a program uses most, with what each costs:
- Add appends and is cheap: a write into the next free slot, and a new buffer only when the slots run out.
- Insert(0, x) and RemoveAt(0) move every element after the position, so they cost the length of the list.
- Contains, IndexOf and Remove(value) compare element by element until they find a match.
- Sort is a comparison sort and costs about n log n comparisons.
A list that is filled once and then only read is better off as an array: ToArray() copies the elements into one, and the result cannot change size behind the reader.
Count and Capacity
Two numbers describe a list, and they are not the same: Count is how many elements it holds and Capacity is how many fit before the buffer grows. The list above held three elements with room for four.
var numbers = new List<int> { 3, 1, 2 };
numbers.AddRange(new[] { 5, 4 });
int[] asArray = numbers.ToArray();
Console.WriteLine(asArray.Length);
Console.WriteLine(numbers.IndexOf(5));
Console.WriteLine(string.Join("-", numbers));
numbers.RemoveAt(0);
Console.WriteLine(numbers.Count);
dotnet run
5
3
3-1-2-5-4
4
At seven elements the capacity of a list of this runtime becomes 8, and it
doubles from there: 8, 16, 32. That doubling is why an
Add is cheap on average even though one of them
copies the whole buffer: the copies get rarer as the list grows.
A program that knows the final count should pass it:
new List<int>(capacity: 10000) allocates once
and skips every copy. The capacity is a hint about the buffer and never
about the contents, so Count stays 0.
Exercises
- Add a hundred elements one at a time and print the capacity after each doubling. At which counts does it change?
- Remove an element that is not in the list and print the return value. What does it say?
- Sort a list of { "beta", "Alpha" } and print it. Which order does the current culture give?
- Insert into the middle of a list of ten thousand elements and compare the time with an Add. What does the difference come from?
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What is the difference between Count and Capacity of a list?
Answer
Count is the number of elements; Capacity is how many fit before the buffer grows
The buffer usually has spare slots, so Capacity is at least Count and grows in steps as elements are added.
-
Which operation costs the length of the list?
Answer
Insert at the front
An insertion at the front moves every element one slot to the right; Add writes into a free slot.
-
What does this program print?
var list = new List<int> { 1, 2 }; list.Add(3); Console.WriteLine(list.Count); Console.WriteLine(list[^1]);Answer
3 / 3
The list holds three elements after the Add, and ^1 names the last one, which is 3.
-
What does this program print?
var list = new List<string> { "a", "b", "c" }; list.Remove("b"); Console.WriteLine(string.Join(",", list));Answer
a,c
Remove takes the first equal element out and leaves the rest in order, so b is gone.
-
What does Remove return?
Answer
True when it found and removed an element
The bool says whether the value was there, which a caller uses to decide what to do next.
-
What does this program print?
var list = new List<int> { 3, 1, 2 }; list.Sort(); Console.WriteLine(string.Join("-", list));Answer
1-2-3
Sort orders the elements in place with the default comparison, so the numbers come out ascending.
-
How do you copy the elements of a list into a fixed array?
Answer
ToArray()
ToArray allocates an array of Count elements and copies them, which is the independent snapshot a reader wants.
-
What does this program print?
var list = new List<int> { 1, 2, 3 }; list.RemoveAt(0); Console.WriteLine(list[0]); Console.WriteLine(list.Count);Answer
2 / 2
RemoveAt takes the element out at that position, so the second element becomes the first and the count drops by one.
-
What does Contains compare?
Answer
Element by element with the equality of the type, until a match
Contains walks the elements and uses Equals on each, which is value equality for string and int.
-
When is an array better than a list?
Answer
When the number of elements is known and fixed and the data is only read
A fixed array is one allocation with no spare capacity and no growth path, which is exactly what a read-only table wants.
The code on this page was built with the .NET SDK 10.0.303 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev