The Ninth Song Won't Fit: Growing Arrays
A playlist of 8 slots crashes on the 9th song. Find a way to let it grow to a million songs without every add slowing down, and meet the structure inside every language's list: the growing array.
Apprentice · Data Structures · Updated
After this lesson you can
- Describe how a growing array adds an item when it's full: a new array twice the size, and every item copied across
- Tell a growing array's count from its capacity
- Choose how a list of items should grow (a fixed size, a fixed step or doubling) for a job, and say why
Key takeaways
- A growing array (a dynamic array) keeps its items in a plain array with some spare slots, and tracks how many slots are in use.
- Its count is how many items it holds; its capacity is how many slots it has before it must grow.
- When it's full, it makes a new array twice the size and copies every item across: one O(n) moving day.
- Reading by index is still O(1), because the items still sit side by side.
- Growing by a fixed step, one slot or a hundred, makes a million adds cost billions of copies; doubling keeps moving days rare.
Before this: Jump to Song 500: Arrays. An array reads any slot in one step, but it's built to one size.
The music app keeps each playlist in an array of 8 slots. That was plenty when it shipped. Then a user tapped Add on a 9th song, and the app crashed: there's no slot 8, and C# and Java stop the program with an "index out of range" error rather than write past the end. Meanwhile, the app's biggest playlists hold thousands of songs, and people add more every day.
So the playlist has to grow, from 8 songs to 9, and on to a million, and adding a song has to stay quick the whole way. By the end of this lesson you'll have the trick every language's list uses for it, the growing array. First, the plain fixes.
What would you try?
Make it bigger up front: 10,000 slots. The 9th song fits, and so does the 9,999th. But most playlists hold 20 songs, so every one of them carries 10,000 slots, almost all empty. And song 10,001 crashes the app all over again. The limit moved; it didn't go away.
Grow by one slot when it's full. Arrays can't stretch, so "growing" means making a new, bigger array and copying every song across. Make it one slot bigger each time, and every add after the first is a moving day: song 9 copies 8 songs, song 10 copies 9, and so on. From an empty playlist, 1,000 songs cost 499,500 copies (0 + 1 + 2 + … + 999), and a million songs cost about 500 billion. Each add is O(n), and all of them together are O(n²).
Grow by 100 slots. Now there's a moving day only once every 100 songs. For 1,000 songs that's 4,500 copies, which looks fixed. But a million songs means 10,000 moving days, each one bigger than the last: about 5 billion copies. The moves are rarer by a fixed amount, and that's all, so it's still O(n²).
| What we tried | 1,000 songs | 1,000,000 songs | Where it breaks |
|---|---|---|---|
| 10,000 slots up front | no copies | crashes at song 10,001 | the cap, and the empty slots |
| Grow by 1 slot | 499,500 copies | about 500 billion copies | every add is a moving day |
| Grow by 100 slots | 4,500 copies | about 5 billion copies | 10,000 moving days, each bigger |
The questions that lead to it
What does the playlist do most? Add a song at the end, over and over, and read songs by their number. Reading is already O(1). Adding has to be quick too.
What can be slow? One add, now and then. Nobody minds a moving day if it's rare.
So how rare can moving day be? Growing by 1 or by 100 adds a fixed amount of room each time, so a longer playlist means more and more moves. What if the extra room grew with the playlist? Rent as much room again as you have: when 8 slots fill, move to 16. That move copies 8 songs, and buys 8 adds with no move at all. The move to 2,048 slots copies 1,024 songs, and buys 1,024 free adds. The bigger the move, the longer the wait for the next one. A million songs need only 20 moving days that way, and about a million copies in all: one per song.
How it got its name
This idea was so useful that it's inside every language's list. It's called a growing array, or a dynamic array: a plain array with a plan for when it fills up.
- It keeps its items in a plain array with some spare slots at the end.
- Adding an item puts it in the next spare slot.
- When there are no spare slots, it makes a new array twice the size, copies every item across, and uses the new array from then on.
It keeps two numbers, and they're easy to mix up:
- Count: how many items it holds now.
- Capacity: how many slots its array has.
The count is never bigger than the capacity. When they're equal, the array is full, and the next add means moving day.
You already know the everyday version. A couple rents a two-room apartment and fills both rooms with boxes. A third box arrives. They don't rent three rooms, because then they'd move again next week: they rent four, twice what they had, carry every box across, and have room to spare for a while.

