Where your data actually lives

Before any data structure makes sense, it helps to know what the computer is actually doing when you write nums[3].

Memory is a numbered street#

Think of your computer's memory as one very long street of identical houses. Every house holds one small value, and every house has a number. That number is called an address.

The street has one useful property: house 5000 can be reached as fast as house 5. You do not walk down the street counting. The computer jumps straight to any address in the same amount of time, the way you can open a book at page 400 without turning 399 pages.

That single property is where almost every cost in this course comes from.

What an array is#

An array is a promise: these values sit in houses next to each other, starting here.

If an array of numbers starts at address 1000, and each number takes 4 houses, then:

One multiply and one add, whatever the index. That is why reading nums[7] costs the same as nums[0], and why we call it constant time, written O(1).

It is also why array indexes start at 0. nums[0] means "no houses along from the start", not "the first one".

The price of that promise#

Sitting next to each other is what makes indexing instant. It is also what makes two other things slow.

Inserting in the middle. To put a value at position 2 of [a, b, c, d, e], everything from position 2 onward has to shuffle one house along to make room. Five values, four moves. A million values, and you are moving most of a million houses. That is O(n).

Growing. The houses after your array might already belong to something else. When an array runs out of room, the usual answer is to find a bigger empty stretch somewhere else and copy everything across.

Why this matters later#

Every structure in this track is a different answer to one question: what are you willing to give up?

• An array gives you instant indexing and charges you for inserting.
• A linked list gives you instant inserting and charges you for indexing.
• A hash table gives you instant lookup by key and charges you memory, plus giving up any sense of order.

None of them is better. They are trades, and knowing which trade you are making is most of choosing correctly.

The one idea to keep#

Next to each other means fast to reach and expensive to rearrange. Everything else follows from that.

Common mistakes#

• Thinking nums[1000000] is slower than nums[0]. It is not.
• Thinking inserting at the front of an array is cheap. It is the most expensive place.
• Forgetting that "the array grew" may have quietly copied every value somewhere else.