Module assignment: Playlist editor

What you will build

In this assignment you will write a small playlist editor in C++. A playlist is a list of track numbers, in the order they play. The editor reads commands from standard input, one per line, changes the playlist, and prints answers. The data structure is a doubly linked list, so every node knows both the track before it and the track after it.

The assignment uses every idea from this module. Insertion and removal change pointers in the right order, as in lesson 2. Reversal turns the links around, as in lesson 3. Finding the middle uses a slow and a fast pointer, also from lesson 3. Removing the track k places from the end uses a gap of pointers, from lesson 4. The doubly linked node and the backward print come from lesson 5. Memory must be freed exactly once, which is the rule from lesson 2 that you will check with a sanitizer.

You will not need to read any other module. Everything is in this page. Read the whole page once before you start, then work through the checklist in order.

The specification

The program reads an integer n first. That is the number of commands that follow. Each command is one line. The command name is the first word, and the rest of the line holds numbers separated by spaces. Read the commands with cin, and ignore any blank lines.

The playlist starts empty. Track values are integers. Values may repeat, because the same track can appear twice in a playlist. Positions are counted from 0 at the front, unless a command says otherwise.

Here is every command. Keep this table open while you write the program.

Command	What it does	What it prints
`add x`	Adds track x at the back.	Nothing.
`insert i x`	Puts track x at position i, so it becomes the track at index i.	`error index` if i is less than 0 or greater than the size. Otherwise nothing.
`remove x`	Removes the first track whose value is x.	`removed` if one was removed, otherwise `not found`.
`remove_end k`	Removes the track k places from the end. k equal to 1 means the last track.	`removed`, or `error index` if k is less than 1 or greater than the size.
`reverse`	Reverses the order of the playlist, in place.	Nothing.
`middle`	Prints the middle track. For an even size, print the second of the two middle tracks.	The value, or `empty` for an empty playlist.
`count x`	Counts how many tracks have value x.	The count.
`print`	Prints the playlist from front to back, separated by single spaces.	The values, or `(empty)`.
`back`	Prints the playlist from back to front, using the prev pointers.	The values, or `(empty)`.

Every output line ends with a newline. There must be no trailing space at the end of a print or back line.

Two examples

The first example uses most commands. Read it line by line, and check each output against the table before you look at the expected output below it.

15
add 10
add 20
add 30
print
insert 1 15
insert 9 99
print
remove 20
remove 77
back
middle
remove_end 2
print
reverse
print

Here is what the program should print, one line per printing command.

10 20 30
error index
10 15 20 30
removed
not found
30 15 10
15
removed
10 30
30 10

Trace a few steps. After three add commands the list is 10, 20, 30, and print shows it. insert 1 15 puts 15 at index 1, so the list is 10, 15, 20, 30. insert 9 99 asks for index 9 in a list of size 4. The valid indexes are 0 to 4, so the program prints error index and changes nothing. After remove 20 the list is 10, 15, 30. remove 77 finds nothing, so it prints not found. back walks the prev pointers from the tail: 30, 15, 10. middle on three tracks gives the middle one, 15. remove_end 2 removes the second track from the end, which is 15, so the list is 10, 30. reverse gives 30, 10.

The second example checks the empty and single-track cases, and repeated values.

7
middle
remove_end 1
back
add 4
add 4
count 4
middle

empty
error index
(empty)
2
4

On an empty playlist, middle prints empty. remove_end 1 is an error, because k is larger than the size of 0. back prints (empty). After two adds of 4, count 4 gives 2. For an even size of two, the second middle track is the second node, which is 4.

Requirements checklist

Work through this list in order. Tick each item only after you have tested it with a small input you wrote yourself.

How the marks are split

Your work is graded on behaviour, not on style. The rubric below describes what a 60%, an 80% and a 100% solution do. A solution that meets a level does everything in the levels below it.

A 60% solution reads all commands, and handles add, print, remove for a match and count. Its doubly linked nodes are set up, but its back command or its prev pointers may be wrong. It may leak memory. Its insert, remove_end, reverse and middle may be missing or incorrect for some inputs.

An 80% solution handles every command in the table. insert and remove_end give the correct tracks in every position, including the front, the back and the single-track list. reverse gives the same result as printing the playlist in reverse. middle gives the correct value for odd and even sizes. The error messages match the table exactly. Memory is freed in the destructor, but a sanitizer run may still show a problem in one edge case, such as after a remove that removes the head.

A 100% solution passes both samples and at least six extra tests that you write, covering the edge cases below. The program runs under the address sanitizer with no reports. The class cannot be copied. Each command uses the pointer order from lesson 2: save before you change, then free. The code is clear enough that a reader can check each command against the table.

