How a dynamic array grows when it runs out of room

Your list just ran out of room. Here's what it does.

An array keeps items in a fixed block of slots. When the block is full, it builds a new one twice as big and copies every item across.

Because the size doubles, the copying gets rarer and rarer: here 16 adds cost 12 copies, under one per add.

Those are the real sizes a Rust Vec uses: 4, then 8, then 16.

#datastructures #programming #computerscience #coding #technology