Jump to Song 500: Arrays

Find out why a music app jumps to song 500 in one step however long the playlist is, while adding a song at the top gets slower as the playlist grows, and meet the structure behind both: the array.

Apprentice · Data Structures · Updated

By

After this lesson you can

  • Explain why reading or changing any index of an array takes one step, O(1)
  • Count how many items move when an array inserts or removes in the middle

Key takeaways

  • An array keeps its items side by side in memory, each in a numbered slot called its index, counting from 0.
  • Reading or changing the item at any index is O(1): the computer works out where the slot is with one sum.
  • Inserting or removing in the middle is O(n): every item after that spot has to scoot over by one.
  • A plain array's size is fixed when it's made: it can't grow.
  • An array fits a job that reads by position and adds at the end; a job that keeps adding at the front pays for every item after it.

Before this: Why "Play Track 750,000" Is Instant and "Find Golden Hour" Isn't: Memory as Mailboxes, where songs side by side in numbered slots let the app reach any track with one sum, and Arrays and Lists, where you used arrays and lists without asking what's inside them.

Module 1 showed why the music app's Shuffle is instant: the songs sit side by side in numbered slots, so song 500 is where the row starts plus 500 slots, one sum at any length. The app's playlists have grown since, and another button is getting slower. Add to top puts a new song first, and it takes a little longer with every song the playlist gains. At 100,000 songs, people notice the pause.

Same playlist, two buttons: one costs the same at any size, and one grows with the playlist. The side-by-side layout that makes Shuffle instant turns out to be what makes Add to top slow. By the end of this lesson you'll know why, and which of the array's jobs are cheap and which aren't. First, the plain fixes for Add to top.

What would you try?

The job: put a new song first, and keep Shuffle's one-sum jump working.

Write it into slot 0. One step, and Midnight Bus, the old first song, is gone: written over.

Put it in the first free slot at the end, and remember that it belongs at the top. One step again, and nothing is lost. But now the order in memory isn't the order on screen. Shuffle's "start plus 500" lands on the wrong song, and every read has to check the notes first. The one-sum jump is broken.

Move every song one slot along, then write the new song into slot 0. Start from the last song, so nothing gets written over. The order is right, and Shuffle still works. But every song moves: at 100,000 songs, one tap moves 100,000 songs.

What we tried Add to top Where it breaks
Write it into slot 0 O(1) the old first song is lost
Add it at the end, and remember it belongs first O(1) Shuffle lands on the wrong song
Move every song along, then write slot 0 O(n): 100,000 moves at 100,000 songs long playlists

The questions that lead to it

What makes Shuffle instant? Slot i is always the start plus i, because the slots are side by side, all the same size, with no gaps.

So where can a new first song go? Nowhere in front of slot 0. With no gaps allowed, the only way to make room is to move everyone along.

So the fast read and the slow insert come from the same rule. Side by side with no gaps buys "any slot in one step", and it costs "a new song in front moves everyone". Every structure in this course is a trade like that, and this one has a name you met in Module 1.

How it got its name

The row of side-by-side slots is an array, and every language has it built in. It takes a run of memory's mailboxes, side by side, and puts one item in each.

  • Each slot's number is its index. It counts from 0: the first song is at index 0, and the last song of an 8-song playlist is at index 7. The index is "how many slots from the start", so the first one is 0 slots from the start.
  • Finding a slot takes one sum, the start plus the index, whatever the index is. Slot 3 and slot 3,000,000 cost the same. That's constant time, written O(1) and read "big O of one": the work stays the same however long the playlist gets. Changing a slot is O(1) too.

A row of eight mailboxes side by side, numbered 0 to 7 from the left, each holding one song title: Midnight Bus in mailbox 0 through Golden Hour in mailbox 7. An arrow labeled "start + 3" jumps straight to mailbox 3, Paper Boats, without passing the others

Here's an 8-song playlist as an array, read and changed by index:

string[] playlist = { "Midnight Bus", "Lemon Skies", "Slow Rain", "Paper Boats", "Neon Garden", "Quiet Harbor", "Sunday Static", "Golden Hour" };

