#include  #include  using namespace std; /* Implement the "studentList" data structure with a doubly linked list implementation. You must implement all methods and they must work as described in the comments. You must also achieve the stated run times, and know the big-Oh run times for each of your methods. */ class student { public: string name; unsigned int id; double gpa; student() { name = "ghost"; id = 0; gpa = 0; } student(string _name, unsigned int _id, double _gpa) { id = _id; gpa = _gpa; name = _name; } }; class studentList { private: //Implement a doubly linked list of students class node { public: student data; node * next; node * prev; node(student x) { data = x; next = NULL; prev = NULL; } }; node * head; node * tail; public: studentList(); //add a student to the list. //Must run in O(1) time. void insert(student s); //find the student with the given id number and return it //What is the worst case run time of this? //What is the average case run time of this? student retrieveStudent(unsigned int idnumber); //Change the gpa of the student with given id number to newGPA //What is the run time? void updateGPA(unsigned int idnumber, double newGPA); //Add all students from otherlist to this list. //otherlist should be empty after this operation. //Must run in O(1) time. void mergeList(studentList &otherlist); //create a list of students whose gpa is at least minGPA. //Return this list. The original list should //not be modified (do not remove the students from the original list). //Run time? studentList honorRoll(double minGPA); //sort the list by the given field ("name", "id", or "gpa"). //Run time? void sort(string field); //Print out each student in the list. This is mainly for testing purposes. void printList(); };