Linked-list. Anyone could help to finish the function filter() ? template <typen

Question

Linked-list. Anyone could help to finish the function filter()?

template <typename T>
class List
{
private:
// struct for singly-linked list nodes
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;

public:
// constructor
List() {
    front = nullptr;
    back = nullptr;
}

// destructor
~List() {
    clear();
}

/**
     * 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<T> *filter_leq(const T &cutoff)
{

    return nullptr;
}

Explanation / Answer

C:

/* struct Node{
All the datatypes
}
*/
// head is the root of the list.
// cutoff is the cutoff value.
Node * filter(Node* head,int cutoff)
{
    // Initializing two pointers.
    Node* temp=head->next;
    Node* prev=head;
  
    // Traversing the list and doing the needful.
    while(temp){
        if(temp->data<=cutoff)      // if data is less than or equal to cutoff remove that node.
        {
            prev->next=temp->next;
            free(temp);
            temp=prev->next;
        }
        else                        // else do nothing just move ahead.
        {
            prev=temp;
            temp=temp->next;
        }
    }
    return head;                // return the head of the list.
}

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

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