In c++, implement a Linked List (List class) that works with arbitrary class objects (using a class template). You are NOT allowed to use anything from the STL, only the Node class that is included in your starter code.

The Node class is already implemented, you don't need to modify node.h. You will need to implement all member functions of the List class except print() which is already provided; you will modify list.h to do this. The following functions are members of List:

List() and ~List(): Constructor and Destructor, need to initialize members (constructor) and deallocate all nodes in list (destructor).

void print(string name): Print name, size, and values. Already implemented

int size(): Returns the size of the list.

bool empty(): Returns true if list is empty.

void insertStart(T value): Create new node with value, insert this node at the start of the list.

void insertEnd(T value): Create new node with value, insert this node at the end of the list.

void insertAt(T value, int j): Create new node with value, insert this node at position j. Position 0 is the start of the list (first node), position 1 is the second node, positon 2 is the third node, and so on...

void removeStart(): Remove node at the start of the list.

void removeEnd(): Remove node at the end of the list.

void removeAt(int j): Remove node at position j in the list.

T getFirst(): Return value of the node at the start of the list.

T getLast(): Return value of the node at the end of the list.

T getAt(int j): Return value of the node at position j.

int find(T value): Return the position of the first occurance of value in the list.

Node.h:

#pragma once

template class List;

//This class represents a node in a linked list //Do not modify anything in this file template class Node{

friend class List;

private: T value; //value stored by this node Node * next; //pointer to the next node in list

public: Node(T v){ value = v; next = nullptr; }

};

List.h:

#pragma once

#include #include #include "Node.h" using namespace std;

template class List{

private: Node * start; //pointer to the first node in this list int mySize; //size (or length) of this list

public: List(); ~List(); int size(); bool empty(); void insertStart(T); void insertEnd(T); void insertAt(T, int); void removeStart(); void removeEnd(); void removeAt(int); T getFirst(); T getLast(); T getAt(int); int find(T);

void print(string name){ cout << name << ": "; cout << "size = " << size(); cout << ", values = "; Node * iterator = start; while(iterator != nullptr){ cout << iterator->value << ' '; iterator = iterator->next; } cout << endl; }

};

//Modify the code below

//Implement all of the functions below //Construct an empty list by initializing this list's instance variables template List::List(){ }

//Destroy all nodes in this list to prevent memory leaks template List::~List(){ }

//Return the size of this list template int List::size(){ }

//Return true if this list is empty //Otherwise, return false template bool List::empty(){ }

//Create a new node with value, and insert that new node //into this list at start template void List::insertStart(T value){ }

//Create a new node with value, and insert that new node //into this list at end template void List::insertEnd(T value){ }

//Create a new node with value , and insert that new node at position j template void List::insertAt(T value, int j){ }

//Remove node at start //Make no other changes to list template void List::removeStart(){ }

//Remove node at end //Make no other changes to list template void List::removeEnd(){ }

//Remove node at position j //Make no other changes to list template void List::removeAt(int j){ }

//Return the value of the first node in the Linked List, //If no first node, return the default constructed value: T() template T List::getFirst(){ }

//Return the value of the last node in the Linked List, //If no first node, return the default constructed value: T() template T List::getLast(){ }

//Return the value of the node at position j in the Linked List, //If no first node, return the default constructed value: T() template T List::getAt(int j){ }

//Return the position of the (first) node whose value is equal to the key //Otherwise, return -1 template int List::find(T key){ }