Arrays, Lists & Memory Layout
8 min readArrays, Lists & Memory Layout
TL;DR
Arrays are the structure everything else is built on, and their advantage is not an operation count ā it is physical contiguity. A CPU reads memory in cache lines of 64 bytes and aggressively prefetches sequential addresses, so a linear array walk is nearly free per element while a pointer chase stalls on cache misses that cost roughly a hundred cycles each. Understanding that gap is what separates "I know List<T> is O(1) indexed" from being able to explain why the asymptotically-worse structure keeps winning benchmarks.
How it works
What List<T> actually is
A List<T> is an array plus a count. Adding writes to the next slot; when the array is full it allocates a new array of double the capacity, copies everything, and abandons the old one.
// Three separate costs hide in this loop:
// 1. log2(n) reallocations, each copying everything so far
// 2. the garbage left by every abandoned array
// 3. arrays over 85,000 bytes land on the Large Object Heap
var items = new List<Order>();
for (int i = 0; i < 100_000; i++) items.Add(orders[i]);
// One allocation, no copies, no garbage:
var sized = new List<Order>(capacity: 100_000);Pre-sizing is the cheapest performance win in .NET and the one most often left on the table. The same applies to Dictionary, HashSet, StringBuilder, and MemoryStream.
Cache lines and why locality dominates
| Access | Approximate cost |
|---|---|
| L1 cache hit | ~1 ns |
| L2 / L3 hit | ~4ā20 ns |
| Main memory | ~100 ns |
A cache miss costs about a hundred times a hit. When you read array[0], the CPU pulls a whole 64-byte line, so the next 15 ints are already resident ā and the prefetcher, detecting a sequential pattern, fetches ahead of you. A linked list defeats both: each node is a separate heap allocation at an unpredictable address, so every step is a dependent load that may miss, and the prefetcher cannot guess where you are going.
This is the real reason LinkedList<T> is rare in .NET code. Its O(1) insertion assumes you already hold the node ā and finding the node is the O(n) traversal that pays full cache-miss price on every step.
References versus values
class OrderClass { public int Id; public decimal Total; }
struct OrderStruct { public int Id; public decimal Total; }
OrderClass[] a = ...; // contiguous REFERENCES -> objects scattered on the heap
OrderStruct[] b = ...; // contiguous DATA -> one sequential streaming readIterating b and summing Total is a sequential scan. Iterating a reads a pointer, then jumps somewhere else in the heap to read the field ā an indirection per element, plus per-object header overhead, plus GC tracking for every one of them. On large collections this is routinely an order of magnitude.
The caveats are real: large structs are expensive to copy, a struct fetched from a collection is a copy so mutating it does nothing to the original unless you take it by ref, and structs cannot participate in inheritance.
Span, Memory, and slicing without copying
Span<T> is a view over contiguous memory ā an array, a stack buffer, or unmanaged memory ā that lets you slice and pass sub-ranges with zero allocation:
// Allocates a new string per call.
string field = line.Substring(start, length);
// Allocates nothing -- a window over the existing characters.
ReadOnlySpan<char> field = line.AsSpan(start, length);Span<T> is a ref struct, so it lives only on the stack: it cannot be a field of a class, cannot be captured by a lambda, and cannot cross an await. Memory<T> is the heap-friendly counterpart for async paths, converted to a span at the point of use.
The Large Object Heap
Allocations of 85,000 bytes or more (about 10,600 longs, or an array of ~21,000 ints) go on the Large Object Heap, which is collected only with gen-2 collections and is not compacted by default. Repeatedly growing large arrays therefore fragments the LOH, and a process can fail an allocation while reporting plenty of free memory. Pre-sizing, ArrayPool<T>.Shared for reusable buffers, and chunking large collections all avoid it.
A: Because growth is not free: when the backing array fills, the collection allocates a new array of double the size, copies every existing element, and abandons the old one. Building a list of a million items without a capacity therefore performs about twenty reallocations, copies roughly two million elements in total, and leaves every intermediate array as garbage ā and once an array exceeds 85,000 bytes those allocations land on the Large Object Heap, which is not compacted by default. Passing the expected count to the constructor turns all of that into a single allocation. It is the cheapest optimisation available and costs one argument.
A: Because Big-O counts operations while the hardware charges for memory access, and those differ by two orders of magnitude ā an L1 hit is roughly a nanosecond while a main-memory read is around a hundred. The CPU fetches a whole 64-byte cache line at a time and prefetches ahead when it detects sequential access, so a contiguous array walk amortises one memory fetch over many elements. A structure that scatters its elements across the heap gets neither benefit and pays close to full latency on every step, which is how an algorithm with fewer operations ends up slower in wall-clock terms.
A: Almost never, and the honest interview answer says so with the reasoning. Its O(1) insert and remove assume you already hold the node reference, and obtaining one requires an O(n) traversal that pays a likely cache miss at every step, plus a heap allocation and GC tracking per node. It becomes defensible when you hold node references directly and splice frequently ā an LRU cache pairing a dictionary of keys to nodes with a list for recency ordering is the canonical example ā or when you must guarantee no bulk copy ever occurs. For everything else List<T> wins on locality even where the asymptotics say it should not.
A: An array of structs stores the field data inline, so the array is one contiguous block and iterating it is a single sequential read that the prefetcher streams. An array of classes stores references, so the array is contiguous but the objects it points to are separately allocated and may be anywhere on the heap; every element access is an indirection, each object carries header overhead, and the GC must track every one. For large collections that you iterate, the struct layout is regularly an order of magnitude faster. The costs are that structs are copied by value, so large ones are expensive to pass around and mutating one retrieved from a collection modifies a copy unless taken by ref.
A: It gives you a view over a contiguous region of memory ā an array, a stack buffer, or unmanaged memory ā so you can slice and pass sub-ranges without allocating. That eliminates the classic parsing pattern where every Substring allocates a new string, replacing it with windows over the original buffer and often taking allocations in a hot path to zero. The restriction is that Span<T> is a ref struct that must live on the stack: it cannot be a field of a class, boxed, captured in a lambda or iterator, or held across an await. Memory<T> is the heap-friendly equivalent for async code, converted to a span where the work happens.
A: It is a separate .NET heap for allocations of 85,000 bytes or more ā arrays of about 21,000 ints or larger. It matters because it is only collected during expensive gen-2 collections and is not compacted by default, so repeatedly allocating and discarding large arrays fragments it, and eventually an allocation can fail with plenty of total memory free. It also makes each large allocation disproportionately expensive. The mitigations are pre-sizing so you allocate once, renting reusable buffers from ArrayPool<T>.Shared instead of allocating fresh, and chunking data so no single array crosses the threshold.
A: Inserting at the end is O(1) amortised ā a write to the next free slot, with an occasional doubling resize. Inserting at the beginning is O(n), because every existing element must shift one position to make room, so building a list of n items by repeatedly inserting at index zero is O(nĀ²). If you need cheap insertion at both ends, Queue<T> is a circular buffer offering O(1) at both, or you can build in the natural order and reverse once at O(n). The subtlety is that the O(n) shift is a memmove of contiguous memory, which is fast enough per element that lists still beat linked lists at surprisingly large sizes.
Key takeaways
List<T>is an array plus a count; growth means allocate-double, copy everything, discard the old array.- Pre-size everything you can size ā
List,Dictionary,HashSet,StringBuilder. Cheapest win available. - A cache miss is ~100Ć a hit, so contiguity often beats a better complexity class at realistic n.
- Array of classes = contiguous references to scattered objects; array of structs = contiguous data.
Span<T>slices without allocating but is stack-only ā no fields, no lambdas, no crossingawait.- ā„85,000 bytes goes to the LOH: rarely collected, not compacted, fragments under repeated large allocation.