Console.WriteLine("Slots: " + playlist.Length);
Console.WriteLine("Index 0: " + playlist[0]);
Console.WriteLine("Index 3: " + playlist[3]);
Console.WriteLine("Index 7: " + playlist[playlist.Length - 1]);

playlist[5] = "Harbor Lights";
Console.WriteLine("Index 5 is now: " + playlist[5]);
Slots: 8
Index 0: Midnight Bus
Index 3: Paper Boats
Index 7: Golden Hour
Index 5 is now: Harbor Lights
void main() {
    String[] playlist = {"Midnight Bus", "Lemon Skies", "Slow Rain", "Paper Boats", "Neon Garden", "Quiet Harbor", "Sunday Static", "Golden Hour"};

    IO.println("Slots: " + playlist.length);
    IO.println("Index 0: " + playlist[0]);
    IO.println("Index 3: " + playlist[3]);
    IO.println("Index 7: " + playlist[playlist.length - 1]);

    playlist[5] = "Harbor Lights";
    IO.println("Index 5 is now: " + playlist[5]);
}
Slots: 8
Index 0: Midnight Bus
Index 3: Paper Boats
Index 7: Golden Hour
Index 5 is now: Harbor Lights
playlist = ["Midnight Bus", "Lemon Skies", "Slow Rain", "Paper Boats", "Neon Garden", "Quiet Harbor", "Sunday Static", "Golden Hour"]

print(f"Slots: {len(playlist)}")
print(f"Index 0: {playlist[0]}")
print(f"Index 3: {playlist[3]}")
print(f"Index 7: {playlist[len(playlist) - 1]}")

playlist[5] = "Harbor Lights"
print(f"Index 5 is now: {playlist[5]}")
Slots: 8
Index 0: Midnight Bus
Index 3: Paper Boats
Index 7: Golden Hour
Index 5 is now: Harbor Lights
const playlist = ["Midnight Bus", "Lemon Skies", "Slow Rain", "Paper Boats", "Neon Garden", "Quiet Harbor", "Sunday Static", "Golden Hour"];

console.log(`Slots: ${playlist.length}`);
console.log(`Index 0: ${playlist[0]}`);
console.log(`Index 3: ${playlist[3]}`);
console.log(`Index 7: ${playlist[playlist.length - 1]}`);

playlist[5] = "Harbor Lights";
console.log(`Index 5 is now: ${playlist[5]}`);
Slots: 8
Index 0: Midnight Bus
Index 3: Paper Boats
Index 7: Golden Hour
Index 5 is now: Harbor Lights
const playlist: string[] = ["Midnight Bus", "Lemon Skies", "Slow Rain", "Paper Boats", "Neon Garden", "Quiet Harbor", "Sunday Static", "Golden Hour"];

console.log(`Slots: ${playlist.length}`);
console.log(`Index 0: ${playlist[0]}`);
console.log(`Index 3: ${playlist[3]}`);
console.log(`Index 7: ${playlist[playlist.length - 1]}`);

playlist[5] = "Harbor Lights";
console.log(`Index 5 is now: ${playlist[5]}`);
Slots: 8
Index 0: Midnight Bus
Index 3: Paper Boats
Index 7: Golden Hour
Index 5 is now: Harbor Lights

C# and Java arrays have a fixed number of slots, set when the array is made. Python's list and JavaScript's Array are growing arrays, which add slots when they fill up: the next lesson, The Ninth Song Won't Fit: Growing Arrays, builds one. Reading and changing by index work the same in all five.

Add to top, in code

Here's the third try, the one an array actually does. The slots are side by side with no gaps, which is exactly what made the jump fast, and it means there's no room in front of index 0. To make room, every song moves one slot to the right, starting from the last one so nothing gets overwritten. Then the new song goes in index 0.

The same happens in the middle. Your friend wants Paper Boats in the third spot of a 6-song playlist: every song from index 2 onward moves one slot right, and Paper Boats goes into index 2. Removing works the other way: take out the song at index 0, and every song after it moves one slot left to close the gap.

The code below keeps the playlist in an array of 8 slots with a count of how many are in use, and counts every song it moves.

