class CDLinkedList $\{$

public:

CDLinkedList$()$; $//$ the constructor

CDLinkedList$($const CDLinkedList &rhs$)$;

~CDLinkedList$()$; $//$ the destructor

int getCurrentSize$()$ const;

bool isEmpty$()$ const;

bool add$($int newEntry$)$;

bool remove$($int anEntry$)$;

void clear$()$;

$//$ This will search the entry from the list. make sure to use virtual so that transposelist can override

virtual bool contains$($int anEntry$)$;

int getTraverseCount$()$ const; $//$ return traverseCount

int retrieve$($ const int index $)$; $//$ retrieve the data by index. The first item is at index $0.$

void resetTraverseCount$()\{$ traverseCount $=0$; $\}$

protected:

DListNode $*$header; $//$ a dummy header

int traverseCount $=0$;

$\}$;

The data member $($traverseCount$)$ is initialized to zero and is used to hold the count of the number of nodes traversed during list usage. contains$(),$ remove$(),$ and retrieve$()$ methods should update this count as it traverses the list $($i$.$e$.,$ increment it each time it moves from one Node to the next$).$ add$()$ method will add a Node in front if the data is not already in the list. If it is already in the list, then ignore. Since it also traverses the list, this add$()$ method should also update the traverse count. If add$()$ method calls contains$()$method$,$ it will automatically update the traverse count. If not, you have to make sure to update the traverse count in the method as well. It is up to your design.

$2.$ Make two subclasses of CDLinkedList $,$ called MtfList and TransposeList, that implements the move$-$to$-$front and swap strategy, respectively, by overriding CDLinkedList ::contains$()$ method. MtfList ::contains$()$ should override CDLinkedList ::contains$()$ method so that if it contains, move the target node to front. TransposeList ::contains$()$ should override CDLinkedList ::contains$()$ method so that if it contains, swap the target node with the previous node.

$3.$ Test each class's method with your own designed testing file. A brief sample driver.cpp file is available from Files$>$Programs$>$program$1$ folder. The following testing scenarios explain how to test your programs.