Arrays & the Playlist
A playlist is the most ordinary thing in Tunebox: tracks in order, numbered from the
top. Python's list is a dynamic array, and that one fact decides which playlist
actions are instant and which quietly touch every track — like dragging track 5,000
to the top.
One block of memory
An array keeps its items in contiguous slots: one unbroken block, every slot the
same size. To reach slot i the computer doesn't search — it calculates:
address of slot i = address of slot 0 + i × slot size
slot: 0 1 2 3
┌─────────┬─────────┬─────────┬─────────┐
│ "Glow" │ "Tide" │ "Ember" │ "Drift" │
└─────────┴─────────┴─────────┴─────────┘One multiplication and one addition, whether the playlist has 4 tracks or 4 million. That's why indexing is O(1).
❓ Cross-question — "A list can hold
[1, "Glow", 4.5]. How can every slot be the same size?" The slots don't hold the objects — they hold references to objects living elsewhere, and every reference is the same size. In Java terms, a Python list is anArrayList<Object>.
playlist = ["Glow", "Tide", "Ember"]
print(playlist[len(playlist)])Dynamic arrays: length vs capacity
A raw array's size is fixed when it's created. A dynamic array hides that by
tracking two numbers: its length (tracks you have) and its capacity (slots it
reserved). append fills a spare slot — O(1). When no spare is left it allocates a
bigger block, copies every reference across — O(n) — and carries on.
Most appends print nothing — they landed in a spare slot. Because each new block is a fixed proportion bigger than the last, the copies across n appends add up to O(n), so each append is amortized O(1). (Byte counts vary by platform; the rhythm doesn't.)
Inserting or deleting in the middle is O(n)
Slots can't have gaps. To put a track at index 1, everything from index 1 onward must first shift one slot right — starting from the back, so nothing is overwritten before it has moved:
Deleting is the mirror image: everything after the gap shifts left. Near the end
that's a move or two; at the front it's all n. So insert(0, x), pop(0) and
del playlist[0] are O(n), while append(x) and pop() at the end move nothing.
Shift in the wrong direction and one track gets copied over the rest:
This should open a gap at index 1 for "Echo". Instead "Tide" is copied into every later slot and "Ember" is lost.
Slicing copies
playlist[a:b] builds a new list of those references — O(b − a). Convenient and
safe, but a slice inside a loop is a hidden O(n):
playlist = ["Glow", "Tide", "Ember"]
top = playlist[:2]
top.append("Drift")
print(len(playlist))Watch out:
playlist[:]andlist(playlist)are the idiomatic full copies, and both are shallow — the new list points at the same objects. Harmless for strings; for track dicts it means both lists share them.
In-place algorithms
An in-place algorithm rearranges the array it was given instead of building a new one — at its best, with O(1) extra memory. Python offers both styles, and the names tell you which:
In place saves memory, but the caller's list changes under them. Tunebox's rule: a function that returns a playlist leaves its argument alone.
Coming from Java/JS: JS
arr.sort()sorts in place and returns the array; Python'slist.sort()returnsNoneprecisely so nobody mistakes it for a copy. JS's copyingtoSorted()/toReversed()are Python'ssorted()and[::-1].
Rotation
"Shuffle the queue round by 2" is a rotation: the last k tracks wrap around to the front, in order. With slices it's one line — O(n) time and O(n) new memory:
Prefix sums — range totals in O(1)
"How long are tracks 1 to 3?" Summing that slice is O(k), and Tunebox asks thousands
of these questions. Pay O(n) once to build a prefix-sum array, where prefix[i]
is the total of the first i tracks, and every range total becomes one subtraction:
prefix = [0, 4, 7, 12, 14, 20] # built from mins = [4, 3, 5, 2, 6]
print(prefix[5] - prefix[2])Complexity at a glance
| operation | cost |
|---|---|
a[i], a[i] = x, len(a) |
O(1) |
a.append(x) |
O(1) amortized |
a.pop() |
O(1) |
a.insert(i, x), a.pop(i), del a[i] |
O(n − i) — O(n) at the front |
a[i:j] (a copy) |
O(j − i) |
x in a, a.index(x) |
O(n) |
a.reverse() / a.sort() in place |
O(n) / O(n log n) |
| prefix sums: build / each range total | O(n) / O(1) |
Idioms & real-world patterns
Slice assignment — replace a stretch in one move
A slice on the left of = replaces that stretch, and the list shifts whatever is
after it. del takes a slice too:
accumulate — prefix sums without the loop
⚡ Advanced — rotate in place with three reversals
Slice rotation builds a new list. To rotate using O(1) extra memory, reverse the whole array, then reverse each of the two parts back:
That reverse helper — one index from each end, walking inward — is the two-pointer
technique, and it's the whole of the next lesson.
⚡ Advanced — packed arrays with array
A list stores references, each pointing at a full Python object. When every item is
the same primitive — millions of play counts — the array module stores the raw
numbers directly in the block, with no objects behind them:
🎯 Your turn
Build the playlist's drag-to-reorder: move_track(playlist, i, j) moves the track at
index i so it ends up at index j, and returns the new playlist. The original list
must not change.
move_track(["a", "b", "c", "d"], 0, 2)→["b", "c", "a", "d"]move_track(["a", "b", "c"], 2, 0)→["c", "a", "b"]
Hint — copy with list(playlist), pop(i) the track out, then insert(j, …) it back.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Tunebox is built. ✅