int InsertAt(string[] slots, int count, int index, string song)
{
    int moves = 0;
    for (int i = count; i > index; i--)
    {
        slots[i] = slots[i - 1];
        moves++;
    }
    slots[index] = song;
    return moves;
}

int RemoveAt(string[] slots, int count, int index)
{
    int moves = 0;
    for (int i = index; i < count - 1; i++)
    {
        slots[i] = slots[i + 1];
        moves++;
    }
    return moves;
}

string[] slots = { "Midnight Bus", "Lemon Skies", "Slow Rain", "Neon Garden", "Quiet Harbor", "Golden Hour", "", "" };
int count = 6;

int moved = InsertAt(slots, count, 2, "Paper Boats");
count++;
Console.WriteLine("Insert at 2: " + string.Join(", ", slots, 0, count) + " (" + moved + " songs moved)");

moved = RemoveAt(slots, count, 0);
count--;
Console.WriteLine("Remove at 0: " + string.Join(", ", slots, 0, count) + " (" + moved + " songs moved)");
Insert at 2: Midnight Bus, Lemon Skies, Paper Boats, Slow Rain, Neon Garden, Quiet Harbor, Golden Hour (4 songs moved)
Remove at 0: Lemon Skies, Paper Boats, Slow Rain, Neon Garden, Quiet Harbor, Golden Hour (6 songs moved)
int insertAt(String[] slots, int count, int index, String song) {
    int moves = 0;
    for (int i = count; i > index; i--) {
        slots[i] = slots[i - 1];
        moves++;
    }
    slots[index] = song;
    return moves;
}

int removeAt(String[] slots, int count, int index) {
    int moves = 0;
    for (int i = index; i < count - 1; i++) {
        slots[i] = slots[i + 1];
        moves++;
    }
    return moves;
}

void main() {
    String[] slots = {"Midnight Bus", "Lemon Skies", "Slow Rain", "Neon Garden", "Quiet Harbor", "Golden Hour", "", ""};
    int count = 6;

    int moved = insertAt(slots, count, 2, "Paper Boats");
    count++;
    IO.println("Insert at 2: " + String.join(", ", Arrays.copyOf(slots, count)) + " (" + moved + " songs moved)");

    moved = removeAt(slots, count, 0);
    count--;
    IO.println("Remove at 0: " + String.join(", ", Arrays.copyOf(slots, count)) + " (" + moved + " songs moved)");
}
Insert at 2: Midnight Bus, Lemon Skies, Paper Boats, Slow Rain, Neon Garden, Quiet Harbor, Golden Hour (4 songs moved)
Remove at 0: Lemon Skies, Paper Boats, Slow Rain, Neon Garden, Quiet Harbor, Golden Hour (6 songs moved)
def insert_at(slots, count, index, song):
    moves = 0
    for i in range(count, index, -1):
        slots[i] = slots[i - 1]
        moves += 1
    slots[index] = song
    return moves


def remove_at(slots, count, index):
    moves = 0
    for i in range(index, count - 1):
        slots[i] = slots[i + 1]
        moves += 1
    return moves


slots = ["Midnight Bus", "Lemon Skies", "Slow Rain", "Neon Garden", "Quiet Harbor", "Golden Hour", "", ""]
count = 6

moved = insert_at(slots, count, 2, "Paper Boats")
count += 1
print(f"Insert at 2: {', '.join(slots[:count])} ({moved} songs moved)")

moved = remove_at(slots, count, 0)
count -= 1
print(f"Remove at 0: {', '.join(slots[:count])} ({moved} songs moved)")
Insert at 2: Midnight Bus, Lemon Skies, Paper Boats, Slow Rain, Neon Garden, Quiet Harbor, Golden Hour (4 songs moved)
Remove at 0: Lemon Skies, Paper Boats, Slow Rain, Neon Garden, Quiet Harbor, Golden Hour (6 songs moved)
function insertAt(slots, count, index, song) {
  let moves = 0;
  for (let i = count; i > index; i--) {
    slots[i] = slots[i - 1];
    moves++;
  }
  slots[index] = song;
  return moves;
}

function removeAt(slots, count, index) {
  let moves = 0;
  for (let i = index; i < count - 1; i++) {
    slots[i] = slots[i + 1];
    moves++;
  }
  return moves;
}

