Overview

For this assignment you will be creating a multi$-$file project in which you implement your own

templated linked list and use it to create a simple list of composers. When doing this

assignment, take small, incremental steps; trying to complete the lab in one go will make the lab

more difficult. This means that any time you finish part of the lab, such as a linked list method,

you should immediately test and debug it if necessary.

Part $1$: Creating your Linked List

Create a header file, Node.h$,$ that has a templated class called $$Node$.$ This class should be able

to hold both a data value and a pointer to another node.

Once your node class is complete, create a new header file, LinkedList.h$,$ that has a templated

class called $$LinkedList$.$ The class should have two member variables: a pointer to the first

element of the linked list and a pointer to the last element of the linked list.

Additionally, the class will need to have the following methods $($do not define them inline$).$ Some

methods may only have a few lines while others are more complicated and will require a bit

more thought. Make sure you test all cases for each method and appropriately update the

pointers to the first and last nodes if needed.

$1.$ LinkedList$()$;

Constructor for linked list. You decide what needs to be done here

$2.$ ~LinkedList$()$;

Destructor for linked list. You decide what needs to be done here

$3.$ void printList$()$ const;

Displays all elements in linked list. This is one of the most important methods

because it gives you a way to test your code! For example, once you write the append$()$

method, you should test it using printList$().$

$4.$ void append$($const T data$)$;

Adds a node to the end of the list. For example:

list $=1->2->3$

list.append$(4)$

list $=1->2->3->4$

$5.$ void prepend$($const T data$)$;

Adds a node to the front of the list. For example:

list $=1->2->3$

list.append$(0)$

list $=0->1->2->3$

$6.$ bool removeFront$()$;

Removes the front node. For example:

list $=1->2->3$

list.removeFront$()$

list $=2->3$

$7.$ void insert$($const T data$)$;

Accepts a value and will insert the value into the linked list in the correct order.

list $=1->2->4$

list.insert$(0)$

list $=0->1->2->4$

list.insert$(5)$

list $=0->1->2->4->5$

list.insert$(3)$

list $=0->1->2->3->4->5$

$8.$ bool remove$($const T data$)$;

Accepts a value and will remove the node with that value from the list. Return true if the

node was found and removed and return false otherwise.

list $=1->2->3$

list.remove$(2)//$returns true

list $=1->3$

list.remove$(2)//$returns false

list $=1->3$

$9.$ bool find$($const T data$)$;

Accepts a value and will search for that value in the linked list. Return true if the value is

in the list and false otherwise

$10.$ bool isEmpty$()$ const;

Returns true if list is empty and false otherwise

$11.$ T getFirst$()$ const;

Returns the value stored in the first node of the list $($not a pointer to the node$).$

$12.$ T getLast$()$ const;

Returns the value stored in the last node of the list. For example:

list $=1->2->3$

list.getFirst$()//$returns $1$

list.getLast$()//$return $3$

Note: Remember that your linked list needs to have both a pointer to the first node and a pointer

to the last node $($The book has code for a templated linked list, but it only has a head pointer.

You will not be able to directly copy out of the book$).$ Keep this in mind when writing your

methods. For example, what is different about the remove$()$ method if we remove a node from

the front vs$.$ a node at the end vs$.$ a node in the middle? What about if the list is empty?

Part $2$: Using your linked list

You will now test your linked list by creating a simple list of composers using the input below.

composers.txt

Ludwig van Beethoven, $1827$

Wolfgang Amadeus Mozart, $1791$

Johann Sebastian Bach, $1750$

Frederic Chopin, $1849$

George Frideric Handel, $1759$

Franz Liszt, $1886$

Johannes Brahms, $1897$

Igor Stravinsky, $1971$

Pyotr Ilyich Tchaikovsky, $1893$

Claude Debussy, $1918$

Joseph Haydn, $1809$

Gustav Mahler, $1911$

Sergei Prokofiev, $1953$

Richard Wagner, $1883$

Giacomo Puccini, $1924$

Felix Mendelssohn, $1847$

Aaron Copland, $1990$

Franz Schubert, $1828$

Giuseppe Verdi, $1901$

Maurice Ravel, $1937$

Dmitri Shostakovich, $1975$

Sergei Rachmaninoff, $1943$

Arnold Schoenberg, $1951$

George Gershwin, $1937$

Robert Schumann, $1856$

Leonard Bernstein, $1990$

Bela Bartok, $1945$

Antonin Dvorak, $1904$

Antonio Vivaldi, $1741$

Edvard Grieg, $1907$

Camille Saint$-$Saens, $1921$

Henry Purcell, $1695$

Claudio Monteverdi, $1643$

Hector Berlioz, $1869$

Each entry in the file consists of two data fields: the composer$$s name and the date of death.

Instead of creating two separate linked lists, we will take advantage of the fact that our linked list

is a template and can hold any generic type. Our generic type will be a new class.

First create a new header file, Composer.h; the class should have two member variables to hold

the composer$$s name and the date of their death. It is