The dynamic array from the inside

Code in:JavaC#PythonJavaScript

In short: A dynamic array (the JavaScript array) has 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.

const orderLines = ["Flour 25 kg", "Sugar 10 kg", "Oil 5 l", "Rice 10 kg"];
const cart = [];
for (const line of orderLines) {
  cart.unshift(line);
}
console.log("The cart: " + cart.join(", "));

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

The array 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 {
  constructor() {
    this.items = new Array(8);
    this.length = 0;
  }

  get capacity() {
    return this.items.length;
  }

  get(index) {
    this.#check(index, this.length);
    return this.items[index];
  }

  set(index, value) {
    this.#check(index, this.length);
    this.items[index] = value;
  }

  add(value) {
    this.insert(this.length, value);
  }

  insert(index, value) {
    this.#check(index, this.length + 1);
    if (this.length === this.items.length) {
      this.#grow();
    }
    for (let i = this.length; i > index; i--) {
      this.items[i] = this.items[i - 1];
    }
    this.items[index] = value;
    this.length++;
  }

  removeAt(index) {
    this.#check(index, this.length);
    const removed = this.items[index];
    for (let i = index; i < this.length - 1; i++) {
      this.items[i] = this.items[i + 1];
    }
    this.length--;
    this.items[this.length] = undefined;
    return removed;
  }

  #grow() {
    const bigger = new Array(this.items.length * 2);
    for (let i = 0; i < this.length; i++) {
      bigger[i] = this.items[i];
    }
    this.items = bigger;
  }

  #check(index, limit) {
    if (index < 0 || index >= limit) {
      throw new RangeError(`index ${index}, size ${this.length}`);
    }
  }
}

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

insert(index, value) {
  this.#check(index, this.length + 1);
  if (this.length === this.items.length) {
    this.#grow();
  }
  for (let i = this.length; i > index; i--) {
    this.items[i] = this.items[i - 1];
  }
  this.items[index] = value;
  this.length++;
}

removeAt(index) {
  this.#check(index, this.length);
  const removed = this.items[index];
  for (let i = index; i < this.length - 1; i++) {
    this.items[i] = this.items[i + 1];
  }
  this.length--;
  this.items[this.length] = undefined;
  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. get(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 undefined: the old reference would keep the product alive in memory.
7. get(5): place 5 exists (the capacity is 8), but it is not in the cart. The check compares with the size and throws RangeError.
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.

const cart = new DynamicArray();
cart.add("Bread");
cart.add("Milk");
cart.add("Coffee");
cart.add("Butter");
cart.add("Apples");
console.log(cart.get(3));
cart.insert(0, "Cheese");
cart.removeAt(2);
for (let i = 0; i < cart.length; i++) {
  console.log(`${i}: ${cart.get(i)}`);
}
console.log("Places: " + cart.capacity);
try {
  cart.get(5);
} catch (e) {
  console.log("Error: " + e.message);
}

Output

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

The built-in JavaScript array does not check the index: cart[5] outside the array gives undefined, with no error. Our class checks and throws RangeError, as Java, C# and Python do.

Try it

Predict the output

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

class DynamicArray {
  constructor() {
    this.items = new Array(8);
    this.length = 0;
  }

  get capacity() {
    return this.items.length;
  }

  get(index) {
    this.#check(index, this.length);
    return this.items[index];
  }

  set(index, value) {
    this.#check(index, this.length);
    this.items[index] = value;
  }

  add(value) {
    this.insert(this.length, value);
  }

  insert(index, value) {
    this.#check(index, this.length + 1);
    if (this.length === this.items.length) {
      this.#grow();
    }
    for (let i = this.length; i > index; i--) {
      this.items[i] = this.items[i - 1];
    }
    this.items[index] = value;
    this.length++;
  }

  removeAt(index) {
    this.#check(index, this.length);
    const removed = this.items[index];
    for (let i = index; i < this.length - 1; i++) {
      this.items[i] = this.items[i + 1];
    }
    this.length--;
    this.items[this.length] = undefined;
    return removed;
  }

  #grow() {
    const bigger = new Array(this.items.length * 2);
    for (let i = 0; i < this.length; i++) {
      bigger[i] = this.items[i];
    }
    this.items = bigger;
  }

  #check(index, limit) {
    if (index < 0 || index >= limit) {
      throw new RangeError(`index ${index}, size ${this.length}`);
    }
  }
}

const cart = new DynamicArray();
for (let i = 1; i <= 8; i++) {
  cart.add("P" + i);
}
cart.insert(0, "P0");
console.log("Products: " + cart.length);
console.log("Places: " + cart.capacity);
console.log(cart.get(8));

Answer

Products: 9
Places: 9
P8

Products: 9
Places: 16
P0

Products: 9
Places: 16
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):

