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
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.

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)

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.