Arrays as contiguous memory, O(1) indexing, List<T> as a growable array with capacity doubling, amortised O(1) Add, and when to use arrays, lists, spans and pooled buffers.
An array is a fixed-size block of contiguous elements of one type. Element i lives at start + i × elementSize, so indexing is O(1) and iteration is very cache-friendly. Its size cannot change.
List<T> wraps an internal array plus a Count. When the array is full, Add allocates a new array about twice as large and copies the elements, so Add is amortised O(1) but occasionally O(n). Inserting or removing in the middle is O(n) because elements shift.
Use an array for fixed-size data and hot paths, List<T> when the size changes, set Capacity when you know the size, and Span<T>/Memory<T> to work on slices without copying.
int[] numbers = { 10, 20, 30, 40 };
address: 1000 1004 1008 1012
┌──────┬──────┬──────┬──────┐
│ 10 │ 20 │ 30 │ 40 │ numbers[2] = *(1000 + 2*4) = 30
└──────┴──────┴──────┴──────┘
For reference types the array holds references (8 bytes each in a 64-bit process) that point to objects elsewhere on the heap, so iterating a Customer[] still jumps around memory.
| Operation | Array | List<T> |
|---|---|---|
| Index read/write | O(1) | O(1) |
| Add at end | n/a (fixed size) | Amortised O(1) |
| Insert/remove in middle | n/a | O(n) (shift) |
| Search unsorted | O(n) | O(n) |
| Search sorted | O(log n) with Array.BinarySearch |
O(log n) with BinarySearch |
| Memory overhead | Header + elements | Backing array + count + version, plus spare capacity |
List<T> growsnew List<int>() capacity 0
Add #1 capacity 4 (allocate)
Add #5 capacity 8 (allocate + copy 4)
Add #9 capacity 16 (allocate + copy 8)
...
Adding n items copies fewer than n items in total → amortised O(1) per Add
A list of 1 million ints grows about 18 times, and every backing array from 32 KB upwards (21,250+ ints) lands on the Large Object Heap, which is only collected in gen 2.
| Need | Choose |
|---|---|
| Fixed size, hot loop, interop | T[] |
| Size changes, general purpose | List<T> (pre-sized when you can) |
| Look at part of an array or string without copying | Span<T> / ReadOnlySpan<T> |
Same, but stored in a field or across await |
Memory<T> |
| Large temporary buffer | ArrayPool<T>.Shared.Rent |
| Read-only data shared across threads | ImmutableArray<T> or FrozenSet<T> / FrozenDictionary |
An export endpoint built a List<ReportRow> of 2 million rows with Add and no capacity, then called ToArray(). Each growth step allocated a bigger array on the LOH, and the final copy doubled memory again. Setting new List<ReportRow>(expectedCount) and returning the list directly (or streaming rows with IAsyncEnumerable<T>) cut peak memory by more than half and removed several gen 2 GCs per request.
Checks the fundamentals that every other data structure builds on.
Green flags
List<T> is a growable array with doubling and amortised O(1) Add.Span<T>, ArrayPool<T>, CollectionsMarshal.AsSpan and the Large Object Heap.Red flags
List<T> is a linked list.Add is usually fast but sometimes slow.i.arr[0] of an int[] also brings arr[1..15] into cache, and the prefetcher pulls the next lines ahead of time. Sequential loops over arrays of structs are the fastest data access pattern you can write.0 <= i < Length on each access, but the JIT removes the check in simple for (int i = 0; i < arr.Length; i++) loops and when iterating a span with foreach.Point[] (struct) [x,y][x,y][x,y][x,y] contiguous data
Customer[] (class) [ref][ref][ref][ref]
│ │ │ └──► object somewhere on heap
│ │ └───────► object
...
int[,] is one block with row-major layout; indexing is slower than jagged arrays because of extra bounds and offset maths.int[][] is an array of arrays; rows can differ in length and each row is its own object.List<T>public class List<T>
{
private T[] _items;
private int _size;
private int _version; // detects modification during foreach
}
foreach over a list throws InvalidOperationException if you modify it during enumeration (the _version check).TrimExcess() shrinks capacity when less than 90% of it is used.CollectionsMarshal.AsSpan(list) gives a Span<T> over the backing array for fast loops. Do not add or remove items while using it, because a resize leaves the span pointing at the old array.EnsureCapacity(n) grows once ahead of a bulk add, and AddRange with an ICollection<T> sizes the array in one step.Span<T>, Memory<T> and poolingSpan<T> is a ref struct view (reference + length) over arrays, stack memory or native memory. Slicing is free: no copy. Because it is a ref struct it cannot be stored on the heap or used across await.Memory<T> is the heap-storable version for async code; call .Span when you need to process it.ArrayPool<T>.Shared.Rent(n) reuses large temporary arrays instead of allocating new ones, which avoids LOH churn. The rented array can be larger than requested, so always track the length you used.int[] a = [1, 2, 3];) and stackalloc for small fixed buffers (Span<byte> buf = stackalloc byte[256];).ints from an int[], a List<int> and a LinkedList<int>.new List<int>() versus new List<int>(1_000_000) and compare allocated bytes with [MemoryDiagnoser].list.Capacity after each Add for the first 20 items to see the doubling.// Pre-size when you know (or can estimate) the count
var rows = new List<ReportRow>(capacity: expectedCount);
foreach (var order in orders)
rows.Add(ReportRow.From(order));
// Fast loop over a list's backing array (no bounds checks per element, no enumerator)
long total = 0;
foreach (ref readonly var row in CollectionsMarshal.AsSpan(rows))
total += row.Amount;
// Slicing without copying
int[] samples = LoadSamples();
Span<int> lastHour = samples.AsSpan(samples.Length - 3600);
int max = 0;
foreach (var s in lastHour) max = Math.Max(max, s);
// Temporary large buffer from the pool instead of new byte[1_000_000]
byte[] buffer = ArrayPool<byte>.Shared.Rent(1_000_000);
try
{
int read = await stream.ReadAsync(buffer.AsMemory(0, 1_000_000), ct);
Process(buffer.AsSpan(0, read));
}
finally
{
ArrayPool<byte>.Shared.Return(buffer);
}
Mistake: Adding many items to a List<T> without setting capacity.
Why it is wrong: Each growth allocates a bigger array and copies everything, creating garbage, and for large lists every step allocates on the Large Object Heap.
Instead: Pass the expected count to the constructor or call EnsureCapacity before a bulk add.
Mistake: Inserting or removing at the front of a large list in a loop.
Why it is wrong: Each operation shifts all later elements, making the loop O(n²).
Instead: Use Queue<T> for FIFO work, build a new list in one pass, or use RemoveAll(predicate).
Mistake: Calling ToList() or ToArray() repeatedly "just in case".
Why it is wrong: Each call copies the whole collection and allocates a new array.
Instead: Materialise once, at the boundary where you need it.
Mistake: Modifying a list inside foreach.
Why it is wrong: The enumerator checks the version number and throws InvalidOperationException.
Instead: Iterate backwards with for when removing, use RemoveAll(predicate), or collect changes and apply them after.
Mistake: Keeping a span from CollectionsMarshal.AsSpan while adding to the list.
Why it is wrong: A resize copies the data to a new array, so the span silently reads stale data.
Instead: Take the span only for a loop that does not change the list's size.
Mistake: Assuming an array of objects is cache-friendly. Why it is wrong: It holds references, and the objects can be scattered across the heap. Instead: For hot numeric data, use arrays of structs or separate primitive arrays.
Arrays are the foundation for almost every other collection: List<T>, Queue<T>, Stack<T>, Dictionary<TKey, TValue> (buckets and entries), PriorityQueue<TElement, TPriority> and HashSet<T> are all arrays underneath. Contiguous memory, amortised growth and cache locality explain why these structures usually beat pointer-based ones such as linked lists in practice, even when big-O says they are equal.
| Lever | Typical win | Cost |
|---|---|---|
| Pre-size lists | Fewer copies, no LOH growth chain | Needs an estimate |
| Slice with spans | No copies when parsing or windowing | ref struct rules (no fields, no await) |
ArrayPool<T> for big buffers |
Far less GC pressure | Must return buffers, track used length |
| Arrays of structs for hot data | Cache-friendly loops | Copy semantics, careful with large structs |
| Frozen or immutable collections for read-mostly data | Faster lookups, safe sharing | Slower to build |
In production code the main levers are allocation and copying: pre-size lists, avoid repeated ToList(), slice with spans instead of copying, and pool large temporary buffers. These rarely show up in big-O analysis but often dominate GC time and memory in real services, so I measure with BenchmarkDotNet and dotnet-counters before and after.
A linked list stores each element in a node that points to the next node (singly linked) or to both neighbours (doubly linked). Nodes are separate heap objects, not contiguous.
.NET's LinkedList<T> is a doubly linked, circular list of LinkedListNode<T> objects. In practice List<T> is faster for most workloads because arrays are cache-friendly and allocate less; linked list nodes are scattered and each costs an object allocation.
Use a linked list when you need frequent O(1) removal or move of known nodes, such as an LRU cache (Dictionary of key → node + linked list for recency order).
CPUs load memory in cache lines of 64 bytes, so after one access the neighbouring bytes are already in cache (spatial locality), and recently used data is likely still there (temporal locality). Hardware prefetchers also spot sequential access and fetch ahead. A C# int[,] is stored row-major: one row's elements are next to each other. Walking row by row uses every byte of each line and the prefetcher keeps up; walking column by column jumps a whole row each step, wasting most of each line and missing cache, often 5–10× slower for large arrays. The same logic favours arrays of structs over lists of objects scattered on the heap, and struct-of-arrays layouts for hot numeric fields.
Each thread allocates from its own allocation context, a small chunk of gen 0 where new is just a pointer bump plus zeroing; when it runs out, the thread asks the GC for another chunk, and when the gen 0 budget is used up, a gen 0 GC runs. The GC is generational because most objects die young: gen 0 collections are cheap, survivors are promoted to gen 1 and then gen 2, which is collected rarely (and mostly in the background). Objects of 85,000 bytes or more go to the large object heap (LOH), which is collected only with gen 2 and isn't compacted by default, so it can fragment. Pinned objects can't be moved, which blocks compaction; the pinned object heap (.NET 5+) keeps long-lived pinned buffers separate. In hot paths I reduce the allocation rate rather than tuning the GC.
Last updated 23 Oct 2026.