In C++, you need to transpose the linked list, where you move the object in the
ID: 3838174 • Letter: I
Question
In C++, you need to transpose the linked list, where you move the object in the node that is being searched, one node closer to the head. This allows to decrease the cost as the more often the obj is searched the closer it moves to the head of the list. You have a remove function to remove the node from the linked list. You need to create a function where the parameter is the object that is being searched and will be swapped one node closer to the head. Insert your line of code in the find function where the two helper comments are.
DList<Object>::DList( ) {
header = new DListNode<Object>;
header->next = NULL;
header->prev = NULL;
cost = 0;
}
int TransposeList<Object>::find( const Object &obj ) {
DListNode<Object> *found = DList<Object>::header->next;
int i = 0;
for ( ; found != NULL && found->item != obj; found = found->next, ++i )
++DList<Object>::cost;
if ( found == NULL )
return -1; // not found
if ( found == DList<Object>::header->next )
return 0; // no need to swap
// remove found from the current position
// insert found before previous
}
Explanation / Answer
DList<Object>::DList( ) {
header = new DListNode<Object>;
header->next = NULL;
header->prev = NULL;
cost = 0;
}
int TransposeList<Object>::find( const Object &obj ) {
DListNode<Object> *found = DList<Object>::header->next;
int i = 0;
for ( ; found != NULL && found->item != obj; found = found->next, ++i )
++DList<Object>::cost;
if ( found == NULL )
return -1; // not found
if ( found == DList<Object>::header->next )
return 0;
}