MTF and Transpose List

Purpose

This programming assignment exercises dynamic memory allocation, pointer operations, and copy constructor design through designing a doubly$-$linked circular list with a dummy header. You will also implement an ADT class hierarchy from scratch, and will understand how to improve time efficiency with different search algorithms.

Improving Search in a Linked List

An example of an inefficient ADT for use in applications that require frequent searching is a linked list $$ especially an unsorted linked list. Basic linked list implementations fundamentally require sequential searches to find elements. Moreover, if a linked list is unsorted, then finding an element by value not only requires sequential search, but also requires that the entire list be traversed before concluding that the element isn't in the list. And sorting isn't a panacea, because the insertion operation requires traversal.

However, this basic performance analysis considers only single searches in isolation, without taking into account any information about the intended application. What if we have an application in which the list is built once and then searched many times $($or$,$ more generally, where searches are much more common than inserts$/$deletes$)?$ And what if we already have an unsorted list implementation? Can we modify our list in a simple way to improve its performance on average? Formally, this is the topic of what is called amortized analysis, which is an advanced area of algorithm analysis that we won't touch on much this quarter. However, let's do a simple exercise to see what a simple modification can achieve.

What we are going to implement is a MTF $($Move$-$to$-$front$)$ and Transpose list. In an MTF list, every time an element is accessed, it is moved to the front of the list. In a Transpose list, every time an element is accessed, it is swapped with the previous node of the list. So$,$ if some items are statistically more likely to be accessed than others $($accessed more frequently$),$ then they will tend to be near the front of the list and so shorter traversals will be needed to find them. Assuming this, then the average number of nodes traversed during the execution of a program should be much lower. Through this assignment, you will learn the followings.

Use C$++$ pointers and memory management.

Implement classes that manage their own dynamically allocated memory.

Demonstrate understanding of linked lists by producing modified versions and analyzing their performance.

Implement a non$-$trivial linked list$-$based ADT class hierarchy from scratch.

Statement of Work

Refer the Files$>$Programs$>$program$1$ folder.

$1.$ Design and implement a Circular Doubly Linked List with dummy header with all listed methods, name as CDLinkedList class, with a Node class$/$struct that holds an int, and two pointers point to previous and next node. The files should be CDLinkedList.h and CDLinkedList.cpp$.$ Since it is circular and with a dummy header, the first node is a dummy header and last node's next node should point this dummy header, and dummy header's previous node is the list's last node.

$//$ A node that will have two pointers, prev, and next

struct DListNode $\{//$ a list node

int item;

DListNode $*$prev;

DListNode $*$next;

$\}$;

The CDLinkedList class should include the following methods, and you have to implement them. The specification provided below are essential methods that are necessary. You can add any other helper methods if needed.

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.

make CDLinkedList.cpp