Write a method reverse() in the LinkedList class. The method will display a string of the items in the LinkedList in reverse order.

Given the data: 0 1 2 3 4 5 The reverse method would return a string with all the values separated by a space and no trailing space at the end such as... "5 4 3 2 1 0"

You may test your algorithm using the following repl.it (Links to an external site.). (right-click and open in a new tab)

StringStream

You will need to be able to concatenate the values into a string. The stringstream object is an easy way to concatenate strings and numbers. The stringstream is located in the library and has already been included in the code. The str() function converts the stream to a string. Here is a refresher of how it works...

stringstream ss; ss << 5; ss << " plus " << 5; string equation = ss.str();

Algorithm:

There are two possible ways to get this to work.

1. Stack: You may push all the items into the stack, as you remove them, they will be in reverse order.
2. Recursion: You may recursively go through the linked list. In the build-out phase of the recursion, concatenate add the items to your string. You will most likely need to use a helper recursive function to get this to work to keep track of where you are in the linkedList and your current string, it will also be helpful to have the stringstream as a parameter such as...

   string LinkedList::helperReverse(shared_ptr> curr, stringstream &ss)

LinkedList.h file:

#pragma once #include

using std::ostream; using std::shared_ptr; using std::make_shared; using std::runtime_error;

template struct Node { Type data; shared_ptr > next; };

template class LinkedList;

template ostream& operator<< (std::ostream& out, const LinkedList& list);

template class LinkedList { public: LinkedList() : front(nullptr), back(nullptr), count(0) {}// Default constructor for the LinkedList. Creates an empty list by setting front and back of the list to nulllptr //~LinkedList(); //Destructor for the LinkedList. Creates an empty list by setting front and back of the list to nulllptr void insert(Type data); //Adds to the back of the list Type peek(int ndx)const;//Looks at an element at the given ndx value void remove(int ndx); //Removes an element at the given ndx position friend ostream& operator<< <>(std::ostream& out, const LinkedList& list);// Returns an output stream for displaying the LinkedList protected: shared_ptr > front; shared_ptr > back; int count; };

template void LinkedList::insert(Type data) { auto temp = make_shared >(); temp->data = data; temp->next = nullptr; if (!front) { front = temp; back = temp; } else { back->next = temp; back = temp; } count++; }

template Type LinkedList::peek(int ndx)const { if (ndx >= count || ndx < 0) { throw runtime_error("Out of range"); }

int currNodeNum = 0; auto currentNode = front; while (currNodeNum < ndx) { currNodeNum++; currentNode = currentNode->next; } return currentNode->data; }

template void LinkedList::remove(int ndx) { if (ndx >= count || ndx < 0) { throw runtime_error("Out of range"); }

if (ndx == 0) { auto toDelete = front; front = toDelete->next;

return; }

int currNodeNum = 0; auto currentNode = front; while (currNodeNum < ndx-1) { currNodeNum++; currentNode = currentNode->next; }

auto toDelete = currentNode->next; if (toDelete->next) { currentNode->next = toDelete->next; } else { currentNode->next = nullptr; back = currentNode; } count--; }

template ostream& operator<< (std::ostream& out, const LinkedList& list) { auto curr = list.front;

while (curr) { out << curr->data; if (curr->next) { out << " "; }

curr = curr->next; } return out; }

____________________________________________________________________________________________________________________________

LinkedList.cpp file:

#include #include #include "LinkedList.h"

using std::exception;

void testNumbers(); void testException(); void testStrings(); void testDelete();

bool checkTest(std::string testName, std::string whatItShouldBe, std::string whatItIs); bool checkTest(std::string testName, int whatItShouldBe, int whatItIs); bool checkTestMemory(std::string testName, int whatItShouldBe, int whatItIs);

int main() { testNumbers(); testException(); testStrings(); testDelete(); return 0; }

//This helps with testing, do not modify. void testNumbers() {

LinkedList si; for (int i = 10; i < 20; i++) { si.insert(i); } std::ostringstream out; out << si; //Test just to make sure the data went in the list. checkTest("test #1: adding elements", "10 11 12 13 14 15 16 17 18 19", out.str());

//Test retrieving item. int item = si.peek(0); checkTest("test #2: checking first element", 10, item); item = si.peek(3); checkTest("test #3: checking middle element", 13, item); item = si.peek(9); checkTest("test #4: checking last element", 19, item);

}

