See list_handout.pdf for the class definition and implementation of a double lin
ID: 3882437 • Letter: S
Question
See list_handout.pdf for the class definition and implementation of a double linked list. Rewrite the findnode(int index)functionto perform a forward search in the first half ofthe list if index<N/2 and a backward search in the second half of the list otherwise. The result should be that no more than N/2 nodes will be visited as part of a search.Hint: Sketch what you are trying to accomplish on a piece of paper before you thinkabout the code.
list_handout 09/08/17 09:57:11 #include #include using namespace std; Hint: Notice how the three different list implementations on the next several pages use the SAME public interface with the only differences being wrt the implementation details class 1ist/see next several pages Hint: Notice how the operator member functions are overloaded differently to support the different underlying 1ist types void printlist (const char operation, list &v;) coutExplanation / Answer
node *findnode(int n){
node *p;
int count,found;
count = 0;
found = 0;
if (head == NULL)
return NULL;
p = head;
count
if (n < N/2) {
while (count <= N/2){
if (p->data == n){
found = 1;
break;
}
p = p->next;
count++;
}
}
else{
while (p->next != NULL)
p = p->next;
while (count <= N/2){
if (p->data == n){
found = 1;
break;
}
p = p->prev;
count++;
}
}
if (found == 1)
return p;
else
return NULL;
}