Exercise: A Playlist You Can Walk
"Play next" lags on long up-next queues, and Previous must be instant: build a music player's playlist where next, previous, play next and remove each take the same moment at any length, with the tests checking every end and a 200,000-song run, and name each method's Big-O.
Apprentice · Data Structures · Updated
Here's the ticket from the music app's player team:
Our up-next queue is a list, and "Play next" puts the song at its index after the current one. On long queues it lags: at 100,000 songs, every tap moves tens of thousands of songs to make room. The new playlist keeps a song "now playing", and:
- Next and Previous move one song along, and stop at the ends.
- Play next puts a song right after the one playing, and the one playing keeps playing.
- Remove takes the song playing out of the playlist; the song after it plays next, or the one before it if it was the last.
- Every button takes the same moment on a 4-song playlist or a 200,000-song one. Previous included: nobody waits while the app looks for the song before.
You've met every piece of this in the chapter, and now you build the player's four buttons. The tests check every end of the playlist (the first song, the last song, an empty playlist), then run a long up-next queue against the clock.
Before you start
You need one language set up, as in Setup: VS Code and Your Language. The exercise is written in all five of the course's languages; pick the one you use.
Get the exercise code
Open this lesson's GitHub repository, github.com/ask-codey/exercise-ds-linked-playlist, also linked from the Exercise box beside the lesson. Clone it into your course folder. In a terminal, in that folder:
git clone https://github.com/ask-codey/exercise-ds-linked-playlist.git
Git makes a folder, exercise-ds-linked-playlist, with the exercise code inside.
The repository has a folder for each language: csharp, java, python, javascript and typescript. Each folder holds:
- your code: one file with a
SongNodeclass and aPlaylistclass with four methods to finish (the repository'sREADME.mdnames the file for each language); - the tests that check your methods. You don't need to change them;
- a demo program that walks a four-song playlist.
In VS Code, choose File > Open Folder and open your language's folder, not the whole repository.
What to do
Each SongNode holds a title and two references, prev and next, to the songs on either side. The Playlist keeps the first song, the last song and the song now playing, and it can already add a song at the end and list its titles forward (titles) and backward (titlesBackward). Read add first: it shows how a new song is linked both ways.
Your four methods are there with their parameters, and return false or nothing for now. The comment above each one says what it should do, with examples, and ends with a Big-O: line. Here is next in Python, as the starter has it (the other languages say the same in their own syntax):
class Playlist:
def __init__(self):
self._current = None
def next(self):
"""
Move to the song after the current one and return True. If the
current song is the last one, or the playlist is empty, stay where
you are and return False.
Midnight Bus (current), Lemon Skies: next() -> True, current is Lemon Skies
then next() -> False, current is still Lemon Skies
Big-O: (write it here)
"""
return False
- Next and previous. Finish
nextandprevious(NextandPreviousin C#). Each moves one song along a reference, or stays put at the end and returns false. - Play next. Finish
addAfterCurrent(add_after_currentin Python). Link the new song between the current song and the one after it, both ways. Adding after the last song moves the tail, and on an empty playlist the new song is the only song. - Remove. Finish
removeCurrent(remove_current). Link the songs on either side of the current one to each other, and return the title you took out. The song after it plays next; if there isn't one, the song before it does. - Name the costs. On each method's Big-O: line, write its Big-O and a few words on why.
Check your work
Each language has its own command, run in the terminal in your language's folder (Terminal > New Terminal in VS Code). The repository's README.md has the full list, including the one-time setup for Python (a virtual environment and pytest) and TypeScript (npm install).
| Language | Run the tests | Run the demo |
|---|---|---|
| C# | dotnet test |
dotnet run --project LinkedPlaylist |
| Java | ./mvnw test (.\mvnw test in PowerShell) |
java src/main/java/Demo.java |
| Python | python -m pytest |
python demo.py |
| JavaScript | npm test |
node demo.js |
| TypeScript | npm test |
node demo.ts |
At first all 9 tests fail. That's expected: each method you finish turns its tests green. A failing test's message starts with Not yet: and says what it expected, for example Not yet: Slow Rain's prev must skip back to Midnight Bus. The last test runs a long up-next queue (100,000 songs, 100,000 taps of Play next, a walk to the end and all the way back, and 100,000 removes) and stops once it passes 2 seconds.
<details> <summary>Stuck?</summary>
- Draw it first. Three boxes on paper with arrows both ways. Which arrows change when a song goes in after the first box? Which change when the middle box comes out? Write the code from the drawing.
- Every link goes both ways. Whenever you set a node's
next, ask which node'sprevhas to match. The tests walk the playlist backward withtitlesBackward, so a forgottenprevshows up there. - Order matters when you link a new node. Point the new node at its neighbors first, while you can still reach them, then point the neighbors at it.
- Check the ends. A node with no
previs the head; a node with nonextis the tail. Removing either one moves the head or the tail, and removing the only song empties all three references. - The long queue ran out of time? Look for a loop inside a button. A
previousthat walks from the first song to find the one before is the usual one: theprevreference is right there.
</details>
When you're done
Every test is green, and the demo prints the same nine lines in every language:
Playlist: Midnight Bus, Lemon Skies, Slow Rain, Paper Boats
Now playing: Midnight Bus
Next: Lemon Skies
Next: Slow Rain
Previous: Lemon Skies
Added after Lemon Skies: Golden Hour
Removed: Lemon Skies, now playing: Golden Hour
Playlist: Midnight Bus, Golden Hour, Slow Rain, Paper Boats
Backward: Paper Boats, Slow Rain, Golden Hour, Midnight Bus
Now look back at your four methods. Would any of them get slower on a playlist of 100,000 songs? How would removeCurrent have to change if the playlist were a growing array instead, and what would it cost?
<details> <summary>Why Should I Choose This?</summary>
The long-queue test taps Play next 100,000 times on a 100,000-song queue, with the song playing at position 50,000, then walks to the end and back.
- Today's list, with an insert after the song playing: every tap moves every song after it, 50,000 or more, about 10 billion moves for the test's taps. O(n) per tap.
- Songs that only know the song after them: Play next is quick, but Previous walks from the first song to find the one before. Walking back from song 200,000 that way is about 20 billion steps; on the test's clock it was stopped at 2 to 6 seconds in every language.
- Songs that know both neighbors: every button changes at most four references, O(1), and the whole test takes a fraction of a second (0.04 seconds in C#, Java and JavaScript, 0.2 in Python).
What it gives up: "jump to song 500" now walks 500 songs from the front, O(n), and every song carries two references. When the job is mostly jumping by number, the growing array wins.
</details>
Where else does this shape show up?
You've built "each thing knows its neighbors, so changing the line never moves anyone". Before you open the answers, think of three other places, in apps or in daily life, where things are kept in a line by each one knowing the next (or the one before), and things are added or taken out in the middle of it.
<details> <summary>Some answers</summary>
- A browser's tabs: close one, and the tabs on either side close the gap without anyone renumbering.
- A photo viewer's previous and next arrows, stepping through an album one picture at a time.
- A scavenger hunt, where each clue says where the next one is hidden.
- A conga line: someone joins behind a friend, and nobody else changes places.
- An editor's undo history can be one too, and the next chapter builds a structure for exactly that job.
</details>
Submit your exercise
The exercise is how you finish this lesson. When your work is done, put it on GitHub in a repo of your own, then submit that repo's address here.
On GitHub, click +, then New repository. Name it (for example
exercise-ds-linked-playlist), choose Public, and click Create repository. Leave out the README: your folder already has one.In a terminal in your exercise folder (Git Bash on Windows), send your work to your new repo. Point your copy at your own repo, then commit and push:
git remote set-url origin https://github.com/your-name/exercise-ds-linked-playlist.git git add . git commit -m "My solution" git push -u origin mainPaste your repo's address, such as
https://github.com/your-name/exercise-ds-linked-playlist, into Submit your exercise on this page. The site checks that the repo is public and holds your commits, and then the lesson is complete.
Changed something after you submitted? Push it, and submit again: your latest submission is the one that counts.
So what
You've built the structure behind every previous and next button, and handled the edge cases that trip up most linked-list code: the head, the tail and the empty list. Getting references right in both directions is the same skill trees and graphs ask for later in the course.