the to do section needs to be coded at the end for function filter_leq

#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;

}

/**

* TODO

*

* function: length

* desc: returns the length of the calling list

*

* REQUIREMENTS: this is a working implementation, but

* it takes linear time.

*

* Your job (todo): make modifications so that this

* operation becomes constant time (O(1)).

*

* This task is different from most others in that most of

* the "real" work you do to make this work

* in O(1) time will be in _other_ functions which affect

* the length of lists.

*

* HINT: you are free to add data members to the List class...

* maybe for "bookkeeping"??

*/

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;

}

/**

* TODO

* function: filter_leq

*

* description: removes all elements of the given list (lst) which

* are less than or equal to a given value (cutoff)

*

* A list containing the removed elements is returned.

*

* examples:

*

* EX1: lst: [4, 9, 2, 4, 8, 12, 7, 3]

* cutoff: 4

*

* after call:

* lst: [9, 8, 12, 7]

* returned list: [4, 2, 4, 3]

*

* -----------------------------------------

* EX2: lst: [6, 5, 2, 1]

* cutoff: 6

*

* after call:

* lst: []

* returned list: [6, 5, 2, 1]

*

* REQUIREMENTS:

*

* RUNTIME: THETA(n) where n is the length of the given list

*

* ORDERING: the ordering of the returned list should be the same as

* in the given list

*

* MEMORY: for full credit, no new nodes should be allocated or deallocated;

* you should just "re-use" the existing nodes. HOWEVER, you will

* need to allocate a LIST structure itself (i.e., for the returned

* list).

*

*/

List *filter_leq(const T &cutoff)

{

return nullptr;

}