The edge cases your own tests must cover are these. An empty list with every command. A single track with remove, remove_end 1, middle and reverse. Removal of the head, the tail and a middle track. insert at 0 and at the size. Two tracks with the same value. A list of even size for middle. A list of odd size for middle. A remove_end with k equal to the size, which removes the head.

Step-by-step hints

You can read each hint in turn. Try each step yourself first, and open the next hint only if you are stuck. The hints are hidden, so that the thinking stays with you.

Hint 1: the node and the class

Copy the DNode struct from lesson 5, with data, prev and next. Make a class named Playlist with head_, tail_ and size_. Start with only pushBack, print and the destructor. Compile it and test add with print before you add anything else. The destructor is simple: walk forward, save next, delete, move on.

Hint 2: pushBack and the empty list

Set the new node's prev to tail_. If tail_ is not null, set tail_->next to the new node. Otherwise, the list was empty, so set head_ to the new node. Then move tail_ to the new node and add one to size_. Test with one add and then two. The one-node case is the one most people get wrong.

Hint 3: insertAt and the index check

First check the range. Return false if the index is less than 0 or greater than size_. If the index equals size_, call pushBack. Otherwise, find the node currently at that index with a walk, call it at. The new node's next is at, its prev is at->prev. Then set at->prev->next to the new node, or head_ if at->prev is null, and set at->prev to the new node. Save the old prev before you change anything. Test index 0, the size, and a middle position.

Hint 4: unlink for removal

Write one private function, unlink(node), that handles all four cases: a middle node, the head, the tail and the only node. The pattern is the removeNode from lesson 5. Both remove and remove_end call it, so you only need to get it right once. The removal changes the neighbours' pointers first, then deletes the node.

Hint 5: removeFirst and removeFromEnd

removeFirst walks from the head, compares data, and calls unlink on the first match. It returns true when it removed one. removeFromEnd(k) returns false if k is less than 1 or greater than the size. Otherwise it finds the node at index size_ - k with a walk and unlinks it. Check k equal to 1 and k equal to the size by hand.

Hint 6: reverse

Walk the list once. For each node, save next, set next to prev, set prev to the saved value, then move to the saved value. This swaps the two pointers of every node. After the walk, the old tail is the new head, so swap head_ and tail_. Test by printing forwards and backwards after a reverse: the two prints must be each other's reverse.

Hint 7: middle

Use two pointers from the head. The slow one moves one node, the fast one moves two, and the loop runs while fast and fast->next are both not null. The slow pointer stops on the middle. For an even size this gives the second middle, which is what the table asks for. An empty list has no head, so return false before the loop.

Hint 8: back and the empty case

back starts at tail_ and follows prev. This is the only command that reads prev to walk the list, so it is also the best test of whether your prev pointers are right. Compare its output with print: the values must be in opposite order. Check the empty case first, because tail_ is null then.

Reference solution

The reference solution below is a complete program. Read it only after you have written your own, and compare the two line by line. There may be several correct ways to write it. What matters is that the output matches the table and the sanitizer is silent.

Reference solution (playlist.cpp)

#include <iostream>
#include <string>
using namespace std;
 
struct DNode {
    int data;
    DNode* prev;
    DNode* next;
    DNode(int d) : data(d), prev(nullptr), next(nullptr) {}
};
 
class Playlist {
public:
    Playlist() = default;
    Playlist(const Playlist&) = delete;
    Playlist& operator=(const Playlist&) = delete;
 
    ~Playlist() {
        DNode* cur = head_;
        while (cur != nullptr) {
            DNode* nxt = cur->next;
            delete cur;
            cur = nxt;
        }
    }
 
    int size() const { return size_; }
 
    void pushBack(int v) {
        DNode* n = new DNode(v);
        n->prev = tail_;
        if (tail_ != nullptr) tail_->next = n;
        else head_ = n;
        tail_ = n;
        size_++;
    }
 
    // Puts v at index (0 is the front). Returns false when index is outside 0..size.
    bool insertAt(int index, int v) {
        if (index < 0 || index > size_) return false;
        if (index == size_) {
            pushBack(v);
            return true;
        }
        DNode* at = nodeAt(index);
        DNode* n = new DNode(v);
        n->next = at;
        n->prev = at->prev;
        if (at->prev != nullptr) at->prev->next = n;
        else head_ = n;
        at->prev = n;
        size_++;
        return true;
    }
 
    bool removeFirst(int v) {
        for (DNode* cur = head_; cur != nullptr; cur = cur->next) {
            if (cur->data == v) {
                unlink(cur);
                return true;
            }
        }
        return false;
    }
 
    // k = 1 means the last node.
    bool removeFromEnd(int k) {
        if (k < 1 || k > size_) return false;
        unlink(nodeAt(size_ - k));
        return true;
    }
 
