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 #Ifndef SORTEDLST H #de fine SORTEDLIST H using namespace std; template class SortedList private: // The basic single 1inked 1ist node type. // Nested inside of SortedList struct NodeType T data NodeType* next; NodeType* prev: odeType (const next-nullptr; public class const iterator public: Public constructor for const iterator const iterator) current-nullptr; const T &operator* const return retrieve ( const iterator & operator++ () current-current-nexti return *this const iterator & operator--) current-current->prev: return *this bool operator const const_iterator & rhs const return currentrhs.current; bool operator!- const const_iterator& rhs ) const return ! ( *this == rhs ); protected: NodeType* current: T & retrieveconst return current->data; const_iterator NodeType* p current = p; friend class SortedList class iterator public const_iterator public: iterator) T &operator* return const_iterator: :retrieve const T&operator*) const return const_iterator::operator*C iterator & operator++ this->current-this->current->next; return*this; iterator & operator this->current this->current->prev: return*this; protected: iterator ( NodeType* p const iteratort p friend class SortedListnext const_iterator begin( ) const return const iteratorhead->next) // Return iterator representing endmarker of list. // Mutator version is first, then accessor version iterator end) return iterator (tail const iterator endconst return const iterator ( tail); // Return number of elements currently in the list int size( const return theSize; // Return true if the list is empty, false otherwise bool empty const return size ( ) == 0; void clear) while( lempty) iterator temp (erase (tail->prev) // Find x in the list // Ifx is found, return x position; // If x is not found, return the position that x should be located. iterator find (const T&x NodeType* ptr -head->next: // add your code / Insert x before itr iterator insert( iterator itr, const T&X) NodeType * newptr new NodeType (x) ; NodeType pitr.current: newptr->prev newptr->next p->prev; p; = = p->prev-nextnewptr: p->prev = newptr; ++theSize; return iterator newptr // Erase item at itr. iterator erase ( iterator itr) NodeType* pitr.current; iterator retVal( p->next) p->prev->next = p->next ; p->next->prev = p->prev; delete p; --theSize; return retVal; // add x in the sorted list, find the position that x should be inserted, and then insertx iterator add item (const T&x add your cod thotion of K and remove x from the sorted list. /I If x is in the sorted list, find the position of x, and then / If x is not in the sorted list, return the position that x should iterator remove_item (const T&x) remove x be located add your code private: int theSize; NodeType head; NodeType* tail; void init) theSize0; head - new NodeType ) 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 implementation of SortedLinkedList class template, 2) the application file a2ql.cpp containing main () function, 3) a script file a2qlresult containing result. definition and Here are the sample runs Enter values in the sorted list: 3 6 2951 8 74 0 The sorted list is: 1 2 345 6 78 9 The values to be removed: The sorted list is: 1 3 57 9