In C++

Write a recursive function to determine whether or not a Linked List is in sorted order (smallest value to largest value).

Add the following function prototypes to your List class under the section for access functions, then implement the functions below the class definition:

public:

/**Access Functions*/

bool isSorted();

//Wrapper function that calls the isSorted helper function to determine whether //a list is sorted in ascending order. //We will consider that a list is trivially sorted if it is empty. //Therefore, no precondition is needed for this function

private: bool isSorted(Nodeptr node); //Helper function for the public isSorted() function. //Recursively determines whether a list is sorted in ascending order.

#include //for NULL #include #include using namespace std; template //list stores generic list data, not any specific C++ type class List { private: struct Node { listdata data; Node* next; Node* previous;

Node(listdata data): data(data), next(NULL), previous(NULL){} };

typedef struct Node* Nodeptr;

Nodeptr first; Nodeptr last; Nodeptr iterator;

int size; public:

/**Constructors and Destructors*/

List(); //Default constructor; initializes and empty list //Postcondition: numeric values equated to zero, or strings should be empty. List(const List &list);

~List(); //Destructor. Frees memory allocated to the list //Postcondition: position NodePtr at next Node

/**Accessors*/

listdata getFirst(); //Returns the first element in the list //Precondition:NodePtr points to the first node on list

listdata getLast(); //Returns the last element in the list //Precondition: make new node first on the list listdata getIterator();

bool isEmpty(); //Determines whether a list is empty.

int getSize(); //Returns the size of the list

/**Manipulation Procedures*/ void startIterator(); void advanceIterator(); void removeLast(); //Removes the value of the last element in the list //Precondition: list is not empty, not the first element. //Postcondition: one remaining node void removeIterator(); void removeFirst(); //Removes the value of the first element in the list //Precondition: list is not empty //Postcondition: no nodes left

void insertLast(listdata data); //Inserts a new element at the end of the list //If the list is empty, the new element becomes both first and last //Postcondition: next equal to null

void insertFirst(listdata data); //Inserts a new element at the start of the list //If the list is empty, the new element becomes both first and last //Postcondition:point nodePtr next node on list

/**Additional List Operations*/ bool offEnd(); void printList(); //Prints to the console the value of each element in the list sequentially //and separated by a blank space //Prints nothing if the list is empty void insertIterator(listdata data); bool operator==(const List &list); };

// constructor definition template List::List(): first(NULL), last(NULL), iterator(NULL), size(0) {}

template List::List(const List &list): size(list.size) { if(list.first == NULL) //If the original list is empty, make an empty list for this list { first = last = iterator = NULL; } else { first = new Node(list.first->data); //calling Node constructor Nodeptr temp = list.first; //set a temporary node pointer to point at the first of the original list iterator = first; //set iterator to point to first node of the new list

while(temp->next != NULL) {

temp = temp->next; //advance up to the next node in the original list iterator->next = new Node(temp->data); //using node constructor to create a new node with copy of data iterator = iterator->next; //advance to this new node

}

last = iterator; iterator = NULL; } }

template List::~List() { Nodeptr cursor = first; Nodeptr temp; while(cursor != NULL) { temp = cursor->next;

delete cursor;

cursor = temp; } } //inserts first node template //Step 1: template the function void List::insertFirst(listdata data) { if (size == 0) //Why is this necessary? { first = new Node(data);

last = first; //notice the order here. Assignment is right to left

} else{

Nodeptr N = new Node(data);//create the new node by calling the node constructor N->next = first;//set the new node's next field to point to the first node first->previous = N; first = N;}//point the first pointer to the new node size++; }

template void List::printList() { iterator = first; //create a temporary iterator while (iterator != NULL) {

coutnext; //Add two lines of code here

//Hint: One statement should contain a cout

} cout << endl; //What does this do? }

template void List::insertLast(listdata data) { if (size == 0) //Why is this necessary? { Nodeptr n = new Node(data); first = last = n; //notice the order here. Assignment is left to right

} else { Nodeptr N = new Node(data);//create the new node by calling the node constructor last->next = N;//set the new node's next field to point to the last node last->previous = N; last = N;//point the last pointer to the new node }

size++;

}

template void List::removeFirst() { if (size==0){

cout << "removeFirst: List is empty. No data to remove." << endl;

} else if (size == 1) {

delete first;

first = last = NULL;

size = 0;

} else {

Nodeptr temp = first; //store pointer to first so we don't lose access to it

first = first->next; //advance the pointer

delete temp; //free the memory for the original first node

size--;

}

}

template void List::removeLast() { if (size==0){

cout<<"last is empty"; } else if (size==1) {

delete last; last = first = NULL; size = 0;//fill in the missing lines here

} else { last->previous->next=last->next;

delete last; //free the memory for the original last node

last->next = NULL; //so last->next is not pointing at freed memory

size--;

}

}

template bool List::isEmpty() { return (size==0); }

template listdata List::getIterator() { assert(size != 0); assert(iterator != NULL); return iterator->data; }

template int List::getSize() { return size; }

template listdata List::getFirst() { assert(first != NULL); return first->data; }

template listdata List::getLast() { assert(last != NULL); return last->data; }

template void List::insertIterator(listdata data) {

if(size==0) cout<<"list empty"< else if(iterator == last) { insertLast(data); } else{ Nodeptr n = new Node(data); n->next = iterator ->next; n->previous = iterator; iterator->next->previous=n; iterator->next = n; size++; } }

template void List::startIterator() { iterator = first; }

template void List::advanceIterator() { iterator=iterator->next; }

template void List::removeIterator() { assert(iterator != NULL); if (iterator == first) { removeFirst(); } else if (iterator == last) { removeLast(); } else { iterator->previous->next = iterator->next; iterator->next->previous = iterator->previous; delete iterator; iterator = NULL; size--; } }

template bool List::offEnd()

{ return iterator == NULL; } template bool List::operator==(const List& list) { if(size != list.size) return false; Nodeptr temp1 = first; Nodeptr temp2 = list.first; while(temp1 != NULL) { if(temp1->data != temp2->data) return false; temp1 = temp1->next; temp2 = temp2->next; } return true; }