This lab is a continuation of your previous 4 labs, but in this lab we will be swapping out the `stringVector` you wrote with a linked list. A linked list is a data structure that connects nodes together in a line, and the only way to get to a particular node it to traverse down the line until you find it. Linked lists are useful because they allow us to insert or delete at certain places in O(1) time. Your First In/First Out(Queue) and Last In/First Out(Queue) can easily be rewritten to use a linked list. This form of stacks and queues is actually the more traditional way of implementing those data structures because linked list both allow for constant time access of the first element and removal of items, and that that you can have an infinite amount of items in the stack or queue. ### Lab Instructions Implement each of the functions to perform the necessary actions outlined in the `.h` files or here. Implement the linked list and test the functionality of it using tests. Remember, you need to implement all of the functions supported by the class, including the `sort` function. As you are writing your functions, read the instructions and think of how you would test that functions while you are writing it. Write your Test first and then implement your functions. Try running your test and then fixing your issues. `linked_list::sort()` will sort the items in a linked list using selection sort. Refer to the wikipedia article on selection sort for more information on how this sorting algorithm works. Remember, you wlll be implemnting this in a linked list and not an array. Get creative, because the wikipedia article talks specifically about performing this sort on an array. You will need to understand how to translate this algorithm to use a linked list instead. For the calculator, you only need to support integer calculations. You need to support the operators `+ - * / ( ) ^ %`. **NOTE:** You are adding two new operations in this lab. The actual calculator will be almost exactly the same as your previous calculator. Just copy the contents of the `.h` and `.cpp` and change the namespace and the data structures used to hold the stacks and queues. You may need to change some of the way you accomplish some of the functions as well. If you feel like supporting floating point calculations, you might need to change the way expressionStream works. You will also need to write a new calculate function that returns a float rather than an integer. You may need to create auxiliary functions to complete tasks, or to avoid copy and pasting repetitive code. Do not make these class functions. These should only appear in the .cpp file ### Lab Functions that you haven't seen before  `linked_list::insert(input, location = 0)`: create a node from the input string and put it into the linked list at the given location `linked_list::append(input)`: create a new node and put it at the end/tail of the linked list `linked_list::remove(location = 0)`: Remove the node at the given location `linked_list::sort()`: Perform selection sort on the linked list `linked_list::listSize()`: Note that you do **not** have a size variable in your linked list. You *MUST* count the nodes. Ask questions on slack about functions that you don't understand. For the most part, this lab is a rehash of your previous labs but with a new data structure. 

#ifndef CMPE126S18_LABS_LIB_LAB05_INC_LINKED_LIST_H #define CMPE126S18_LABS_LIB_LAB05_INC_LINKED_LIST_H #include "node.h" #include namespace lab5 { class linked_list { node *head, *tail; public: linked_list(); explicit linked_list(std::string &data); linked_list(const linked_list &original); virtual ~linked_list(); linked_list &operator=(const linked_list &RHS); friend std::ostream& operator<<(std::ostream& stream, linked_list& RHS); friend std::istream& operator>>(std::istream& stream, linked_list& RHS); bool isEmpty() const; unsigned listSize() const; void insert(const std::string input, unsigned location = 0 ); void append(const std::string input); void remove(unsigned location = 0); void sort(); }; } #endif 

#include namespace lab5 { linked_list::linked_list() { head=nullptr; tail=nullptr; } linked_list::linked_list(std::string &data) { } linked_list::linked_list(const linked_list &original) { } linked_list::~linked_list() { head=nullptr; tail=nullptr; } linked_list &lab5::linked_list::operator=(const linked_list &RHS) { //return <#initializer#>; } bool linked_list::isEmpty() const { if(head=nullptr&&tail=nullptr) { return false; } } unsigned linked_list::listSize() const { return 0; } void linked_list::insert(const std::string input, unsigned int location) { } void linked_list::append(const std::string input) { } void linked_list::remove(unsigned location) { } std::ostream& operator<<(std::ostream &stream, linked_list &RHS) { return stream; } std::istream& operator>>(std::istream &stream, linked_list &RHS) { return stream; } void linked_list::sort() { } } 

#ifndef CMPE126S18_LABS_LIB_LAB05_INC_QUEUE_H #define CMPE126S18_LABS_LIB_LAB05_INC_QUEUE_H #include "linked_list.h" namespace lab5 { class queue { private: linked_list storage_structure; public: queue(); queue(std::string &data); queue(const queue &original); virtual ~queue(); queue &operator=(const queue &RHS); bool isEmpty() const; unsigned queueSize() const; std::string top() const; void enqueue(const std::string &data); void dequeue(); friend std::ostream& operator<<(std::ostream& stream, queue& RHS); friend std::istream& operator>>(std::istream& stream, queue& RHS); }; } #endif 

#include "queue.h" namespace lab5{ queue::queue() { } queue::queue(std::string &data) { } queue::queue(const queue &original) { } queue::~queue() { } queue &queue::operator=(const queue &RHS) { //return <#initializer#>; } bool queue::isEmpty() const { return false; } unsigned queue::queueSize() const { return 0; } std::string queue::top() const { //return std::__cxx11::string(); } void queue::enqueue(const std::string &data) { } void queue::dequeue() { } std::ostream& operator<<(std::ostream &stream, queue &RHS) { return stream; } std::istream& operator>>(std::istream &stream, queue &RHS) { return stream; } } 

#ifndef CMPE126S18_LABS_LIB_LAB5_NODE_H #define CMPE126S18_LABS_LIB_LAB5_NODE_H #include  namespace lab5 { class node { public: node *next; std::string data; explicit node(const std::string &data) : data(data), next(nullptr){}; }; } #endif