Suppose you keep 1,000 to-dos at consecutive addresses. What is fast and what is slow when you store them like this?
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, however, means pushing every value after it back one slot.
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.
Press run.
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.
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.