Module assignment: Playlist toolkit in Python

What you will build

A music app keeps its playlist as a linked list, in the order the songs were added. This assignment asks you to build the core of that playlist as a command program. The program reads commands from the Input box, one per line, and it changes the playlist and prints results. Every operation in this assignment is one of the operations from lessons 1 to 4, so you will not need any new idea. What is new is putting them together, handling every command, and keeping the list correct after many changes.

The assignment is worth doing in order. The checkpoints below give you a working program at two stages, so you can check your progress before the last commands. Read the whole spec first, then build the checkpoints, then add the rest.

The spec

The program reads commands until it sees the word end or runs out of input. Each command is one word, followed by an argument when the command needs one. Song titles are single words with no spaces, such as Intro or Chorus.

Read the whole input as words with sys.stdin.read().split(). The split() call breaks the text on any run of spaces or line breaks, so the line breaks do not matter.

Command	Argument	What it does	What it prints
`add`	a title	Adds the song at the end of the playlist.	Nothing
`remove`	a title	Removes every song with that title.	Nothing
`reverse`	none	Reverses the order of the songs.	Nothing
`show`	none	Lists the songs in order.	The titles joined by `\|`, or `EMPTY`
`middle`	none	Finds the middle song. For an even count, takes the second of the two middle songs.	The title, or `EMPTY`
`nth`	a number k, at least 1	Removes the k-th song counted from the end, where k = 1 is the last song.	`removed TITLE`, or `no such song` when k is larger than the playlist
`end`	none	Stops reading commands.	Nothing

The show output joins titles with a space, a vertical bar and a space. For example, Intro | Verse | Chorus has two separators. With one song, there are no separators. An empty playlist prints the single word EMPTY.

The middle command picks the song at the middle position. For a playlist of four songs, that is the third song, because the two middle songs are the second and third. This is the same choice lesson 3 made for the middle finder, and it is the one the examples use.

The nth command removes the song k places from the end. It must not change the playlist when the removal is impossible, and it prints no such song in that case. A removal of the last song is nth 1, and it can empty the playlist.

Sample input and output

The first sample uses most of the commands. Type it into the Input box exactly as written:

add Intro
add Verse
add Chorus
add Bridge
show
middle
remove Verse
reverse
show
nth 2
show
end

Your program must print these five lines:

Intro | Verse | Chorus | Bridge
Chorus
Bridge | Chorus | Intro
removed Chorus
Bridge | Intro

Trace the first few commands to check your model. After the four add commands the list is Intro, Verse, Chorus, Bridge. The show prints all four. The middle picks the second of the two middle songs, which is Chorus. The remove Verse takes out the second song, leaving Intro, Chorus, Bridge. The reverse turns it into Bridge, Chorus, Intro. The nth 2 counts two from the end, which is Chorus, so Chorus is removed, leaving Bridge, Intro.

The second sample checks the empty and the error cases. Type this into the Input box:

show
middle
nth 1
add Solo
nth 3
middle
show
end

Your program must print these six lines:

EMPTY
EMPTY
no such song
no such song
Solo
Solo

Notice the nth 1 on an empty list. There is no song to remove, and 1 is larger than the length of zero, so the program prints no such song and changes nothing. The nth 3 after add Solo is also too large, because the list has one song.

Checkpoint 1: add and show

Before you write the other commands, make add and show work. The starter below holds the skeleton. Fill in the TODO comments. The checkpoint that follows is one correct version of the first two commands, so you can compare your work with it after you try.

Start with this skeleton. Run it with an empty Input box. It prints nothing, which is correct until you add commands.

import sys
 
 
class Song:
    def __init__(self, title):
        self.title = title
        self.next = None
 
 
class Playlist:
    def __init__(self):
        self.head = None
        self.tail = None
 
    # TODO: def add(self, title) appends a song at the end
    # TODO: def show(self) returns the titles joined by " | ", or "EMPTY"
    # TODO: def remove(self, title), def reverse(self), def middle(self), def remove_from_end(self, k)
 
 
def main():
    words = iter(sys.stdin.read().split())
    playlist = Playlist()
    for command in words:
        if command == "end":
            break
        # TODO: handle add, show, remove, reverse, middle and nth
 
 
if __name__ == "__main__":
    main()

When you have the skeleton, type this into the Input box to check the first two commands. The program after it is a complete version that works for add and show, and it is a fair model for your own version of those two methods:

add Intro
add Verse
add Chorus
show
add Outro
show
end

import sys
 
 
class Song:
    def __init__(self, title):
        self.title = title
        self.next = None
 
 
class Playlist:
    def __init__(self):
        self.head = None
        self.tail = None
 
    def add(self, title):
        song = Song(title)
        if self.head is None:
            self.head = self.tail = song
        else:
            self.tail.next = song
            self.tail = song
 
    def show(self):
        if self.head is None:
            return "EMPTY"
        titles = []
        cur = self.head
        while cur is not None:
            titles.append(cur.title)
            cur = cur.next
        return " | ".join(titles)
 
 