Building one
This GrowingPlaylist starts with a capacity of 2, the two-room apartment. Its add prints a line every time it moves, so you can watch the capacity double while nine songs go in: the 9th song that crashed the app now fits.
GrowingPlaylist playlist = new GrowingPlaylist();
foreach (string song in new string[] { "Midnight Bus", "Lemon Skies", "Slow Rain", "Paper Boats", "Neon Garden", "Quiet Harbor", "Sunday Static", "Golden Hour", "Velvet Morning" })
{
playlist.Add(song);
}
Console.WriteLine("Count: " + playlist.Count + ", capacity: " + playlist.Capacity);
Console.WriteLine("Index 8: " + playlist.Get(8));
class GrowingPlaylist
{
private string[] slots = new string[2];
private int count = 0;
public int Count => count;
public int Capacity => slots.Length;
public void Add(string song)
{
if (count == slots.Length)
{
string[] bigger = new string[slots.Length * 2];
for (int i = 0; i < count; i++)
{
bigger[i] = slots[i];
}
Console.WriteLine("Moving day: capacity " + slots.Length + " to " + bigger.Length + ", copied " + count + " songs");
slots = bigger;
}
slots[count] = song;
count++;
}
public string Get(int index)
{
if (index < 0 || index >= count)
{
throw new ArgumentOutOfRangeException(nameof(index), "No song at index " + index);
}
return slots[index];
}
}
Moving day: capacity 2 to 4, copied 2 songs
Moving day: capacity 4 to 8, copied 4 songs
Moving day: capacity 8 to 16, copied 8 songs
Count: 9, capacity: 16
Index 8: Velvet Morning
class GrowingPlaylist {
private String[] slots = new String[2];
private int count = 0;
int count() {
return count;
}
int capacity() {
return slots.length;
}
void add(String song) {
if (count == slots.length) {
String[] bigger = new String[slots.length * 2];
for (int i = 0; i < count; i++) {
bigger[i] = slots[i];
}
IO.println("Moving day: capacity " + slots.length + " to " + bigger.length + ", copied " + count + " songs");
slots = bigger;
}
slots[count] = song;
count++;
}
String get(int index) {
if (index < 0 || index >= count) {
throw new IndexOutOfBoundsException("No song at index " + index);
}
return slots[index];
}
}
void main() {
GrowingPlaylist playlist = new GrowingPlaylist();
for (String song : new String[] {"Midnight Bus", "Lemon Skies", "Slow Rain", "Paper Boats", "Neon Garden", "Quiet Harbor", "Sunday Static", "Golden Hour", "Velvet Morning"}) {
playlist.add(song);
}
IO.println("Count: " + playlist.count() + ", capacity: " + playlist.capacity());
IO.println("Index 8: " + playlist.get(8));
}
Moving day: capacity 2 to 4, copied 2 songs
Moving day: capacity 4 to 8, copied 4 songs
Moving day: capacity 8 to 16, copied 8 songs
Count: 9, capacity: 16
Index 8: Velvet Morning
class GrowingPlaylist:
def __init__(self):
self.slots = [None] * 2
self.count = 0
def capacity(self):
return len(self.slots)
def add(self, song):
if self.count == len(self.slots):
bigger = [None] * (len(self.slots) * 2)
for i in range(self.count):
bigger[i] = self.slots[i]
print(f"Moving day: capacity {len(self.slots)} to {len(bigger)}, copied {self.count} songs")
self.slots = bigger
self.slots[self.count] = song
self.count += 1
def get(self, index):
if index < 0 or index >= self.count:
raise IndexError(f"No song at index {index}")
return self.slots[index]
playlist = GrowingPlaylist()
for song in ["Midnight Bus", "Lemon Skies", "Slow Rain", "Paper Boats", "Neon Garden", "Quiet Harbor", "Sunday Static", "Golden Hour", "Velvet Morning"]:
playlist.add(song)
print(f"Count: {playlist.count}, capacity: {playlist.capacity()}")
print(f"Index 8: {playlist.get(8)}")
Moving day: capacity 2 to 4, copied 2 songs
Moving day: capacity 4 to 8, copied 4 songs
Moving day: capacity 8 to 16, copied 8 songs
Count: 9, capacity: 16
Index 8: Velvet Morning
class GrowingPlaylist {
slots = new Array(2);
count = 0;
get capacity() {
return this.slots.length;
}
add(song) {
if (this.count === this.slots.length) {
const bigger = new Array(this.slots.length * 2);
for (let i = 0; i < this.count; i++) {
bigger[i] = this.slots[i];
}
console.log(`Moving day: capacity ${this.slots.length} to ${bigger.length}, copied ${this.count} songs`);
this.slots = bigger;
}
this.slots[this.count] = song;
this.count++;
}
get(index) {
if (index < 0 || index >= this.count) {
throw new RangeError(`No song at index ${index}`);
}
return this.slots[index];
}
}
const playlist = new GrowingPlaylist();
for (const song of ["Midnight Bus", "Lemon Skies", "Slow Rain", "Paper Boats", "Neon Garden", "Quiet Harbor", "Sunday Static", "Golden Hour", "Velvet Morning"]) {
playlist.add(song);
}
console.log(`Count: ${playlist.count}, capacity: ${playlist.capacity}`);
console.log(`Index 8: ${playlist.get(8)}`);
Moving day: capacity 2 to 4, copied 2 songs
Moving day: capacity 4 to 8, copied 4 songs
Moving day: capacity 8 to 16, copied 8 songs
Count: 9, capacity: 16
Index 8: Velvet Morning
class GrowingPlaylist {
private slots: string[] = new Array<string>(2);
count = 0;
get capacity(): number {
return this.slots.length;
}
add(song: string): void {
if (this.count === this.slots.length) {
const bigger = new Array<string>(this.slots.length * 2);
for (let i = 0; i < this.count; i++) {
bigger[i] = this.slots[i];
}
console.log(`Moving day: capacity ${this.slots.length} to ${bigger.length}, copied ${this.count} songs`);
this.slots = bigger;
}
this.slots[this.count] = song;
this.count++;
}
get(index: number): string {
if (index < 0 || index >= this.count) {
throw new RangeError(`No song at index ${index}`);
}
return this.slots[index];
}
}
const playlist = new GrowingPlaylist();
for (const song of ["Midnight Bus", "Lemon Skies", "Slow Rain", "Paper Boats", "Neon Garden", "Quiet Harbor", "Sunday Static", "Golden Hour", "Velvet Morning"]) {
playlist.add(song);
}
console.log(`Count: ${playlist.count}, capacity: ${playlist.capacity}`);
console.log(`Index 8: ${playlist.get(8)}`);
Moving day: capacity 2 to 4, copied 2 songs
Moving day: capacity 4 to 8, copied 4 songs
Moving day: capacity 8 to 16, copied 8 songs
Count: 9, capacity: 16
Index 8: Velvet Morning
In Python and JavaScript, [None] * 2 and new Array(2) make a list of two empty slots, and the class uses it as a plain fixed-size array: it never calls append or push, which would let the language do the growing for us. get refuses an index past the count, even when the slot exists, because a spare slot isn't a song.

