Why Does This Loop Take Seconds? Your Language's List
A loop over 100,000 orders takes seconds, and one call in it is why. Meet your language's list, the growing array under five names, and read its cost card before you pick a method.
Apprentice · Data Structures · Updated
After this lesson you can
- Name your language's growing array and use it to add, read, insert and remove
- Give the Big-O of each operation on your language's list
Key takeaways
- C#'s List<T>, Java's ArrayList, Python's list and JavaScript's and TypeScript's Array are all growing arrays.
- Adding at the end and reading by index are fast: amortized O(1) and O(1).
- Inserting or removing at the front or in the middle, and searching by value, are O(n).
- Removing from the front over and over is a hidden O(n²); a queue is the structure for that job.
- Asking for the capacity up front skips the moving days, but doesn't change any Big-O.
Before this: The Ninth Song Won't Fit: Growing Arrays and Is Adding a Song Slow? Amortized Cost, where you built the structure inside your language's list.
A teammate's change to the coffee shop's order screen is up for review. It keeps the morning's orders in a list, and serves them by taking the first order off the list, again and again, until the list is empty. In testing, with 100 orders, it was instant. With a busy day's 100,000 orders it takes seconds, and the reviewer asks why. Nothing in the loop looks expensive: one call per order, and every language's list has that call.
The answer is in which call, and you can read it off the list's cost card once you know what the list is. You'll rarely build a growing array yourself at work: every language ships one, and it's the collection you'll reach for most often, for the songs in a playlist, the items in a cart or the rows from a database. What you will do every day is decide which of its operations to call. This lesson puts names to the structure you built, gives you its cost card in your language, and then comes back to the slow loop.
One structure, five names
| Language | The growing array | Add at the end | Read | Insert at | Remove at | How many |
|---|---|---|---|---|---|---|
| C# | List<T> |
Add(x) |
list[i] |
Insert(i, x) |
RemoveAt(i) |
Count |
| Java | ArrayList<T> |
add(x) |
get(i) |
add(i, x) |
remove(i) |
size() |
| Python | list |
append(x) |
items[i] |
insert(i, x) |
pop(i) |
len(items) |
| JavaScript, TypeScript | Array |
push(x) |
items[i] |
splice(i, 0, x) |
splice(i, 1) |
length |
Inside each of them is a plain array with spare slots, a count and a capacity, and a moving day when it fills: exactly what you built. The T in List<T> and ArrayList<T> is the type of item it holds, as Generics: a Box for Any Type showed.

