(The SortedLinkedList class template) Complete theSortedLinkedList 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 SORTEDLIST_H #define 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; 

}; 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->next; }return *this; 

 const_iterator & operator-- ( ) 

 {current = current->prev; }return *this; 

 bool operator== ( const const_iterator & rhs ) const 

 {return current == rhs.current; } 

 bool operator!= ( const const_iterator & rhs ) const 

 {return !( *this == rhs ); } 

 protected: NodeType* current; 

 T & retrieve( ) const 

 {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*( ); } 

 iterator & operator++ ( ) 

 { this->current = this->current->next; } return *this; 

 iterator & operator-- ( ) 

 { this->current = this->current->prev; 

 return *this; } 

protected: iterator( NodeType* p ) : const_iterator{ p } {}

 friend class SortedList; }; 

public: SortedList() 

{ init( );

}~SortedList()

{ clear( );

delete head;

 delete tail; } 

 iterator begin( ) 

 { return iterator( head->next ); 

}

 const_iterator begin( ) const 

 { return const_iterator( head->next ); 

}

 // Return iterator representing endmarker of list. // Mutator version is first, then accessor version. iterator end( ) { 

 return iterator( tail ); } 

 const_iterator end( ) const 

 { 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( !empty( ) ) 

}

iterator temp(erase(tail->prev)); 

// Find x in the list 

// If x 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* p = itr.current; 

 newptr->prev = p->prev; newptr->next = p; 

 p->prev->next = newptr; p->prev = newptr; 

++theSize;

 return iterator( newptr ); } 

// Erase item at itr. iterator erase( iterator itr ) 

{ NodeType* p = itr.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 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( )

{ theSize = 0;

 head->next = tail; 

 tail->prev = head; } 

}; #endif

1) Read the code carefully, and understand the nested classes const_iterator anditerator. 2) Implement the member functions find, add_item, and remove_item based on thecorrespondingcomments. Thethreefunctionsallreturnaniteratorclass.

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 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.

*******find item*******

iterated find(const T &x)

{

Node Type* ptr = head->next;

while (ptr != NULL)

{

if (ptr ->d== x)

return ptr;

current = ptr ->next;

}

return NULL;

}

******add_item*******

iterator add_item(const T &x)

{

struct Node** head_ref;

struct Node* new Node;

new Node->d = x;

struct Node* current;

// if list is empty

if (*head_ref == NULL)

*head_ref = new Node;

// if the node is to be inserted at the beginning

// of the doubly linked list

else if ((*head_ref)->d >= new Node->d) {

new Node->next = *head_ref;

new Node->next->prev = new Node;

*head_ref = new Node;

}

else {

current = *head_ref;

// locate the node after which the new node

// is to be inserted

while (current->next != NULL &&

current->next->d d)

current = current->next;

/* Make the appropriate links */

new Node->next = current->next;

// if the new node is not inserted

// at the end of the list

if (current->next != NULL)

new Node->next->prev = new Node;

current->next = new Node;

new Node->prev = current;

}

}

******remove******

iterator remove_item(const T& x)

{

struct Node* current = head;

struct Node* next_next;

while (current->next != NULL)

{

/* Compare current node with next node */

if (current->data == x)

{

/* The sequence of steps is important*/

next_next = current->next->next;

free(current->next);

current->next = next_next;

}

else /* This is tricky: only advance if no deletion */

{

current = current->next;

}

}

}

--------------------------------------------------------

this is a2q1.cpp file

#include  #include "SortedLinkedList.h" using namespace std; int main() { SortedList myList; int x; do { cout > x; if(x != 0) { myList.add_item(x); } } while(x != 0); for (SortedList::iterator it = myList.begin(); it != myList.end(); ++it) cout > x; if(x != 0) { myList.remove_item(x); } } while(x != 0); for (SortedList::iterator it = myList.begin(); it != myList.end(); ++it) cout  
Please fix my code and write SortedLinkedList.h and a2q1.cpp and show me your output
 
Thank you
 
 
 
 
  ree 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 a2q1.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 629518740 The sorted list is: 1 2 3 4567 89 The values to be removed: 4 6 2 80 The sorted list is: 1 3 5 79 please show me your output! please write code for the three files that in the question!  ree 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 a2q1.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 629518740 The sorted list is: 1 2 3 4567 89 The values to be removed: 4 6 2 80 The sorted list is: 1 3 5 79 please show me your output! please write code for the three files that in the