Linked lists

New idea

Squeezing one name into the front

An array holds 1,000,000 names. You want a new name at the very front. Sounds quick? The computer has to move all 1,000,000 names one box to the right to make room.

Array boxes sit side by side with no gaps, which is what makes scores[700] instant. But it also means there's no space to slip something in. Inserting at the front or in the middle is O(n).

So what if the items didn't have to sit next to each other at all?