The dynamic array from the inside

Code in:JavaC#PythonJavaScript

In short: A dynamic array (List<T> in C#) is an array with more slots than elements: reading by index is O(1), appending is O(1) on average, and inserting at the front is O(n).

Problem

The cart that slows down

The online shop shows the cart with the last added product at the top. The code does it simply: every new line goes in at index 0.

string[] orderLines = { "Flour 25 kg", "Sugar 10 kg", "Oil 5 l", "Rice 10 kg" };
var cart = new List<string>();
foreach (string line in orderLines)
{
    cart.Insert(0, line);
}
Console.WriteLine("The cart: " + string.Join(", ", cart));

Output

The cart: Rice 10 kg, Oil 5 l, Sugar 10 kg, Flour 25 kg

For an ordinary customer with 5 products you do not notice it. Then a wholesale customer comes and uploads an order from a file: 50,000 lines. The page freezes for seconds.

The reason: every insert at index 0 moves all the products already added by one place. 50,000 lines make 1 + 2 + … + 49,999 = 1,249,975,000 moves.

The idea

An array that looks after itself

List<T> is a dynamic array inside: an ordinary array with more places than there are elements, and a counter of how many of them are used.

• The capacity is how many places the array has.
• The size is how many of them are used, from 0 to the size minus one.

When the places run out, it makes a new array, twice as big, and copies everything. Why that is O(1) on average is in the lesson "Amortized complexity". Here we look at what happens inside the array: on read, on insert and on remove by index.

The places of the array sit next to each other in memory and are equally big. If the array starts at address 1000 and every place is 8 bytes, place i is at address 1000 + i × 8. So reading by index is one multiplication and one addition: O(1), however many elements there are.

See it

Your own dynamic array

Here is the same thing, written by hand. The array starts with 8 places:

class DynamicArray
{
    private string[] items = new string[8];
    private int size = 0;

    public int Count => size;

    public int Capacity => items.Length;

    public string this[int index]
    {
        get
        {
            CheckIndex(index, size);
            return items[index];
        }
        set
        {
            CheckIndex(index, size);
            items[index] = value;
        }
    }

    public void Add(string value)
    {
        Insert(size, value);
    }

    public void Insert(int index, string value)
    {
        CheckIndex(index, size + 1);
        if (size == items.Length)
        {
            Grow();
        }
        for (int i = size; i > index; i--)
        {
            items[i] = items[i - 1];
        }
        items[index] = value;
        size++;
    }

    public string RemoveAt(int index)
    {
        CheckIndex(index, size);
        string removed = items[index];
        for (int i = index; i < size - 1; i++)
        {
            items[i] = items[i + 1];
        }
        size--;
        items[size] = null;
        return removed;
    }

    private void Grow()
    {
        string[] bigger = new string[items.Length * 2];
        for (int i = 0; i < size; i++)
        {
            bigger[i] = items[i];
        }
        items = bigger;
    }

    private void CheckIndex(int index, int limit)
    {
        if (index < 0 || index >= limit)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
    }
}

Watch what happens to the places on read, insert and remove:

public void Insert(int index, string value)
{
    CheckIndex(index, size + 1);
    if (size == items.Length)
    {
        Grow();
    }
    for (int i = size; i > index; i--)
    {
        items[i] = items[i - 1];
    }
    items[index] = value;
    size++;
}

public string RemoveAt(int index)
{
    CheckIndex(index, size);
    string removed = items[index];
    for (int i = index; i < size - 1; i++)
    {
        items[i] = items[i + 1];
    }
    size--;
    items[size] = null;
    return removed;
}

Step by step, in words

1. The cart is one block of 8 places next to each other in memory. 5 are used: that is the size. All 8 are the capacity.
2. cart[3]: the address is start + 3 × 8 = 1024. One jump, without passing the others: O(1), whatever the size.
3. Insert(0, …): place 0 is taken. Every product moves one place right, from the back, so nothing is overwritten: 5 moves.
4. Only now does "Cheese" go into place 0, and the size becomes 6.
5. RemoveAt(2) takes out "Milk". The 3 after it move one place left to close the gap: 3 moves.
6. The size drops to 5, and the last place gets null: the old reference would keep the product alive in memory.
7. cart[5]: place 5 exists (the capacity is 8), but it is not in the cart. The check compares with the size and throws ArgumentOutOfRangeException.
8. Reading by index is one jump. Insert and remove move everything after the index: at the front that is all n, O(n). At the end nothing moves.

var cart = new DynamicArray();
cart.Add("Bread");
cart.Add("Milk");
cart.Add("Coffee");
cart.Add("Butter");
cart.Add("Apples");
Console.WriteLine(cart[3]);
cart.Insert(0, "Cheese");
cart.RemoveAt(2);
for (int i = 0; i < cart.Count; i++)
{
    Console.WriteLine(i + ": " + cart[i]);
}
Console.WriteLine("Places: " + cart.Capacity);
try
{
    Console.WriteLine(cart[5]);
}
catch (ArgumentOutOfRangeException e)
{
    Console.WriteLine("Error: " + e.Message);
}

Output

Butter
0: Cheese
1: Bread
2: Coffee
3: Butter
4: Apples
Places: 8
Error: Specified argument was out of the range of valid values. (Parameter 'index')

this[int index] is an indexer: thanks to it you write cart[3] as with an array. List<T> is made the same way.

Try it

Predict the output

An array with 8 places holds 8 products. You insert one more at the front:

class DynamicArray
{
    private string[] items = new string[8];
    private int size = 0;

    public int Count => size;

    public int Capacity => items.Length;

    public string this[int index]
    {
        get
        {
            CheckIndex(index, size);
            return items[index];
        }
        set
        {
            CheckIndex(index, size);
            items[index] = value;
        }
    }

    public void Add(string value)
    {
        Insert(size, value);
    }

    public void Insert(int index, string value)
    {
        CheckIndex(index, size + 1);
        if (size == items.Length)
        {
            Grow();
        }
        for (int i = size; i > index; i--)
        {
            items[i] = items[i - 1];
        }
        items[index] = value;
        size++;
    }

    public string RemoveAt(int index)
    {
        CheckIndex(index, size);
        string removed = items[index];
        for (int i = index; i < size - 1; i++)
        {
            items[i] = items[i + 1];
        }
        size--;
        items[size] = null;
        return removed;
    }

    private void Grow()
    {
        string[] bigger = new string[items.Length * 2];
        for (int i = 0; i < size; i++)
        {
            bigger[i] = items[i];
        }
        items = bigger;
    }

    private void CheckIndex(int index, int limit)
    {
        if (index < 0 || index >= limit)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
    }
}

var cart = new DynamicArray();
for (int i = 1; i <= 8; i++)
{
    cart.Add("P" + i);
}
cart.Insert(0, "P0");
Console.WriteLine("Products: " + cart.Count);
Console.WriteLine("Places: " + cart.Capacity);
Console.WriteLine(cart[8]);

Answer

Products: 9
Places: 16
P8

Products: 9
Places: 9
P8

Products: 9
Places: 16
P0

Check

The idea

Insert and remove cost O(n)

An insert at index i moves everything from i to the end one place right, from the back, so that nothing is overwritten. A remove moves everything after i one place left. The closer to the start, the more:

• At the end: nothing moves. O(1), and with the growth O(1) amortized.
• At the front: everything moves. O(n).
• In the middle: half on average. Still O(n).

So n inserts at the front are O(n²), and n adds at the end O(n). The fix for the cart is to add at the end and show it from the back. Walking from the back is the same O(n):

string[] orderLines = { "Flour 25 kg", "Sugar 10 kg", "Oil 5 l", "Rice 10 kg" };
var cart = new List<string>();
foreach (string line in orderLines)
{
    cart.Add(line);
}
var newestFirst = Enumerable.Reverse(cart);
Console.WriteLine("The cart: " + string.Join(", ", newestFirst));

Output

The cart: Rice 10 kg, Oil 5 l, Sugar 10 kg, Flour 25 kg

See it

Measure it: at the end against at the front

Run both ways on the same products. We count the writes of elements in the array: the new one, every move and every copy on growth. Inserting at the front at 100,000 is not really run: Bench estimates it from the curve.

• Append at the end O(n)
• Insert at the front O(n²)

Algorithm	n = 10	n = 1,000	n = 10,000	n = 100,000
Append at the end	18	2,016	26,376	231,064
Insert at the front	63	501,516	50,021,376	≈ 5,002,137,600

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

class DynamicArray
{
    private string[] items = new string[8];
    private int size = 0;

    public int Count => size;

    public int Capacity => items.Length;

    public string this[int index]
    {
        get
        {
            CheckIndex(index, size);
            return items[index];
        }
        set
        {
            CheckIndex(index, size);
            items[index] = value;
        }
    }

    public void Add(string value)
    {
        Insert(size, value);
    }

    public void Insert(int index, string value)
    {
        CheckIndex(index, size + 1);
        if (size == items.Length)
        {
            Grow();
        }
        for (int i = size; i > index; i--)
        {
            items[i] = items[i - 1];
        }
        items[index] = value;
        size++;
    }

    public string RemoveAt(int index)
    {
        CheckIndex(index, size);
        string removed = items[index];
        for (int i = index; i < size - 1; i++)
        {
            items[i] = items[i + 1];
        }
        size--;
        items[size] = null;
        return removed;
    }

    private void Grow()
    {
        string[] bigger = new string[items.Length * 2];
        for (int i = 0; i < size; i++)
        {
            bigger[i] = items[i];
        }
        items = bigger;
    }

    private void CheckIndex(int index, int limit)
    {
        if (index < 0 || index >= limit)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
    }
}

With 1000 products adding at the end makes 2,016 writes: 1000 new ones and the copies on growth. Inserting at the front makes 501,516. At 10,000 the difference is 26,376 against 50,021,376.

More precisely, if you are curious

The same numbers in your language, with a counter of the writes in the class:

class DynamicArray
{
    private string[] items = new string[8];
    private int size = 0;
    public long Writes { get; private set; }

    public int Count => size;

    public int Capacity => items.Length;

    public string this[int index]
    {
        get
        {
            CheckIndex(index, size);
            return items[index];
        }
        set
        {
            CheckIndex(index, size);
            items[index] = value;
        }
    }

    public void Add(string value)
    {
        Insert(size, value);
    }

    public void Insert(int index, string value)
    {
        CheckIndex(index, size + 1);
        if (size == items.Length)
        {
            Grow();
        }
        for (int i = size; i > index; i--)
        {
            items[i] = items[i - 1];
            Writes++;
        }
        items[index] = value;
        Writes++;
        size++;
    }

    public string RemoveAt(int index)
    {
        CheckIndex(index, size);
        string removed = items[index];
        for (int i = index; i < size - 1; i++)
        {
            items[i] = items[i + 1];
        }
        size--;
        items[size] = null;
        return removed;
    }

    private void Grow()
    {
        string[] bigger = new string[items.Length * 2];
        for (int i = 0; i < size; i++)
        {
            bigger[i] = items[i];
            Writes++;
        }
        items = bigger;
    }

    private void CheckIndex(int index, int limit)
    {
        if (index < 0 || index >= limit)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
    }
}

foreach (int n in new[] { 10, 1000, 100000 })
{
    var cart = new DynamicArray();
    for (int i = 0; i < n; i++)
    {
        cart.Add((1001 + i).ToString());
    }
    Console.WriteLine($"at the end, n = {n}: {cart.Writes} writes");
}
foreach (int n in new[] { 10, 1000 })
{
    var cart = new DynamicArray();
    for (int i = 0; i < n; i++)
    {
        cart.Insert(0, (1001 + i).ToString());
    }
    Console.WriteLine($"at the front, n = {n}: {cart.Writes} writes");
}

Output

at the end, n = 10: 18 writes
at the end, n = 1000: 2016 writes
at the end, n = 100000: 231064 writes
at the front, n = 10: 63 writes
at the front, n = 1000: 501516 writes

Try it

Find the bug

A colleague has rewritten Insert. Three products, then one more at the front, and the cart comes out like this:

var cart = new DynamicArray();
cart.Add("Bread");
cart.Add("Milk");
cart.Add("Coffee");
cart.Insert(0, "Cheese");
for (int i = 0; i < cart.Count; i++)
{
    Console.WriteLine(i + ": " + cart[i]);
}

Output

0: Cheese
1: Bread
2: Bread
3: Bread

Which line is the bug on?

Pick the line with the bug.

1class DynamicArray2{3 private string[] items = new string[8];4 private int size = 0;56 public int Count => size;78 public int Capacity => items.Length;910 public string this[int index]11 {12 get13 {14 CheckIndex(index, size);15 return items[index];16 }17 set18 {19 CheckIndex(index, size);20 items[index] = value;21 }22 }2324 public void Add(string value)25 {26 Insert(size, value);27 }2829 public void Insert(int index, string value)30 {31 CheckIndex(index, size + 1);32 if (size == items.Length)33 {34 Grow();35 }36 for (int i = index; i < size; i++)37 {38 items[i + 1] = items[i];39 }40 items[index] = value;41 size++;42 }4344 public string RemoveAt(int index)45 {46 CheckIndex(index, size);47 string removed = items[index];48 for (int i = index; i < size - 1; i++)49 {50 items[i] = items[i + 1];51 }52 size--;53 items[size] = null;54 return removed;55 }5657 private void Grow()58 {59 string[] bigger = new string[items.Length * 2];60 for (int i = 0; i < size; i++)61 {62 bigger[i] = items[i];63 }64 items = bigger;65 }6667 private void CheckIndex(int index, int limit)68 {69 if (index < 0 || index >= limit)70 {71 throw new ArgumentOutOfRangeException(nameof(index));72 }73 }74}

Check

Try it

Fill in

RemoveAt closes the gap by moving every element after it one place left. Where does the element of place i come from?

public string RemoveAt(int index)
{
    CheckIndex(index, size);
    string removed = items[index];
    for (int i = index; i < size - 1; i++)
    {
        items[i] = items[];
    }
    size--;
    items[size] = null;
    return removed;
}

Check

The idea

To shrink or not

The cart had 10,000 products, then the customer removed almost all of them. The array still holds 16,384 places. Should it shrink?

If it shrinks by half as soon as the size falls under half, there is a trap. An array with 16 places and 9 elements: a remove, and it becomes 8 places, full. An add, and it is 16 places again. Do the two in turn right at that limit, and every operation copies everything: O(n).

So shrinking waits longer: by half, when it is a quarter full. After shrinking the array is half full, and there are at least n/4 operations until the next copy. The cost stays O(1) amortized.

The built-in lists decide differently:

• Java ArrayList does not shrink by itself, it has trimToSize();
• C# List<T> does not shrink by itself. Capacity stays until you call TrimExcess().
• Python (CPython) shrinks by itself under half;
• JavaScript (V8) sometimes shrinks, by its own rules.

Shrinking saves memory but costs a copy. If the array will soon grow again, it is cheaper not to shrink.

The idea

Why the array is fast in practice too: the cache

The processor does not read memory one byte at a time. It takes a whole line of 64 bytes and keeps it in the cache, a small and very fast memory next to it. Reading from the cache is tens of times faster than reading from main memory.

The array is one block. When you read place 0, its neighbours come in the same line, and the next reads are from the cache. The processor also notices that you read in order and fetches the next lines in advance. So walking an array is fast not only on paper but on the clock too.

What sits in the places matters: - int[] and List<int> hold the numbers themselves next to each other. string[] and List<string> hold references next to each other, and the objects themselves are elsewhere in memory. Walking the references is fast, but every read of an object can be a jump.

The next lesson, "Linked list", is the opposite: every element is a separate object somewhere in memory. There an insert at the front is O(1), but the cache does not help.

Exercise

An array that shrinks

Solve it in your editor.

Shrinking at a quarter. Replace the growth of the class with a method Resize(int places) that makes an array with that many places and copies the elements. Insert calls it with twice as many places when the array is full. RemoveAt calls it with half when the size becomes a quarter of the places, but never under 8 places.

Add 20 products and print the size and the places. Then remove from the end until 2 are left, and print the size and the places at every change of the places:

Output

20 / 32
8 / 16
4 / 8

More tasks

• indexOf and remove. Add IndexOf(string value), which returns the index or -1, and Remove(string value), which removes the first occurrence. What does each cost?
• Removing from the start without moving. A queue of orders always removes the first one. Keep an index head of the first used place instead of moving all of them. What happens when head reaches the end of the array? (Hint: continue from the start.)
• Fill it in pieces. Import 50,000 lines at once: collect them at the end and reverse the array once. How many writes is that?

Test

Check yourself

1. A dynamic array has 1000 elements. How many elements does an insert at index 0 move? And at index 990?

1 and 11000 and 101000 and 1000

2. Why is reading by index O(1) even with a million elements?

Because the array is sortedThe array keeps where every element is in a separate tableThe address is computed: start + index × the size of one place

3. The array has capacity 8 and size 5. What happens on get(6)?

The array grows to 16An index out of bounds error, even though place 6 existsIt returns an empty place

4. Why does the array shrink by half only when it is a quarter full, and not when it is half full?

Because memory is only freed in quartersBecause shrinking is slowWith the limit at "half", adding and removing in turn right there shrinks and grows every time, and each one copies everything

5. The cart has to show the last added product at the top. What is the fast solution?

Insert at index 0Add at the end and show it from the backSort after every add

Check

Start the lesson over

Related lessons

• Builds on: Big-O: how the work grows · Best, average and worst case · Space complexity · Amortized complexity
• Continues in: Linked list · Stack and queue · Hash table
• Tasks on this topic: Data structures