Arrays and Growing Arrays

Mailboxes side by side: why reading any spot in an array is instant and inserting in the middle isn't, then build a growing array and see what your language's list does when it's full.

Updated

Arrays

  1. Jump to Song 500: Arrays (Apprentice): 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.

Growing Arrays

  1. The Ninth Song Won't Fit: Growing Arrays (Apprentice): 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.
  2. Is Adding a Song Slow? Amortized Cost (Journeyman): One add to a growing playlist just copied 1,024 songs. Work out what adding really costs over a long run of adds, why doubling beats growing a little at a time, and what "amortized O(1)" promises.
  3. Why Does This Loop Take Seconds? Your Language's List (Apprentice): 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.

Exercise: Build a Growing Array

  1. Exercise: Build a Growing Array (Apprentice): The music app crashes on the 9th song of an 8-slot playlist: build a playlist that takes any number of songs, adds a million in under 2 seconds and opens any song at once, with tests on every edge, and name each method's Big-O.