def main():
    words = iter(sys.stdin.read().split())
    playlist = Playlist()
    for command in words:
        if command == "end":
            break
        if command == "add":
            playlist.add(next(words))
        elif command == "show":
            print(playlist.show())
 
 
if __name__ == "__main__":
    main()

Output for the input above:

Intro | Verse | Chorus
Intro | Verse | Chorus | Outro

Look at add closely. The first song sets both head and tail. The line self.head = self.tail = song does this in one step, so both names point at the same song. Every later song is linked after tail, and then tail moves to it. This is the same tail pattern as lesson 2, and it makes add take the same time whatever the length of the list. Without the tail reference, every add would walk from the head, which is correct but slower.

The words value is an iterator. It hands out one word each time next(words) is called. The for loop takes the command word, and next(words) takes the argument that follows it. The last two lines run main only when you start the file directly. That check is the usual pattern for a Python program that has a main function.

Checkpoint 2: remove and reverse

The next two commands change the order and the membership of the list, and they are where most bugs appear. This checkpoint adds remove and reverse to the program from checkpoint 1. The remove method removes every match, so it uses the same loop as lesson 4, with a dummy node in front of the head. The reverse method uses the three-reference loop from lesson 3.

Type this into the Input box. It adds four songs, two of them named A, removes every A, then reverses the rest:

add A
add B
add A
add C
remove A
show
reverse
show
end

Your program must print these two lines:

B | C
C | B

The complete checkpoint code is below. Read the two new methods first, because they are the heart of the assignment. Then run the program with the input above.

import sys
 
 
class Song:
    def __init__(self, title):
        self.title = title
        self.next = None
 
 
class Playlist:
    def __init__(self):
        self.head = None
        self.tail = None
 
    def add(self, title):
        song = Song(title)
        if self.head is None:
            self.head = self.tail = song
        else:
            self.tail.next = song
            self.tail = song
 
    def remove(self, title):
        dummy = Song("")
        dummy.next = self.head
        cur = dummy
        while cur.next is not None:
            if cur.next.title == title:
                cur.next = cur.next.next  # stay on cur: the next node may match too
            else:
                cur = cur.next
        self.head = dummy.next
        self.tail = self.head
        if self.tail is not None:
            while self.tail.next is not None:
                self.tail = self.tail.next  # keep tail on the last song
 
    def reverse(self):
        prev = None
        cur = self.head
        while cur is not None:
            next_song = cur.next
            cur.next = prev
            prev = cur
            cur = next_song
        self.head = prev
        self.tail = self.head
        if self.tail is not None:
            while self.tail.next is not None:
                self.tail = self.tail.next
 
    def show(self):
        if self.head is None:
            return "EMPTY"
        titles = []
        cur = self.head
        while cur is not None:
            titles.append(cur.title)
            cur = cur.next
        return " | ".join(titles)
 
 
def main():
    words = iter(sys.stdin.read().split())
    playlist = Playlist()
    for command in words:
        if command == "end":
            break
        if command == "add":
            playlist.add(next(words))
        elif command == "remove":
            playlist.remove(next(words))
        elif command == "reverse":
            playlist.reverse()
        elif command == "show":
            print(playlist.show())
 
 
if __name__ == "__main__":
    main()

Two details in this code are worth checking. The remove method compares titles with ==. In Python, == compares the text of two strings, which is what the spec asks for. is asks whether two names point at the same object, which is a different question. Module 11 covers why. The tail line after each change is the one that most people forget. If tail still points at a removed song, the next add links the new song to a song that is no longer in the list, and the new song disappears from show.

Requirements checklist

Use this list to check your finished program. Each item is something a grader will test.

Grading rubric

A grader checks the program with the two samples above and with several hidden inputs. Your mark depends on which commands are correct.

60 percent. add, show, remove and end work. The two samples pass for the lines that involve those commands. reverse, middle and nth may be missing or may print wrong results. The program does not crash on the samples.

80 percent. All of the 60 percent items, plus reverse and middle are correct, including the EMPTY cases. The nth command removes a song from the middle of the list and from the head, when k equals the length. The tail reference stays correct after each command that changes the list.

100 percent. All commands are correct, including nth with k larger than the playlist, and the no such song message. The program passes every hidden input, including long lists of several hundred songs, repeated titles and a removal that empties the playlist. The code is clean: each method has one job, the loops have clear end conditions, and the program never reads past the end of the input.

A common reason for a lower mark is a crash on an edge case. A program that is correct on the samples but fails on an empty list has not reached 100 percent, even if the output looks right for most inputs. For example, a middle method with no check for an empty list fails with AttributeError: 'NoneType' object has no attribute 'title' when the playlist is empty. Test the empty list before you submit.

Step-by-step hints

Read one hint at a time. Each one is a small step, not the full answer.

Hint 1: the skeleton

Write add and show first, using the checkpoint 1 code as a pattern. Run the program with the first two lines of sample 1 before you write anything else. If show prints the right titles, the list structure is working.

Hint 2: removing every match

Use a dummy node in front of the head, the same as the dummy node in lesson 4. Walk with cur, and remove a match by setting cur.next = cur.next.next. Do not move cur after a removal. At the end, set self.head = dummy.next, then rebuild self.tail by walking to the last song.

