this is the function that needs to be finished . insert_sorted

#ifndef LIST_H #define LIST_H

#include #include

/** * class List * * General description: class for storing and manipulating sequences of items * where item type is specified via template. * * Underlying organization: the implementation uses a singly-linked list data structure * with pointers to both the front (first node) and back (last node) of the list. * * A private struct Node is used to represent individual nodes in a list. */

template class List { private:

struct Node { T data; Node *next;

Node(const T &d = T{}, Node *n = nullptr) : data{d}, next{n} {} };

/* Data members of List class: a front and back pointer */ Node *front; Node *back; int list_size; public: // constructor List() { front = nullptr; back = nullptr; list_size = 0; }

// destructor ~List() { clear(); } /** * Disclaimer: C++ conventions tell us that we should have a couple * of additional constructors here (a copy constructor, assignment operator * etc.) * * However, to keep things simple for now we will ignore that convention * (since the exposure to C++ is pretty variable it seems -- some students * having taken 141 before last semester; some students coming from 107, * etc.) */

/** * function: clear * desc: makes the calling list empty (but the list still * exists). */ void clear() { Node *p = front; Node *pnext;

while (p != nullptr) { pnext = p->next; delete p; p = pnext; } front = back = nullptr; }

int length() const { return list_size; } public: /** * function: is_empty * desc: Returntrue if the list is empty, false otherwise. */ bool is_empty() const { return front == nullptr; }

/** * function: print * desc: self-evident: simply prints the elements/values of the list in order. */ void print() const { Node *p = front;

std::cout << "[ "; while (p != nullptr) { std::cout << p->data << " "; p = p->next; } std::cout << "] "; }

/** * function: push_front * desc: adds a new element to the front of the list (calling object) containing val. * Equivalently, you can think of this as an "prepend" operation. */ void push_front(const T &data) { front = new Node(data, front);

if (back == nullptr) back = front; list_size++; }

/** * function: pop_front * desc: if the list (calling object) is non-empty, the first element (front of list) * is removed and the value it stored is 'passed back' to the caller via the reference * parameter val. In this case (non-empty list), true is returned for success. * * Otherwise (the list is empty), false is returned and the reference parameter val has * no meaning. */ bool pop_front(T &val) { Node *tmp;

if (front == nullptr) return false; val = front->data;

tmp = front; front = front->next; delete tmp; if (front == nullptr) back = nullptr; list_size++;

return true;

}

/** * function: push_back * desc: adds a new element to the end of the list (calling object) containing val. * Equivalently, you can think of this as an "append" operation. */ void push_back(const T &val) { Node *tmp = new Node(val, nullptr);

if (front == nullptr) { front = back = tmp; } else { back->next = tmp; back = tmp; list_size--; } }

/** * function: remove_first * desc: removes first ocflience of x (if any) in given list (calling object). * if a match is found (and removed), true is returned. * Otherwise (no match found), false is returned and the list is unchanged. */ bool remove_first(const T &x) { Node *p, *tmp; T dummy;

if (front == nullptr) return false; if (front->data == x) { pop_front(dummy); return true; } p = front; while (p->next != nullptr) { if (x == p->next->data) { tmp = p->next; p->next = tmp->next; if (tmp == back) back = p; delete tmp; return true; } p = p->next; } return false; }

/** * function: slow_remove_all * desc: removes all occurrences of x (if any) in given list (calling object). * returns number of matches found/deleted. Relative order of undeleted elements * is unchanged. * * approach: repeatedly calls remove_first until it fails. * * Note: function is designated with the slow_ prefix because, in the worst case, it can * take quadratic time. */ int slow_remove_all(const T &x) { int n = 0;

while (remove_first(x)) n++; return n; list_size--; }

/** * function: is_sorted * desc: returns true if elements in list are in sorted order from * smallest to largest (duplicates allowed); returns false otherwise. * * Note: requires that type T has the > operator defined on it (perhaps via * operator overloading as in the case of the string class) */ bool is_sorted() const { Node *p = front;

while (p != nullptr && p->next != nullptr) { if (p->data > p->next->data) return false; p = p->next; } return true; }

int count(const T &x) const { int frequency = 0;

if (this->is_empty()) return frequency;

Node* temp1 = front; while (temp1 != nullptr) {

if (temp1->data == x) frequency++; temp1 = temp1->next; } return frequency;

}

bool pop_back(T &data) { if(front == nullptr) return false; else{ Node *temp1 = front; while(temp1->next->next != nullptr) { temp1 = temp1->next; } this->back = temp1; temp1=temp1->next ; data = temp1-> data; delete (temp1); return true; //list_size++; go back to this

}

}

/** TODO

* function: insert_sorted

*

* description: assumes given list is already in sorted order from

* smallest to largest and inserts x into the appropriate position

* retaining sorted-ness.

* Note 1: duplicates are allowed.

*

* Note 2: if given list not sorted, behavior is undefined/implementation

* dependent. We blame the caller.

* So... you don't need to check ahead of time if it is sorted.

*

*

* REQUIREMENTS:

*

* O(n) runtime

*/

void insert_sorted(const T &x)

{

}