const orderLines = ["Flour 25 kg", "Sugar 10 kg", "Oil 5 l", "Rice 10 kg"];
const cart = [];
for (const line of orderLines) {
  cart.push(line);
}
const newestFirst = cart.toReversed();
console.log("The cart: " + newestFirst.join(", "));

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 {
  constructor() {
    this.items = new Array(8);
    this.length = 0;
  }

  get capacity() {
    return this.items.length;
  }

  get(index) {
    this.#check(index, this.length);
    return this.items[index];
  }

  set(index, value) {
    this.#check(index, this.length);
    this.items[index] = value;
  }

  add(value) {
    this.insert(this.length, value);
  }

  insert(index, value) {
    this.#check(index, this.length + 1);
    if (this.length === this.items.length) {
      this.#grow();
    }
    for (let i = this.length; i > index; i--) {
      this.items[i] = this.items[i - 1];
    }
    this.items[index] = value;
    this.length++;
  }

  removeAt(index) {
    this.#check(index, this.length);
    const removed = this.items[index];
    for (let i = index; i < this.length - 1; i++) {
      this.items[i] = this.items[i + 1];
    }
    this.length--;
    this.items[this.length] = undefined;
    return removed;
  }

  #grow() {
    const bigger = new Array(this.items.length * 2);
    for (let i = 0; i < this.length; i++) {
      bigger[i] = this.items[i];
    }
    this.items = bigger;
  }

  #check(index, limit) {
    if (index < 0 || index >= limit) {
      throw new RangeError(`index ${index}, size ${this.length}`);
    }
  }
}

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 {
  constructor() {
    this.items = new Array(8);
    this.length = 0;
    this.writes = 0;
  }

  get capacity() {
    return this.items.length;
  }

  get(index) {
    this.#check(index, this.length);
    return this.items[index];
  }

  set(index, value) {
    this.#check(index, this.length);
    this.items[index] = value;
  }

  add(value) {
    this.insert(this.length, value);
  }

  insert(index, value) {
    this.#check(index, this.length + 1);
    if (this.length === this.items.length) {
      this.#grow();
    }
    for (let i = this.length; i > index; i--) {
      this.items[i] = this.items[i - 1];
      this.writes++;
    }
    this.items[index] = value;
    this.writes++;
    this.length++;
  }

  removeAt(index) {
    this.#check(index, this.length);
    const removed = this.items[index];
    for (let i = index; i < this.length - 1; i++) {
      this.items[i] = this.items[i + 1];
    }
    this.length--;
    this.items[this.length] = undefined;
    return removed;
  }

  #grow() {
    const bigger = new Array(this.items.length * 2);
    for (let i = 0; i < this.length; i++) {
      bigger[i] = this.items[i];
      this.writes++;
    }
    this.items = bigger;
  }

  #check(index, limit) {
    if (index < 0 || index >= limit) {
      throw new RangeError(`index ${index}, size ${this.length}`);
    }
  }
}

for (const n of [10, 1000, 100000]) {
  const cart = new DynamicArray();
  for (let i = 0; i < n; i++) {
    cart.add(String(1001 + i));
  }
  console.log(`at the end, n = ${n}: ${cart.writes} writes`);
}
for (const n of [10, 1000]) {
  const cart = new DynamicArray();
  for (let i = 0; i < n; i++) {
    cart.insert(0, String(1001 + i));
  }
  console.log(`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:

const cart = new DynamicArray();
cart.add("Bread");
cart.add("Milk");
cart.add("Coffee");
cart.insert(0, "Cheese");
for (let i = 0; i < cart.length; i++) {
  console.log(`${i}: ${cart.get(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 constructor() {3 this.items = new Array(8);4 this.length = 0;5 }67 get capacity() {8 return this.items.length;9 }1011 get(index) {12 this.#check(index, this.length);13 return this.items[index];14 }1516 set(index, value) {17 this.#check(index, this.length);18 this.items[index] = value;19 }2021 add(value) {22 this.insert(this.length, value);23 }2425 insert(index, value) {26 this.#check(index, this.length + 1);27 if (this.length === this.items.length) {28 this.#grow();29 }30 for (let i = index; i < this.length; i++) {31 this.items[i + 1] = this.items[i];32 }33 this.items[index] = value;34 this.length++;35 }3637 removeAt(index) {38 this.#check(index, this.length);39 const removed = this.items[index];40 for (let i = index; i < this.length - 1; i++) {41 this.items[i] = this.items[i + 1];42 }43 this.length--;44 this.items[this.length] = undefined;45 return removed;46 }4748 #grow() {49 const bigger = new Array(this.items.length * 2);50 for (let i = 0; i < this.length; i++) {51 bigger[i] = this.items[i];52 }53 this.items = bigger;54 }5556 #check(index, limit) {57 if (index < 0 || index >= limit) {58 throw new RangeError(`index ${index}, size ${this.length}`);59 }60 }61}

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?

removeAt(index) {
  this.#check(index, this.length);
  const removed = this.items[index];
  for (let i = index; i < this.length - 1; i++) {
    this.items[i] = this.items[];
  }
  this.length--;
  this.items[this.length] = undefined;
  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 under half;
• JavaScript (V8) shrinks the memory of the array when a large part of it is empty, for example after pop or length = 0. The language does not promise it, the engine decides.

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: - V8 keeps an array of only small integers as the numbers themselves next to each other, and an array of objects or text as references to them. An array with holes or mixed types becomes slower. For numbers next to each other there are Int32Array and Float64Array.

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