const slots = ["Midnight Bus", "Lemon Skies", "Slow Rain", "Neon Garden", "Quiet Harbor", "Golden Hour", "", ""];
let count = 6;

let moved = insertAt(slots, count, 2, "Paper Boats");
count++;
console.log(`Insert at 2: ${slots.slice(0, count).join(", ")} (${moved} songs moved)`);

moved = removeAt(slots, count, 0);
count--;
console.log(`Remove at 0: ${slots.slice(0, count).join(", ")} (${moved} songs moved)`);
Insert at 2: Midnight Bus, Lemon Skies, Paper Boats, Slow Rain, Neon Garden, Quiet Harbor, Golden Hour (4 songs moved)
Remove at 0: Lemon Skies, Paper Boats, Slow Rain, Neon Garden, Quiet Harbor, Golden Hour (6 songs moved)
function insertAt(slots: string[], count: number, index: number, song: string): number {
  let moves = 0;
  for (let i = count; i > index; i--) {
    slots[i] = slots[i - 1];
    moves++;
  }
  slots[index] = song;
  return moves;
}

function removeAt(slots: string[], count: number, index: number): number {
  let moves = 0;
  for (let i = index; i < count - 1; i++) {
    slots[i] = slots[i + 1];
    moves++;
  }
  return moves;
}

const slots: string[] = ["Midnight Bus", "Lemon Skies", "Slow Rain", "Neon Garden", "Quiet Harbor", "Golden Hour", "", ""];
let count = 6;

let moved = insertAt(slots, count, 2, "Paper Boats");
count++;
console.log(`Insert at 2: ${slots.slice(0, count).join(", ")} (${moved} songs moved)`);

moved = removeAt(slots, count, 0);
count--;
console.log(`Remove at 0: ${slots.slice(0, count).join(", ")} (${moved} songs moved)`);
Insert at 2: Midnight Bus, Lemon Skies, Paper Boats, Slow Rain, Neon Garden, Quiet Harbor, Golden Hour (4 songs moved)
Remove at 0: Lemon Skies, Paper Boats, Slow Rain, Neon Garden, Quiet Harbor, Golden Hour (6 songs moved)

Four rows of the same 8-slot array, one per step. Row 1: six songs in slots 0 to 5. Row 2: Golden Hour moves from slot 5 to slot 6. Row 3: Quiet Harbor, Neon Garden and Slow Rain have also each moved one slot right, leaving slot 2 free. Row 4: Paper Boats is in slot 2, and a counter reads "4 songs moved"

Inserting at index 2 moved 4 songs: everything after the spot. Inserting at index 0 moves every song in the playlist. With n songs, the worst case moves all n, so inserting or removing at the front or in the middle is linear time, O(n) ("big O of n"): twice the songs, twice the moving. That's the Add to top button: at 100,000 songs, one tap moves 100,000 songs. Adding at the end, when there's a free slot, moves nobody, so that one is O(1).

Try it. Change the insert to index 0 and run it again. How many songs move now? Then change it to index 6, the first free slot. What does the counter say, and why?

When an array isn't the answer

An array is the best structure there is for "jump to number i", and for reading every item in order. It's the wrong one for two jobs in this module. A playlist that keeps adding at the front pays for every song after the spot, every time: "Play Next" Without Moving Everyone: Linked Lists fixes that. And a plain array is built to one size, so the 9th song of an 8-slot playlist has nowhere to go: that's the next lesson.

The array's cost card

Operation Big-O Why, in everyday words
Read or change the item at an index O(1) Walk straight to the mailbox by its number
Find an item by its value O(n) Open the mailboxes one by one until it turns up
Add or remove at the end, when there's a free slot O(1) Nobody has to move
Insert or remove at the front or in the middle O(n) Everyone after the spot scoots over by one
Make it bigger Not possible The wall of mailboxes is built to one size

Check yourself

2 questions to try on the lesson page.

So what

Whenever you pick where to put new items, you're choosing how much scooting your code does. Reading by position is free at any size, adding to the end is cheap, and adding to the front is expensive. Knowing those three facts will save you from a slow list long before you ever measure one.

Key terms

Cheat sheets