The dynamic array from the inside

Code in:JavaC#PythonJavaScript

In short: A dynamic array (list in Python) 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.

order_lines = ["Flour 25 kg", "Sugar 10 kg", "Oil 5 l", "Rice 10 kg"]
cart = []
for line in order_lines:
    cart.insert(0, line)
print("The cart: " + ", ".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 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:
    def __init__(self):
        self.items = [None] * 8
        self.size = 0

    def __len__(self):
        return self.size

    @property
    def capacity(self):
        return len(self.items)

    def __getitem__(self, index):
        self._check(index, self.size)
        return self.items[index]

    def __setitem__(self, index, value):
        self._check(index, self.size)
        self.items[index] = value

    def append(self, value):
        self.insert(self.size, value)

    def insert(self, index, value):
        self._check(index, self.size + 1)
        if self.size == len(self.items):
            self._grow()
        for i in range(self.size, index, -1):
            self.items[i] = self.items[i - 1]
        self.items[index] = value
        self.size += 1

    def remove_at(self, index):
        self._check(index, self.size)
        removed = self.items[index]
        for i in range(index, self.size - 1):
            self.items[i] = self.items[i + 1]
        self.size -= 1
        self.items[self.size] = None
        return removed

    def _grow(self):
        bigger = [None] * (len(self.items) * 2)
        for i in range(self.size):
            bigger[i] = self.items[i]
        self.items = bigger

    def _check(self, index, limit):
        if index < 0 or index >= limit:
            raise IndexError(f"index {index}, size {self.size}")

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

def insert(self, index, value):
    self._check(index, self.size + 1)
    if self.size == len(self.items):
        self._grow()
    for i in range(self.size, index, -1):
        self.items[i] = self.items[i - 1]
    self.items[index] = value
    self.size += 1

def remove_at(self, index):
    self._check(index, self.size)
    removed = self.items[index]
    for i in range(index, self.size - 1):
        self.items[i] = self.items[i + 1]
    self.size -= 1
    self.items[self.size] = None
    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. remove_at(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 None: 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 IndexError.
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.

cart = DynamicArray()
cart.append("Bread")
cart.append("Milk")
cart.append("Coffee")
cart.append("Butter")
cart.append("Apples")
print(cart[3])
cart.insert(0, "Cheese")
cart.remove_at(2)
for i in range(len(cart)):
    print(f"{i}: {cart[i]}")
print("Places: " + str(cart.capacity))
try:
    cart[5]
except IndexError as e:
    print("Error: " + str(e))

Output

Butter
0: Cheese
1: Bread
2: Coffee
3: Butter
4: Apples
Places: 8
Error: index 5, size 5

__getitem__, __setitem__ and __len__ are the special methods thanks to which you write cart[3] and len(cart) as with the built-in list.

Try it

Predict the output

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

class DynamicArray:
    def __init__(self):
        self.items = [None] * 8
        self.size = 0

    def __len__(self):
        return self.size

    @property
    def capacity(self):
        return len(self.items)

    def __getitem__(self, index):
        self._check(index, self.size)
        return self.items[index]

    def __setitem__(self, index, value):
        self._check(index, self.size)
        self.items[index] = value

    def append(self, value):
        self.insert(self.size, value)

    def insert(self, index, value):
        self._check(index, self.size + 1)
        if self.size == len(self.items):
            self._grow()
        for i in range(self.size, index, -1):
            self.items[i] = self.items[i - 1]
        self.items[index] = value
        self.size += 1

    def remove_at(self, index):
        self._check(index, self.size)
        removed = self.items[index]
        for i in range(index, self.size - 1):
            self.items[i] = self.items[i + 1]
        self.size -= 1
        self.items[self.size] = None
        return removed

    def _grow(self):
        bigger = [None] * (len(self.items) * 2)
        for i in range(self.size):
            bigger[i] = self.items[i]
        self.items = bigger

    def _check(self, index, limit):
        if index < 0 or index >= limit:
            raise IndexError(f"index {index}, size {self.size}")


cart = DynamicArray()
for i in range(8):
    cart.append(f"P{i + 1}")
cart.insert(0, "P0")
print("Products: " + str(len(cart)))
print("Places: " + str(cart.capacity))
print(str(cart[8]))

Answer

Products: 9
Places: 16
P8

Products: 9
Places: 16
P0

Products: 9
Places: 9
P8

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):

order_lines = ["Flour 25 kg", "Sugar 10 kg", "Oil 5 l", "Rice 10 kg"]
cart = []
for line in order_lines:
    cart.append(line)
newest_first = reversed(cart)
print("The cart: " + ", ".join(newest_first))

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:
    def __init__(self):
        self.items = [None] * 8
        self.size = 0

    def __len__(self):
        return self.size

    @property
    def capacity(self):
        return len(self.items)

    def __getitem__(self, index):
        self._check(index, self.size)
        return self.items[index]

    def __setitem__(self, index, value):
        self._check(index, self.size)
        self.items[index] = value

    def append(self, value):
        self.insert(self.size, value)

    def insert(self, index, value):
        self._check(index, self.size + 1)
        if self.size == len(self.items):
            self._grow()
        for i in range(self.size, index, -1):
            self.items[i] = self.items[i - 1]
        self.items[index] = value
        self.size += 1

    def remove_at(self, index):
        self._check(index, self.size)
        removed = self.items[index]
        for i in range(index, self.size - 1):
            self.items[i] = self.items[i + 1]
        self.size -= 1
        self.items[self.size] = None
        return removed

    def _grow(self):
        bigger = [None] * (len(self.items) * 2)
        for i in range(self.size):
            bigger[i] = self.items[i]
        self.items = bigger

    def _check(self, index, limit):
        if index < 0 or index >= limit:
            raise IndexError(f"index {index}, size {self.size}")

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:
    def __init__(self):
        self.items = [None] * 8
        self.size = 0
        self.writes = 0

    def __len__(self):
        return self.size

    @property
    def capacity(self):
        return len(self.items)

    def __getitem__(self, index):
        self._check(index, self.size)
        return self.items[index]

    def __setitem__(self, index, value):
        self._check(index, self.size)
        self.items[index] = value

    def append(self, value):
        self.insert(self.size, value)

    def insert(self, index, value):
        self._check(index, self.size + 1)
        if self.size == len(self.items):
            self._grow()
        for i in range(self.size, index, -1):
            self.items[i] = self.items[i - 1]
            self.writes += 1
        self.items[index] = value
        self.writes += 1
        self.size += 1

    def remove_at(self, index):
        self._check(index, self.size)
        removed = self.items[index]
        for i in range(index, self.size - 1):
            self.items[i] = self.items[i + 1]
        self.size -= 1
        self.items[self.size] = None
        return removed

    def _grow(self):
        bigger = [None] * (len(self.items) * 2)
        for i in range(self.size):
            bigger[i] = self.items[i]
            self.writes += 1
        self.items = bigger

    def _check(self, index, limit):
        if index < 0 or index >= limit:
            raise IndexError(f"index {index}, size {self.size}")


for n in [10, 1000, 100000]:
    cart = DynamicArray()
    for i in range(n):
        cart.append(str(1001 + i))
    print(f"at the end, n = {n}: {cart.writes} writes")
for n in [10, 1000]:
    cart = DynamicArray()
    for i in range(n):
        cart.insert(0, str(1001 + i))
    print(f"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:

cart = DynamicArray()
cart.append("Bread")
cart.append("Milk")
cart.append("Coffee")
cart.insert(0, "Cheese")
for i in range(len(cart)):
    print(f"{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 DynamicArray:2 def __init__(self):3 self.items = [None] * 84 self.size = 056 def __len__(self):7 return self.size89 @property10 def capacity(self):11 return len(self.items)1213 def __getitem__(self, index):14 self._check(index, self.size)15 return self.items[index]1617 def __setitem__(self, index, value):18 self._check(index, self.size)19 self.items[index] = value2021 def append(self, value):22 self.insert(self.size, value)2324 def insert(self, index, value):25 self._check(index, self.size + 1)26 if self.size == len(self.items):27 self._grow()28 for i in range(index, self.size):29 self.items[i + 1] = self.items[i]30 self.items[index] = value31 self.size += 13233 def remove_at(self, index):34 self._check(index, self.size)35 removed = self.items[index]36 for i in range(index, self.size - 1):37 self.items[i] = self.items[i + 1]38 self.size -= 139 self.items[self.size] = None40 return removed4142 def _grow(self):43 bigger = [None] * (len(self.items) * 2)44 for i in range(self.size):45 bigger[i] = self.items[i]46 self.items = bigger4748 def _check(self, index, limit):49 if index < 0 or index >= limit:50 raise IndexError(f"index {index}, size {self.size}")

Check

Try it

Fill in

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

def remove_at(self, index):
    self._check(index, self.size)
    removed = self.items[index]
    for i in range(index, self.size - 1):
        self.items[i] = self.items[]
    self.size -= 1
    self.items[self.size] = None
    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, it has TrimExcess();
• Python (CPython) shrinks by itself when the size falls under half of the places. The language does not promise it, CPython decides.
• 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: - list always holds references to objects, even for numbers, and the objects themselves are elsewhere in memory. For many numbers next to each other there is array in the standard library, and data analysis uses NumPy.

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(self, 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. remove_at 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 index(self, value), which returns the index or -1, and remove(self, 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