Arrays in memory

The array is the most important data structure of all. Almost every other structure (lists, stacks, queues, hash tables, heaps) is built on top of one. To use them well you need to know what an array really is in memory.

One unbroken block

An array is a single contiguous block of memory: element 0, then element 1 directly after it, then element 2, with no gaps. Every element has the same size, so the computer can work out where any element lives with one small calculation:

1address of a[i] = start address + i × element size2 3int[] a (4 bytes per int), starting at 0x1000:4a[0] → 0x1000    a[1] → 0x1004    a[2] → 0x1008    a[3] → 0x100C

One multiplication and one addition, whether the index is 3 or 3 million. That is why reading or writing a[i] is O(1). It is called random access: you can jump to any position directly.

The price: inserting and deleting

Because there are no gaps, putting a value between two elements means moving every element after it one slot to the right. Removing one means moving them all left to close the hole. The cost depends on the position: free at the end, n moves at the front.

1// The array has spare room; count = how many slots are in use2static void InsertAt(int[] a, ref int count, int index, int value)3{4    if (count == a.Length) throw new InvalidOperationException("Array is full");5 6    for (int i = count; i > index; i--)   // shift right, starting from the end7        a[i] = a[i - 1];8 9    a[index] = value;10    count++;11}12 13int[] data = new int[8] { 10, 20, 30, 40, 0, 0, 0, 0 };14int count = 4;15InsertAt(data, ref count, 1, 15);16Console.WriteLine(string.Join(", ", data[..count]));

10, 15, 20, 30, 40

What a C# array looks like in memory

In .NET an array is an object on the heap. It starts with a small header (about 24 bytes on 64-bit: type information, a sync block and the length), followed by the elements. So new int[1000] takes about 24 + 4,000 bytes. The length is stored in the header, which is why a.Length is O(1) and why .NET can check every index and throw IndexOutOfRangeException instead of reading random memory.

What the elements contain depends on the type:

• Value types (int, double, structs like a Point3D): the values themselves sit side by side in the block.
• Reference types (classes, string): the block holds 8-byte references, and the objects live somewhere else on the heap. Walking the array means jumping to a different memory location for every element.

The CPU cache: why arrays are faster than Big-O says

Reading from main memory is slow (around 100 ns). The CPU therefore loads memory in cache lines of 64 bytes and keeps them in a small, very fast cache. When you read a[0] of an int[], a[1] to a[15] arrive in the same trip for free. Code that walks memory in order uses every byte it fetches; code that jumps around wastes most of each trip.

1const int N = 4000;2var grid = new double[N, N];   // C# stores rows one after another (row-major)3 4double sum = 0;5 6// Fast: the inner loop walks along a row, through memory in order7for (int r = 0; r < N; r++)8    for (int c = 0; c < N; c++)9        sum += grid[r, c];10 11// Same Big-O, often several times slower: the inner loop jumps a whole row (32 KB) each step12for (int c = 0; c < N; c++)13    for (int r = 0; r < N; r++)14        sum += grid[r, c];

1static void InsertSorted(int[] a, ref int count, int value)2{3    if (count == a.Length) throw new InvalidOperationException("Array is full");4 5    int i = count - 1;6    while (i >= 0 && a[i] > value)7    {8        a[i + 1] = a[i];   // make room9        i--;10    }11    a[i + 1] = value;12    count++;13}14 15int[] a = new int[8] { 3, 8, 15, 42, 0, 0, 0, 0 };16int n = 4;17InsertSorted(a, ref n, 10);18InsertSorted(a, ref n, 1);19Console.WriteLine(string.Join(", ", a[..n]));

1, 3, 8, 10, 15, 42