The data structure shown in Figure $1$ can be thought as a list of two lists, is used to classify numbers in one of $2$ groups: even numbers and odd numbers. The first node of the main list $($the list drawn horizontally, made of shaded nodes$)$ stores a number $0$ to signal that the numbers stored in its secondary list $($the list drawn vertically, $$hanging$$ from node storing number $0)$ are even $($in the figure, the numbers $2$ and $18).$ The second node of the main list stores a number $1,$ to signal that the numbers stored in its secondary list $($in the figure, the numbers $9,3$ and $15)$ are odd.

$($a$)$ In a single linked list implemented in C$++$ this is the definition of a node: $[6]$ struct Node $\{$

int data;

Node $*$next;

$\}$;

This definition is useful for the nodes belonging to the secondary lists, but not for the nodes belonging to the main list. Main list nodes need two pointers $($one for the next node in the main list and one for the first node in the secondary list$).$ Assuming that the above definition is kept for the nodes of the secondary lists, propose a new definition of node for the nodes of the main list. Call this type of node Node$\_$main and use the names of pointers given in Figure $1.$

$($b$)$ Write the pseudocode of the function INSERT$($head$,$x$)$ that inserts a new number in this data structure. If the number is even it must go to the

first secondary list $($the one $$hanging$$ from node $0$ in the main list$).$ Otherwise, it must go to the second secondary list. Assume the data structure already has the main list created and numbers are inserted at the start of the secondary list.

$($c$)$ Write the pseudocode of the function SEARCH$($head$,$x$)$ that returns TRUE if the number x is in the data structure $($in any of the secondary lists$)$ and FALSE otherwise.

$($d$)$ Write the pseudocode of the function DELETE$($head$,$ b$)$ that receives as input arguments the head of the last of two lists and a Boolean value. The function DELETE$($head$,$b$)$ deletes one of the main nodes. If b equals $0,$ then the node storing number $0$ is deleted. Otherwise, the main node storing number $1$ is deleted. Consider the following cases: the main list is empty and it has only one node $($node $0$ or $1).$