Assignment # $2$: Doubly Linked Lists

Implementing a Music Playlist Manager

Overview

In this assignment, you will use doubly$-$linked lists implemented in C$++$ to develop a music

playlist manager. This manager will allow users to add songs, navigate through the playlist,

remove songs, and perform other typical playlist operations.

Requirements

You are required to implement several functions that a typical music player would have.

The playlist starts empty, and songs can be added, removed, or navigated through. Each

song will be represented as a string $($the song title$)$ within a node of the doubly$-$linked list.

Class Definitions

You are given the class Playlist, which is a doubly$-$linked list implementation that uses the

class DLLNode. Each song in the playlist will be represented using one DLLNode, where the

song title is a string within the node.

Sample Output

In the sample output below, the current active song is shown enclosed in parenthesis. For

example, in this list $[$ Song$1<($Song$2)>$ Song$3],$ Song$2$ is the current active song. The $<$

indicates previous songs, and $>$ indicates next songs.

Playlist myPlaylist;

cout $<<$ myPlaylist $<<$ endl;

$[]$

cout $<<$ myPlaylist.curr$\_$val$()<<$ endl;

$($myPlaylist is empty$)$

myPlaylist.add$\_$song$("$Song$1")$;

myPlaylist.add$\_$song$("$Song$2")$;

myPlaylist.add$\_$song$("$Song$3")$;

myPlaylist.add$\_$song$("$Song$4")$;

cout $<<$ myPlaylist $<<$ endl;

$[($Song$1)<$ Song$2<$ Song$3<$ Song$4]$

cout $<<$ myPlaylist.curr$\_$val$()<<$ endl;

Song$1$

myPlaylist.next$\_$song$()$;

cout $<<$ myPlaylist $<<$ endl;

$[$ Song$1<($Song$2)<$ Song$3<$ Song$4]$

cout $<<$ myPlaylist.curr$\_$val$()<<$ endl;

Song$2$

myPlaylist.remove$\_$song$("$Song$3")$;

cout $<<$ myPlaylist $<<$ endl;

$[$ Song$1<($Song$2)<$ Song$4]$

Task Descriptions

$1.$ Adding a Song

o Implement the function add$\_$song which takes a song title string and adds it

to the playlist. The new song should be added after the current song.

$2.$ Navigating Forward

o Implement the function next$\_$song, which moves the current song to the next

song in the playlist. It should return the current active song $($title$).$

$3.$ Navigating Backward

o Implement the function previous$\_$song, which moves the current song to the

previous song in the playlist. It should return the current active song $($title$).$

$4.$ Removing a Song

o Implement the function remove$\_$song, which removes a song from the

playlist based on the song title. If the current song is removed, the next song

should become the current song. If the removed song is the last one, the

previous song should become the current song.

$5.$ Clearing the Playlist

o Implement the function clear$\_$playlist, which clears all songs from the

playlist. The playlist should be empty after this operation.

Restrictions

$$ All of your functions must run in time O$($n$)$ in the worst case.

Class Declarations

Below are the skeleton declarations for DLLNode and Playlist classes. You need to

implement the member functions.

#include

#include

template

class DLLNode $\{$

public:

T data;

DLLNode$*$ prev;

DLLNode$*$ next;

DLLNode$($const T& data, DLLNode$*$ prev $=$ nullptr, DLLNode$*$ next $=$ nullptr$)$

: data$($data$),$ prev$($prev$),$ next$($next$)\{\}$

$\}$;

template

class Playlist $\{$

private:

DLLNode$*$ head;

DLLNode$*$ tail;

DLLNode$*$ curr;

void clear$\_$forward$\_$history$()$;

public:

Playlist$()$;

~Playlist$()$;

void add$\_$song$($const T& song$)$;

T next$\_$song$()$;

T previous$\_$song$()$;

void remove$\_$song$($const T& song$)$;

void clear$\_$playlist$()$;

T curr$\_$val$()$ const;

friend std::ostream& operator$<<($std::ostream& os$,$ const Playlist& pl$)$;

$\}$;

Implementation Details

$1.$ Constructor and Destructor:

o Implement the constructor to initialize the playlist.

o Implement the destructor to free the memory used by the nodes.

$2.$ Adding a Song:

o Add a new song after the current song. If the playlist is empty, add the song

as the first song.

$3.$ Navigating Forward and Backward:

o Move the current song pointer to the next or previous song, ensuring you do

not go out of bounds.

$4.$ Removing a Song:

o Find the song by title and remove it from the list, adjusting the pointers

accordingly.

$5.$ Clearing the Playlist:

o Remove all nodes from the playlist and reset it to the initial state.

$6.$ Printing the Playlist:

o Overload the $<<$ operator to print the playlist in the format described.