Lining things up: arrays and lists

Lockers packed together: the array

Earlier we learned that each container
has its own shape.
The simplest shape of all is the array.
It is a locker where numbered slots
are packed together in one row.
Slot 0, slot 1, slot 2,
each slot carries its own number.
Since the slots are all packed together,
knowing the number tells you at once where it 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.
Since the slots sit side by side,
any slot is pinned in one step.
Pulling something out by number like this
is called fast access.
It is the array's biggest strength.
But must the slots really stay packed?
Could we not scatter them instead?

Scattered lockers: the list

A list does not pack its slots.
The slots are scattered here and there.
So how is the order kept?
Each slot gets one little note.
That note holds the address
of where the next slot is.
So from the first slot you read its note
and move to the next slot, then read that note
and go on to the one after.

Tap the note to follow it to the next slot. The slots are scattered, but the notes keep the order.

Following the notes,
the scattered slots linked into one line.
Unlike an array that jumps by number,
a list must read each note
and go one slot at a time, in turn.
It looks a little more bothersome,
yet this scattered structure
gives an unexpected advantage.
You will soon see what it is.

Fast access vs slow access

Now let us compare the two.
Say you want the fifth slot.
For an array, the number alone does it.
The slots are packed, so it jumps in one go.
A list cannot do that.
From the first slot you follow the notes,
one slot, two slots, three slots,
counting your way along in turn.
So the farther it is, 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 clicks.

The difference is clear.
The array took one tap to arrive,
while the list took several taps to get there.
For pulling things out,
the array that jumps by number is far faster.
So is the array simply 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, into the middle of the line
let us slip a new slot.
For a list it is very easy.
You change where the front slot's note points
so it points to the new slot,
and make the new slot's note
point to what used to be next.
Fix just two notes,
leave the rest of the slots as they are, and it is done.

Insert a new slot in the middle. The list fixes two notes; the array pushes every later slot over. Compare how much work each takes.

How did the array fare?
To make room in the middle
it had to push every later slot over, one by one.
The slots are packed, so there is no empty gap.
The list, meanwhile, finished with two notes.
So for inserting in the middle often,
a list is far more comfortable.
Fast access goes to the array,
easy insertion goes to the list.
The two are a trade for each other.

Let's wrap up

Gathered on one line, it is this.
An array is a locker of packed numbered slots,
with fast access by number.
A list is scattered slots,
each wearing a note with the next slot's address,
so inserting in the middle is easy.
Reaching the fifth one, the array is fast;
slipping one into the middle, the list is comfortable.
Pick 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,
depending on how you store them,
are good at different jobs.
Arrays and lists
are the first fork in choosing a container's shape.
Next we will look at special containers
that put in and take out
only at one end,
stacking and queueing, together.