yeolyi.comSeongyeol's CS

Arrays

Suppose you keep 1,000 to-dos at consecutive addresses. What is fast and what is slow when you store them like this?

Arrays

Like the C arrays in the array index post, laying values out one after another with no gaps is called an array in data structures too. Python’s list is also implemented as an array internally.

If the start address is 100, the value at index 3 is at address 103. Memory can read any slot right away once it knows the address, so even the value at index 1000 is one addition away.

Inserting

Inserting, however, means pushing every value after it back one slot.

10203040

Insert 5 at the front.

Python’s insert(0, x) on a list also shifts every value back one slot internally like this. Let’s read 100,000 values one by one, and insert at the front 1,000 times.

Read every value
1a = [0] * 100_000
2for i in range(len(a)):
3 x = a[i]

Press run.

Insert at the front
1a = [0] * 100_000
2for _ in range(1000):
3 a.insert(0, 0)

Press run.

Reading 100,000 times finishes right away, but inserting at the front takes long even 1,000 times, because each insert pushes 100,000 values. Removing is the same, since every value after it has to be pulled forward one slot.

Challenge

You put 10 values one by one into an empty array. Each time, if the array holds n values, you put the new one at index n // 2, the middle, shifting every value after it back one slot. How many times are values moved in total by the time all 10 are in? Answer with a number.