The playlist, with your language's list
The same steps in each language: add three songs, insert one at the front, read one by index, remove one from the middle, and check for a title.
List<string> playlist = new List<string>();
playlist.Add("Midnight Bus");
playlist.Add("Lemon Skies");
playlist.Add("Slow Rain");
Console.WriteLine("After adding: " + string.Join(", ", playlist));
playlist.Insert(0, "Paper Boats");
Console.WriteLine("After inserting at 0: " + string.Join(", ", playlist));
Console.WriteLine("Index 2: " + playlist[2]);
string removed = playlist[1];
playlist.RemoveAt(1);
Console.WriteLine("Removed index 1: " + removed);
Console.WriteLine("Has Slow Rain: " + (playlist.Contains("Slow Rain") ? "yes" : "no"));
Console.WriteLine("Count: " + playlist.Count);
After adding: Midnight Bus, Lemon Skies, Slow Rain
After inserting at 0: Paper Boats, Midnight Bus, Lemon Skies, Slow Rain
Index 2: Lemon Skies
Removed index 1: Midnight Bus
Has Slow Rain: yes
Count: 3
void main() {
ArrayList<String> playlist = new ArrayList<>();
playlist.add("Midnight Bus");
playlist.add("Lemon Skies");
playlist.add("Slow Rain");
IO.println("After adding: " + String.join(", ", playlist));
playlist.add(0, "Paper Boats");
IO.println("After inserting at 0: " + String.join(", ", playlist));
IO.println("Index 2: " + playlist.get(2));
String removed = playlist.remove(1);
IO.println("Removed index 1: " + removed);
IO.println("Has Slow Rain: " + (playlist.contains("Slow Rain") ? "yes" : "no"));
IO.println("Count: " + playlist.size());
}
After adding: Midnight Bus, Lemon Skies, Slow Rain
After inserting at 0: Paper Boats, Midnight Bus, Lemon Skies, Slow Rain
Index 2: Lemon Skies
Removed index 1: Midnight Bus
Has Slow Rain: yes
Count: 3
playlist = []
playlist.append("Midnight Bus")
playlist.append("Lemon Skies")
playlist.append("Slow Rain")
print("After adding: " + ", ".join(playlist))
playlist.insert(0, "Paper Boats")
print("After inserting at 0: " + ", ".join(playlist))
print(f"Index 2: {playlist[2]}")
removed = playlist.pop(1)
print(f"Removed index 1: {removed}")
print("Has Slow Rain: " + ("yes" if "Slow Rain" in playlist else "no"))
print(f"Count: {len(playlist)}")
After adding: Midnight Bus, Lemon Skies, Slow Rain
After inserting at 0: Paper Boats, Midnight Bus, Lemon Skies, Slow Rain
Index 2: Lemon Skies
Removed index 1: Midnight Bus
Has Slow Rain: yes
Count: 3
const playlist = [];
playlist.push("Midnight Bus");
playlist.push("Lemon Skies");
playlist.push("Slow Rain");
console.log(`After adding: ${playlist.join(", ")}`);
playlist.splice(0, 0, "Paper Boats");
console.log(`After inserting at 0: ${playlist.join(", ")}`);
console.log(`Index 2: ${playlist[2]}`);
const removed = playlist.splice(1, 1)[0];
console.log(`Removed index 1: ${removed}`);
console.log(`Has Slow Rain: ${playlist.includes("Slow Rain") ? "yes" : "no"}`);
console.log(`Count: ${playlist.length}`);
After adding: Midnight Bus, Lemon Skies, Slow Rain
After inserting at 0: Paper Boats, Midnight Bus, Lemon Skies, Slow Rain
Index 2: Lemon Skies
Removed index 1: Midnight Bus
Has Slow Rain: yes
Count: 3
const playlist: string[] = [];
playlist.push("Midnight Bus");
playlist.push("Lemon Skies");
playlist.push("Slow Rain");
console.log(`After adding: ${playlist.join(", ")}`);
playlist.splice(0, 0, "Paper Boats");
console.log(`After inserting at 0: ${playlist.join(", ")}`);
console.log(`Index 2: ${playlist[2]}`);
const removed = playlist.splice(1, 1)[0];
console.log(`Removed index 1: ${removed}`);
console.log(`Has Slow Rain: ${playlist.includes("Slow Rain") ? "yes" : "no"}`);
console.log(`Count: ${playlist.length}`);
After adding: Midnight Bus, Lemon Skies, Slow Rain
After inserting at 0: Paper Boats, Midnight Bus, Lemon Skies, Slow Rain
Index 2: Lemon Skies
Removed index 1: Midnight Bus
Has Slow Rain: yes
Count: 3
The method names differ, and a few small things do too: C#'s RemoveAt doesn't hand back the item it removed, so the code reads it first, while Java's remove(i), Python's pop(i) and JavaScript's splice do. JavaScript has no insert method: splice(i, 0, x) means "at index i, remove 0 items and put x in".
Setting the capacity up front
When you know how many items are coming, you can skip the moving days by asking for the capacity at the start: new List<string>(10000) in C# and new ArrayList<>(10000) in Java make room for 10,000 items before the first add. C#'s list also tells you its capacity (playlist.Capacity); Java, Python and JavaScript keep theirs hidden and manage it for you. It's a small speed-up, not a change in Big-O: adding at the end is O(1) either way.
The list's cost card
| Operation | Big-O | Why, in everyday words |
|---|---|---|
| Read or change by index | O(1) | Go straight to the mailbox by its number |
| Add at the end | O(1) amortized | A spare slot is usually waiting; moving day is rare |
| Remove from the end | O(1) | Nobody has to move |
| Insert or remove at the front or in the middle | O(n) | Everyone after the spot scoots over |
| Contains, or find the index of a value | O(n) | Read the titles one by one |
| How many items | O(1) | The list keeps the count as it goes |
Back to the slow loop
Now read the teammate's loop against the cost card. Removing the first item of a list is O(n): everyone behind it scoots forward one slot. Doing that until the list is empty is O(n) work done n times: O(n²), the handshakes again. For 100,000 orders that's close to 5 billion moves (99,999 + 99,998 + … + 1), and that's where the seconds go. With 100 orders it was about 5,000 moves, too few to notice, which is why the bug got through testing.
Inserting at the front over and over has the same cost. When the job is "first in, first served", the right structure takes from the front in O(1): you'll build one in First Come, First Served at Rush Hour: Queues.
Try it. In your language, insert 5 more songs at index 0 one after another, then print the list. Which song is first? How many songs scooted over in all?
Check yourself
2 questions to try on the lesson page.
So what
You now know what's inside the collection you'll use most, and which of its calls are cheap and which quietly move everything. Reading that cost card before you pick a method is a habit that keeps apps fast as they grow.