Consider the following code for a Linked list:

template

class Node

$\{$

public:

Node$()$;

Node$($T value, Node$*$ nextNode$)$;

T data;

Node$*$ next;

$\}$;

template

class LinkedList

$\{$

public:

LinkedList$()$;

Node$*$ getHead$()$ const; $//$ return the head pointer

Node$*$ getTail$()$ const; $//$ returns the tail pointer

void ListAppend$($T value$)$; $//$ inserts an element at the end of the list

void listPrepend$($T value$)$; $//$inserts a n element at the head of the list

void insertAfter$($Node$*$ curNode, T value$)$; $//$ Insert value after the curNode

void removeAfter$($Node$*$ curNode$)$; $//$ remove Node after CurNode

void removeHead$()$; $//$ Removes the first element

void removeTail$()$; $//$ removes the last element

void printList$()$ const; $//$ print the elements of the linked list

private:

Node$*$ head;

Node$*$ tail;

$\}$;

Please add the following functions to the class LinkedList

a$)$ getLength$()$: returns the number of items in the LinkedList.

b$)$ search$($T element$)$ : searches for the element in the LinkedList, returns a pointer to the element if found, otherwise returns NULL.

I already have some pseudocode for this:

search$($list$,$ key$)\{$

curNode $=$ list$$head

while $($curNode is not null$)\{$

if $($curNode$$data $==$ key$)\{$

return curNode

$\}$

curNode $=$ curNode$$next

$\}$

return null

$\}$

c$)$ Write an iterative implementation of a function that receives the head node of a singly Linked list void printEven$($Node $*$ l$).$ The function goes through the list and prints all the even elements in the list.

d$)$ Give a recursive implementation of this function.

e$)$ Please explain so that I can understand what you did.