A data structure is a way of arranging data so the things you do most are quick. No single one is best at everything, so the skill is knowing what each costs.
The simplest is the array: values stored one after another in a single block of memory. Because every slot is the same size, the computer can work out where item number i is with one sum (start + i × size) and go straight there. Reading or changing any item by its index takes the same short time however long the array is.
The cost shows up when you insert or delete anywhere but the end. To put a new value at the front, every other value has to shuffle one place along to make room. With a million items, that's a million moves.
Python's list is an array underneath (a dynamic array: when it runs out of room it quietly moves to a bigger block, about twice the size, so adding at the end stays quick on average).
nums = [5, 7, 9]
nums.append(11) # quick: at the end
nums.insert(0, 3) # slower: everything moves along
print(nums, nums[2])[3, 5, 7, 9, 11] 7
Why can an array read item 500 as fast as item 0?
| Array | Values side by side in one block of memory. |
|---|---|
| Index | A position, from 0. Reading by index is instant. |
| Insert / delete in the middle | Slow: the items after it have to move. |
| Dynamic array | Grows by moving to a bigger block. Python's list. |