Try it. Add six more songs to the list so there are 15, and run it again. How many moving days are there now? Then add a 17th song and predict the new line before you run it.
What it costs, and when something else wins
- Adding with a spare slot: O(1). One write, nobody moves.
- Moving day: O(n). Every item is copied, so twice the songs means twice the copying. But it's rare, and the next lesson, Is Adding a Song Slow? Amortized Cost, counts exactly how rare.
- Reading or changing by index: O(1), as in a plain array: the items still sit side by side.
- Inserting or removing in the middle: O(n), as in a plain array: everyone after the spot scoots over.
A growing array isn't always the best choice. If you know the exact size up front (the 12 months of a year, the 64 squares of a chessboard), a plain array is simpler and never moves. If you know roughly how many items are coming, you can ask your language's list for that capacity at the start and skip the moving days; Why Does This Loop Take Seconds? Your Language's List shows how. And if the job keeps adding at the front, doubling doesn't help at all: every song still scoots over. That's the next chapter.
The growing array's cost card
| Operation | Big-O | Why, in everyday words |
|---|---|---|
| Read or change the item at an index | O(1) | Still a row of mailboxes: go straight to the number |
| Add at the end | O(1) on average | Usually a spare room is waiting; moving day is rare (next lesson) |
| Add at the end on moving day | O(n) | Every box is carried to the new apartment |
| Insert or remove at the front or in the middle | O(n) | Everyone after the spot scoots over |
| Find an item by its value | O(n) | Look through the rooms one by one |
Check yourself
2 questions to try on the lesson page.
So what
Every time you call Add, add, append or push, this is what happens inside. Now you know why your list can keep growing, why it's still fast to read by index, and why it doubles instead of adding a few slots: a fixed step turns a million adds into billions of copies.