void testException() { LinkedList si; for (int i = 1; i < 4; i++) { si.insert(i); }

//Try to access out of bounds. std::string caughtError = ""; try { int item = si.peek(3); item = item;

} catch (std::exception& e) { caughtError = "caught"; } checkTest("test #5: checking exception ", "caught", caughtError); }

void testStrings() {

LinkedList ss; ss.insert("Multi Pass"); ss.insert("Lelu Dallas"); ss.insert("BIG BADA BOOM"); ss.insert("Bruce Willis"); ss.insert("Fried Chicken"); ss.insert("EEEAAAAAAAeeeaaaaaEEeeAAAEEaaaaAA"); checkTest("test #6: testing strings", "Bruce Willis", ss.peek(3));

}

void testDelete() { LinkedList si; for (int i = 10; i < 20; i++) { si.insert(i); }

si.remove(0); std::ostringstream out; out << si; //Test just to make sure the data went in the list. checkTest("test #7: deleting first item", "11 12 13 14 15 16 17 18 19", out.str()); si.remove(8); out.str(""); out.clear(); out << si; checkTest("test #8: deleting last item", "11 12 13 14 15 16 17 18", out.str()); si.insert(20); out.str(""); out.clear(); out << si; checkTest("test: #9: adding after deleting last item", "11 12 13 14 15 16 17 18 20", out.str()); bool test = true; try { test = true; si.remove(22); } catch (exception& e) { test = false; } checkTest("test #10: exceeding the list", test, false); }

//****************** //The IntWrapper class: for testing purposes //****************** class IntWrapper { friend std::ostream& operator<<(std::ostream& out, const IntWrapper& rhs); public: IntWrapper() {} // Constructor IntWrapper(int value) { this->value = value; } // Copy constructor IntWrapper(const IntWrapper& obj) { std::cerr << "Error: You hit a copy constructor, you need to rearrange node pointers, not the values in the nodes." << std::endl; } // Copy assignment bool operator=(const IntWrapper& obj) { std::cerr << "Error: You hit a assignment operator, you need to rearrange node pointers, not the values in the nodes." << std::endl; return false; } // Move constructor IntWrapper(IntWrapper&& obj) { this->value = std::move(obj.value); } // Move assignment bool operator=(IntWrapper&& obj) { this->value = std::move(obj.value); return true; } int value; }; std::ostream& operator<<(std::ostream& out, const IntWrapper& rhs) { out << rhs.value; return out; } //****************** //The Node cl

//This helps with testing, do not modify. bool checkTest(std::string testName, std::string whatItShouldBe, std::string whatItIs) {

if (whatItShouldBe == whatItIs) { std::cout << "Passed " << testName << std::endl; return true; } else { std::cout << "****** Failed test " << testName << " ****** " << std::endl << " Output was " << whatItIs << std::endl << " Output should have been " << whatItShouldBe << std::endl; return false; } }

//This helps with testing, do not modify. bool checkTest(std::string testName, int whatItShouldBe, int whatItIs) {

if (whatItShouldBe == whatItIs) { std::cout << "Passed " << testName << std::endl; return true; } else { std::cout << "****** Failed test " << testName << " ****** " << std::endl << " Output was " << whatItIs << std::endl << " Output should have been " << whatItShouldBe << std::endl; return false; } }

//This helps with testing, do not modify. bool checkTestMemory(std::string testName, int whatItShouldBe, int whatItIs) {

if (whatItShouldBe == whatItIs) { std::cout << "Passed " << testName << std::endl; return true; } else { std::cout << "***Failed test " << testName << " *** " << std::endl << " You lost track of " << whatItIs << " bytes in memory!" << std::endl; return false; } }