Write this function given the template below for linked lists in C++ with the gi

Question

Write this function given the template below for linked lists in C++ with the given requirements:

Given implementation of Linked list that can be helpful for writing function:

TODO function: filter-leg 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: 1st: [4, 9, 2, 4, 8, 12, 7, 3] cutoff: 4 after call: 1st: , 8, 12, 71 returne d list:[4, 2, 4, 3] EX2: 1st: [6, 5, 2,1] cutoff: 6 after call: 1st: returned list: [6, 5, 2, 11 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:

Explanation / Answer

Please find the C++ code below :

#include <bits/stdc++.h>
using namespace std;

template <typename T>
class List{
    private :
        struct Node
        {
            T data;
            Node * next;
            Node(const T &d = T{}, Node *n = nullptr)
                : data{d}, next{n} {}
        };
        Node *front = NULL;
        Node *back = NULL;

    public :
        List<T> filter_leq(const T &cutoff){
            List<T> retList;
            Node *tmp = this->front;
            Node *tmpNext = this->front->next;
            if (tmp->data <= cutoff)
            {
                retList.addNode(tmp->data);
            }

            while(tmpNext != nullptr){
                if (tmpNext->data <= cutoff)
                {
                    retList.addNode(tmpNext->data);
                    tmp->next = tmpNext->next;
                    tmpNext = tmpNext->next;
                    continue;
                }
                tmp = tmp->next;
                tmpNext = tmpNext->next;
            }

            if (this->front->data <= cutoff)
            {
                this->front = this->front->next;
            }

            return retList;
        }

        bool addNode(T data){
            Node *newNode = new Node(data);
            if (back != NULL)
            {
                back->next = newNode;
            }          
            else{
                front = newNode;
            }
            back = newNode;
            return true;
        }

        void printList(){
            Node *tmp = front;
            while(tmp != NULL){
                cout << tmp->data << " ";
                tmp = tmp->next;
            }
            cout << endl;
        }

};

int main()
{
    List<int> myList;
    List<int> retList;
    cout << "test Case 1 :-"<<endl;
    myList.addNode(4);
    myList.addNode(9);
    myList.addNode(2);
    myList.addNode(4);
    myList.addNode(8);
    myList.addNode(12);
    myList.addNode(7);
    myList.addNode(3);
    cout << "List before filter : ";
    myList.printList();
    cout << "List after filter : ";
    retList = myList.filter_leq(4);
    myList.printList();
    cout << "List returned : ";
    retList.printList();
    cout << "test Case 2 :-"<<endl;
    List<int> myList2;
    List<int> retList2;
    myList2.addNode(6);
    myList2.addNode(5);
    myList2.addNode(2);
    myList2.addNode(1);
    cout << "List before filter : ";
    myList2.printList();
    cout << "List after filter : ";
    retList2 = myList2.filter_leq(6);
    myList2.printList();
    cout << "List returned : ";
    retList2.printList();
    return 0;
}

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

Outputs :

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.