Lab 5: Linked Lists c++ Due: Friday 10/1 at 11:59 PM Begin by making a new directory for this lab, and then open a file called list1.h. Into this file type the following code (please do type it on your own, it will help you learn it better): #include #include struct Node{ std::string data; Node *next; }; class Lilist{ public: Lilist(){head = NULL;} void add(std::string item); void show(); private: Node *head; }; void Lilist::add(std::string item){ Node * tmp; if(head == NULL){ head = new Node; head -> data = item; head -> next = NULL; } else{ for(tmp = head; tmp -> next != NULL; tmp = tmp -> next) ; // this loop simply advances the pointer to last node in //the list tmp -> next = new Node; tmp = tmp -> next; tmp -> data = item; tmp -> next = NULL; } } void Lilist::show(){ for(Node *tmp = head; tmp != NULL; tmp = tmp -> next) std::cout data } Now write a main that looks like this in a file called main.cc #include #include #include "list1.h" using namespace std; int main(){ Lilist L1, L2; string target; L1.add("Charlie"); L1.add("Lisa"); L1.add("Drew"); L1.add("Derrick"); L1.add("AJ"); L1.add("Bojian"); Cout L1.show(); // END OF PART ONE // The code from here down requires that you add two functions to //the class /* cout cin >> target; if(L1.search(target) != NULL) cout else{ cout L1.move_front_to_back(); L1.move_front_to_back(); L1.show(); } */ return 0;

}

After you have written and run the program down to the place where it says End of Part One, go back into your class, and write a search function that takes a string as its argument. It will return the address of the node holding the string, or Null if the pointer runs off the end of the list. Hint, part of this code will include: if(cursor -> data == target) return cursor; Then write a move_front_to_back function. The key here is to use an extra pointer to hold the first node in the list, then move the head to the second node of the list, and then with still another pointer find the last node in the list and hook the node that used to be at the front to the back. (Look at the code youve written for adding nodes). Uncomment the rest of the main.