Arrays and lists in memory

An array is a row of items stored one after another in memory. That layout makes reading any item very fast and makes inserting an item in the middle slow.

A compiler could keep the line numbers of its warnings in such a row. Adding a new warning at the right place means moving every later number along by one.

Memory is a long row of numbered boxes. Each box has an address. An array takes a run of boxes with no gaps, and every element is the same size.

So the computer needs no search to find one. It works out the address: the start, plus the index times the size of one element.

python3 -c "import array; a = array.array('i', [10, 20, 30]); print(a.itemsize, len(a))"

python3 -c "import array; print(array.array('i').itemsize, array.array('d').itemsize)"

There are no gaps, so a new element cannot just be squeezed in. Every element after the chosen place must move one box along, starting from the last one.

Deleting is the reverse: the later elements move back to close the gap. Adding at the very end moves nothing, so it is cheap.

# Insert 15 at position 1 of a row of four, counting every shift.
items = [10, 20, 30, 40]
shifts = 0
items.append(0)
i = len(items) - 1
while i > 1:
    items[i] = items[i - 1]
    shifts = shifts + 1
    i = i - 1
items[1] = 15
print(items, shifts)
# Change both 1s (in "i > 1" and "items[1]") to 0 and run again.

python3 -c "a = [10, 20, 30]; a.insert(1, 15); print(a)"

python3 -c "a = [10, 20, 30, 40]; a.pop(0); print(a)"

A block of memory cannot always grow in place, because the boxes after it may be in use. When a list is full, Python asks for a bigger block, copies every element across and frees the old one.

It asks for more room than it needs, often about double, so most appends find a free space waiting.