# 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 November 17, 2026

By Gregor Dzierzon

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:
>
> 1. **Next and Previous** move one song along, and stop at the ends.
> 2. **Play next** puts a song right after the one playing, and the one playing keeps playing.
> 3. **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.
> 4. **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](https://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:

```bash
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 `SongNode` class and a `Playlist` class with four methods to finish (the repository's `README.md` names 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):

```python
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
```

1. **Next and previous.** Finish `next` and `previous` (`Next` and `Previous` in C#). Each moves one song along a reference, or stays put at the end and returns false.
2. **Play next.** Finish `addAfterCurrent` (`add_after_current` in 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.
3. **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.
4. **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.

&lt;details>
&lt;summary>Stuck?&lt;/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's `prev` has to match. The tests walk the playlist backward with `titlesBackward`, so a forgotten `prev` shows 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 `prev` is the head; a node with no `next` is 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 `previous` that walks from the first song to find the one before is the usual one: the `prev` reference is right there.

&lt;/details>

## When you're done

Every test is green, and the demo prints the same nine lines in every language:

```text
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?

&lt;details>
&lt;summary>Why Should I Choose This?&lt;/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.

&lt;/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.

&lt;details>
&lt;summary>Some answers&lt;/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.

&lt;/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.

1. 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.
2. 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:

   ```bash
   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 main
   ```

3. Paste 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.

## Key terms

- [Linked List](https://www.ask-codey.com/glossary/linked-list)
- [Doubly Linked List](https://www.ask-codey.com/glossary/doubly-linked-list)
- [Node](https://www.ask-codey.com/glossary/node-data-structures)
- [Head and Tail](https://www.ask-codey.com/glossary/head-and-tail-data-structures)

## Related

- ["Play Next" Without Moving Everyone: Linked Lists](https://www.ask-codey.com/lessons/ds-linked-lists)
- [Reaching the Last Song, and Going Back One: Doubly Linked Lists](https://www.ask-codey.com/lessons/ds-linked-list-operations)
- [Arrays vs Linked Lists](https://www.ask-codey.com/lessons/ds-arrays-vs-linked-lists)

Source: https://www.ask-codey.com/lessons/exercise-ds-linked-playlist