    void reverse() {
        DNode* cur = head_;
        while (cur != nullptr) {
            DNode* nxt = cur->next;
            cur->next = cur->prev;
            cur->prev = nxt;
            cur = nxt;
        }
        DNode* oldHead = head_;
        head_ = tail_;
        tail_ = oldHead;
    }
 
    // For an even size, returns the second of the two middle values.
    bool middle(int& out) const {
        if (head_ == nullptr) return false;
        DNode* slow = head_;
        DNode* fast = head_;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        out = slow->data;
        return true;
    }
 
    int count(int v) const {
        int n = 0;
        for (DNode* cur = head_; cur != nullptr; cur = cur->next) {
            if (cur->data == v) n++;
        }
        return n;
    }
 
    void print() const {
        if (head_ == nullptr) {
            cout << "(empty)\n";
            return;
        }
        for (DNode* cur = head_; cur != nullptr; cur = cur->next) {
            cout << cur->data << (cur->next != nullptr ? " " : "");
        }
        cout << "\n";
    }
 
    void printBack() const {
        if (tail_ == nullptr) {
            cout << "(empty)\n";
            return;
        }
        for (DNode* cur = tail_; cur != nullptr; cur = cur->prev) {
            cout << cur->data << (cur->prev != nullptr ? " " : "");
        }
        cout << "\n";
    }
 
private:
    DNode* nodeAt(int index) const {
        DNode* cur = head_;
        for (int i = 0; i < index; i++) cur = cur->next;
        return cur;
    }
 
    void unlink(DNode* node) {
        if (node->prev != nullptr) node->prev->next = node->next;
        else head_ = node->next;
        if (node->next != nullptr) node->next->prev = node->prev;
        else tail_ = node->prev;
        delete node;
        size_--;
    }
 
    DNode* head_ = nullptr;
    DNode* tail_ = nullptr;
    int size_ = 0;
};
 
int main() {
    int n;
    if (!(cin >> n)) return 0;
    Playlist pl;
    for (int i = 0; i < n; i++) {
        string cmd;
        cin >> cmd;
        if (cmd == "add") {
            int x;
            cin >> x;
            pl.pushBack(x);
        } else if (cmd == "insert") {
            int idx, x;
            cin >> idx >> x;
            if (!pl.insertAt(idx, x)) cout << "error index\n";
        } else if (cmd == "remove") {
            int x;
            cin >> x;
            cout << (pl.removeFirst(x) ? "removed\n" : "not found\n");
        } else if (cmd == "remove_end") {
            int k;
            cin >> k;
            cout << (pl.removeFromEnd(k) ? "removed\n" : "error index\n");
        } else if (cmd == "reverse") {
            pl.reverse();
        } else if (cmd == "middle") {
            int m;
            if (pl.middle(m)) cout << m << "\n";
            else cout << "empty\n";
        } else if (cmd == "count") {
            int x;
            cin >> x;
            cout << pl.count(x) << "\n";
        } else if (cmd == "print") {
            pl.print();
        } else if (cmd == "back") {
            pl.printBack();
        }
    }
    return 0;
}

Testing your program

Test in three stages. First, run the two samples and compare the output with the expected text exactly, including the line count. Use diff on your output and the expected output, so a single extra space shows up. Second, write your own tests for the edge cases in the rubric section, save each as a file, and check the output by hand before you trust the program. Third, compile with -fsanitizer=address,undefined -g and run each test. A clean run prints nothing extra. A leak shows as a report at exit, and a use after free shows as heap-use-after-free with a line number.

Do not trust a test that you have not checked by hand. A program that prints the same wrong answer as your code proves nothing. Work out the expected output on paper for each new test, then compare.

Stretch extension: a looping playlist

If you finish early and want more practice, add two commands. The first is loop, which makes the playlist circular, so the last track's next points back to the first track and the first track's prev points to the last. The second is next k, which prints the next k tracks starting from a cursor, going around the circle when it reaches the end.

The extension has traps. Once the list is circular, print, back, middle and remove_end must not loop forever, because they walk until nullptr. Decide what each of these commands does on a looping playlist, and write that decision down. A simple choice is to print looping and skip the walk. Before you make the list circular, the destructor must break the circle, or it will loop forever while freeing nodes.

The extension is not graded. It is a way to test whether you understand what a circular list changes about the rest of the code.

What you now know

A doubly linked list stores both prev and next, so it can remove a known node in O(1) and print in both directions.
Every change to a list is a set of pointer changes in the right order, followed by a free. The assignment checks this with a sanitizer.
Edge cases decide the grade: the empty list, the single node, the head, the tail and the even size.
A class that owns nodes must free them in a destructor, and must not be copied.
A table of commands and expected outputs is the most useful test plan for a data structure.