What is an array vs a list
There is more than one way to keep many things in order. Pack the slots side by side in numbered order, and you can take any one out the moment you give its number. Scatter the slots around instead and link them with notes that say where the next slot is, and it becomes easy to slip a new slot into the middle. Which matters more: taking out fast, or slipping in easily?
Lockers packed together: the array
In the last lesson we saw that each container has its own shape. The simplest of them is the array: think of a locker whose numbered slots are packed together in one row.
The slots are usually numbered from 0: slot 0, slot 1, slot 2, and so on. Because all the slots are the same size and sit side by side, adding the slot size times the number to the starting position tells you at once where any slot is.
Tap a number to jump straight to that slot. The slots are packed together, so the number finds it at once.
When you tapped a number, that slot lit up right away. Because the slots sit side by side, any slot is reached in one step, and it takes the same time whether there are ten slots or a million.
Taking something out by number like this is called fast access, and it is the array's biggest strength. But must the slots really be packed together? What happens if we scatter them?
Scattered lockers: the list
A list does not pack its slots together; they are scattered around memory. So how is the order kept? Each slot carries a note that says where the next slot is.
From the first slot you read its note and go to the next slot, read that note and go on to the one after. Because the slots are linked one after another by notes, this shape is called a linked list.
Tap the note to follow it to the next slot. The slots are scattered, but the notes keep them in order.
Following the notes linked the scattered slots into one line. Unlike an array, which jumps by number, a list has to read each note and go one slot at a time.
That looks a little more bothersome, but this scattered structure has an unexpected advantage. You will soon see what it is.
Fast access vs slow access
Now let's compare the two. Say you want the fifth slot. For an array, giving the number is all it takes; the slots are packed, so it jumps there in one go.
A list cannot do that. Starting from the first slot, it follows the notes and counts its way along: one slot, two slots, three slots. So the farther away the slot, the longer it takes.
Reach the fifth one. The array does it in one step; the list goes one slot at a time from the start. Compare the number of taps.
The difference is clear. The array arrived with one tap, while the list got there only after several. For taking things out, the array that jumps by number is far faster.
So is the array always better? No. In the next scene comes the moment the list shines: when you slip something into the middle.
Slipping one into the middle
This time, let's slip a new slot into the middle of the line. For a list it is very easy: change the front slot's note so it points to the new slot, and make the new slot's note point to what used to come next.
Rewrite just two notes and the other slots need not be touched. Even with a million slots, only two notes change.
Insert a new slot in the middle. The list rewrites two notes; the array pushes every later slot over. Compare how much work each takes.
How did the array do? To make room in the middle, it had to push every later slot over, one by one, because the slots are packed and there is no gap. The list finished with two notes.
So for jobs that insert in the middle often, a list is far more convenient. Fast access goes to the array, easy insertion to the list: gaining one means giving up the other.
Summary
In short: an array is a locker of numbered slots packed together, so you can take items out by number at once. A list is scattered slots, each with a note saying where the next one is, so inserting in the middle is easy.
To reach the fifth item, the array is fast; to slip one into the middle, the list is convenient. Choose by what you do most often.
Tap the key points in order to review. (packed-locker array → scattered-locker list → fast vs slow access → middle insertion)
Now you know that even the same things are good at different jobs depending on how you store them. Arrays and lists are the first fork in choosing a container's shape.
The next lesson covers two special containers: the stack, which adds and removes only at one end, and the queue, which lets things out only in the order they lined up.