Hint 3: reversing

Use the three-reference loop from lesson 3, with prev, cur and a saved next_song. The method sets self.head to prev, because prev is the new first song. Do not forget to move self.tail to the new last song, which is the old head.

Hint 4: the middle command

Use the slow and fast pointers from lesson 3. The loop stops with slow on the second of the two middle songs for an even count. Return slow.title. Check the empty list before the loop, because fast.next on None would fail.

Hint 5: removing from the end

Count the songs first, with a simple walk, and call the count n. If k is larger than n, return None and let the caller print no such song. Otherwise use the fixed gap from lesson 4: move fast k steps from the dummy, move both pointers until fast.next is None, then skip slow.next. Read the removed title before you skip it, because after the skip the title is gone.

Hint 6: the tail after removals

Each time the list changes, rebuild self.tail with a short walk to the last song, or update it where you know the answer. A removal of the last song is the case that goes wrong most often. If your add after an nth seems to vanish, print playlist.tail.title and check it against the last title in show.

Reference solution

Try the whole assignment yourself before you read this. The reference below passes both samples, and it is one good answer, not the only one. Check your code against it only after your own version runs.

It is a complete program, so the Input box is the only thing you change. It adds three helper methods to the checkpoint code: fix_tail rebuilds tail with one walk, size counts the songs, and remove_from_end does the nth command. Python has no built-in length for a linked list, because len only works on objects that define a length. So size walks the list.

import sys
 
 
class Song:
    def __init__(self, title):
        self.title = title
        self.next = None
 
 
class Playlist:
    def __init__(self):
        self.head = None
        self.tail = None
 
    def add(self, title):
        song = Song(title)
        if self.head is None:
            self.head = self.tail = song
        else:
            self.tail.next = song
            self.tail = song
 
    def fix_tail(self):
        self.tail = self.head
        if self.tail is None:
            return
        while self.tail.next is not None:
            self.tail = self.tail.next
 
    def size(self):
        n = 0
        cur = self.head
        while cur is not None:
            n += 1
            cur = cur.next
        return n
 
    def remove(self, title):
        dummy = Song("")
        dummy.next = self.head
        cur = dummy
        while cur.next is not None:
            if cur.next.title == title:
                cur.next = cur.next.next
            else:
                cur = cur.next
        self.head = dummy.next
        self.fix_tail()
 
    def reverse(self):
        prev = None
        cur = self.head
        while cur is not None:
            next_song = cur.next
            cur.next = prev
            prev = cur
            cur = next_song
        self.head = prev
        self.fix_tail()
 
    def show(self):
        if self.head is None:
            return "EMPTY"
        titles = []
        cur = self.head
        while cur is not None:
            titles.append(cur.title)
            cur = cur.next
        return " | ".join(titles)
 
    def middle(self):
        if self.head is None:
            return "EMPTY"
        slow = self.head
        fast = self.head
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
        return slow.title
 
    def remove_from_end(self, k):
        n = self.size()
        if k < 1 or k > n:
            return None
        dummy = Song("")
        dummy.next = self.head
        slow = dummy
        fast = dummy
        for _ in range(k):
            fast = fast.next
        while fast.next is not None:
            slow = slow.next
            fast = fast.next
        removed = slow.next.title
        slow.next = slow.next.next
        self.head = dummy.next
        self.fix_tail()
        return removed
 
 
def main():
    words = iter(sys.stdin.read().split())
    playlist = Playlist()
    for command in words:
        if command == "end":
            break
        if command == "add":
            playlist.add(next(words))
        elif command == "remove":
            playlist.remove(next(words))
        elif command == "reverse":
            playlist.reverse()
        elif command == "middle":
            print(playlist.middle())
        elif command == "nth":
            removed = playlist.remove_from_end(int(next(words)))
            print("no such song" if removed is None else f"removed {removed}")
        elif command == "show":
            print(playlist.show())
 
 
if __name__ == "__main__":
    main()

Run it with the first sample. It prints the five lines from the sample section. With the second sample it prints the six lines for that sample.

Going further

When the assignment works, try two extensions. The first is to make remove take a second argument, the number of songs to remove, so it removes only the first matches. The second is to store the playlist in a doubly linked list, so that nth can walk from the end without a separate size count. Both extensions reuse ideas from lessons 2 and 4, and they show how the same problem can be solved with different structures.

Module summary

A singly linked list is a chain of nodes, each with a value and a next link. Walk it from the head, and save next before you overwrite it.
A doubly linked list adds prev, which allows removal of a known node in constant time. A circular list links the last node back to the first. Walking it needs a loop that runs once before its stop check, which in Python is while True with a break.
Reverse the list by flipping next links with three references, and return prev. The middle comes from the slow and fast pointers, and a cycle is found with the same pair, with a second phase to find its start.
A dummy node in front of the head removes the special case for the first node, and you return dummy.next.
Merge two sorted lists by taking the smaller front node each time, and find the nth node from the end with a fixed gap between two pointers.