1 [30 marks] (The SortedLinkedList class template) Complete the SortedLinkedList class template which is a doubly linked list and is implemented with a header node and a tail node // SortedLinkedList.h // SortedLinkedList.h // A collection of data are stored in the list by ascending order #lfndef SORTEDLST H #de fine SORTEDLIST H using namespace std template class SortedList private: // The basic single linked list node type. // Nested inside of SortedList struct NodeType T data; NodeType next; NodeType* prev; on next nullptr; public: class const iterator public: / Public constructor for const iterator. const iterator) currentnullptr; const T & operator* const return retrieve) const iterator & operatortt () current current->next; return this; const iterator & operator-) current = current->prev; return *this; bool operatorconst const_iterator & rhs const return current rhs.current bool operator'= ( const constiterator & rhs ) const - return thisrhs protected: NodeType* current: T & retrieve const return current->data; const iterator NodeType* p current = p; friend class SortedListcurrent return *this; this->current->next; = iterator & operator this->current- this-current->prev return *thisi protected iterator ( NodeType * p ) : const_iterator{ p } friend class SortedListnext: add your code // Insert x before itr iterator insert( iterator itr, const T & x ) NodeType * NodeType * newptr new NodeType (x) ; p 1tr.cu r rent; newptr-preVp>prev; newptr-nextpi p-prev-next-newptr; p-prevnewptri ++theSize; return iterator (newptr; // Erase item at itr. iterator erase( iterator itr ) NodeType* pitr.current; iterator retVal (p->next iterator retVal( p->next) p->prev->next = p->next; p-next-prevp-previ delete p; --theSize; return retVal; // add x in the sorted list, find the position that x should be inserted, and then insert x iterator add item (const T & x add your code / remove x from the sorted list. / If x is in the sorted list, find the position of x, and then remove x // If x is not in the sorted list, return the position that x should be located iterator remove item (const T &x //add your code private: int theSize; NodeType* head: NodeType tail; void init() NodeType tail; void init) thesize 0; ea head->next tail; tail->prev-head; #endif 1) Read the code carefully, and understand the nested classes const_iterator and iterator 2) Implement the member functions find, add_item, and remove item based on the corresponding comments. The three functions all return an iterator class 3) Write an application program that creates an int type sorted list using SortedLinkedList class template. prompt the user to enter int values, and add these values to the sorted list, stop e adding the values when the user enter 0 print the sorted list using iterator prompt the user to enter int values to be removed, remove the values from the sorted list, stop removing the values when the user enter 0 print the sorted list using iterator Three files should be submitted for this program question. 1) the file SortedLinkedList.h which contains the definition and implementation of SortedLinkedList class template, 2) the application file a2q1.cpp containing main ) function, 3) a script file a2qlresult containing result. Here are the sample runs: Enter values in the sorted list: 3 6 2 9 5 1 87 4 0 The sorted list is: 1 2 3 4 5 6 7 8 9 The values to be removed: The sorted list is: 1 3 579