You are given the code for a singly linked list-based implementation of the List ADT. You will add a function called isUnique( ) to the List class such that the function will return true if all the integer elements in the List are unique and return false otherwise. The main function is written in such a way that it will create 1000 Lists (each of size listSize) of random integers in a range [1...maxValue] and will call the isUnique function to determine how many of these 1000 Lists are unique. The main function is programmed to determine the fraction of the 1000 Lists that are unique and the fraction is referred to as the probability that a List of listSize with integers in the range [1...maxValue] will be unique. You will test your code with the following values for listSize and maxValue.

listSize: the last two digits of your J#. For example, if your J# is J00123456, then your listSize is 56. In case, the last two digits of your J# is a value less than 10, you will add 10 to that value and use the sum as the listSize. For example, if your J# is J00120005, then your listSize will be 10 + 05 = 15.

maxValue: the last four digits of your J#. For example, if your J# is J00123456, then your maxValue is 3456. In case, the last four digits of your J# is a value less than 1000, you will add 1000 to that value and use the sum as the maxValue. For example, if your J# is J00120005, then your maxValue will be 1000 + 0005 = 1005.

The Code:

#include

#include

#include

using namespace std;

// implementing the dynamic List ADT using Linked List

class Node{

private:

int data;

Node* nextNodePtr;

public:

Node(){}

void setData(int d){

data = d;

}

int getData(){

return data;

}

void setNextNodePtr(Node* nodePtr){

nextNodePtr = nodePtr;

}

Node* getNextNodePtr(){

return nextNodePtr;

}

};

class List{

private:

Node *headPtr;

public:

List(){

headPtr = new Node();

headPtr->setNextNodePtr(0);

}

Node* getHeadPtr(){

return headPtr;

}

bool isEmpty(){

if (headPtr->getNextNodePtr() == 0)

return true;

return false;

}

void insert(int data){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

while (currentNodePtr != 0){

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

}

Node* newNodePtr = new Node();

newNodePtr->setData(data);

newNodePtr->setNextNodePtr(0);

prevNodePtr->setNextNodePtr(newNodePtr);

}

void insertAtIndex(int insertIndex, int data){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != 0){

if (index == insertIndex)

break;

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

index++;

}

Node* newNodePtr = new Node();

newNodePtr->setData(data);

newNodePtr->setNextNodePtr(currentNodePtr);

prevNodePtr->setNextNodePtr(newNodePtr);

}

int read(int readIndex){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != 0){

if (index == readIndex)

return currentNodePtr->getData();

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

index++;

}

return -1; // an invalid value indicating

// index is out of range

}

void modifyElement(int modifyIndex, int data){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != 0){

if (index == modifyIndex){

currentNodePtr->setData(data);

return;

}

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

index++;

}

}

void deleteElement(int deleteIndex){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

Node* nextNodePtr = headPtr;

int index = 0;

while (currentNodePtr != 0){

if (index == deleteIndex){

nextNodePtr = currentNodePtr->getNextNodePtr();

break;

}

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

index++;

}

prevNodePtr->setNextNodePtr(nextNodePtr);

}

void IterativePrint(){

Node* currentNodePtr = headPtr->getNextNodePtr();

while (currentNodePtr != 0){

cout << currentNodePtr->getData() << " ";

currentNodePtr = currentNodePtr->getNextNodePtr();

}

cout << endl;

}

bool isUnique(){

// Implement the function

}

};

int main(){

srand(time(NULL));

int listSize;

cout << "Enter the number of elements you want to insert: ";

cin >> listSize;

int maxValue;

cout << "Enter the max. value for an element in the list: ";

cin >> maxValue;

int numTrials = 1000;

int numUniqueTrials = 0;

for (int trials = 1; trials <= numTrials; trials++){

List integerList; // Create an empty list

for (int i = 0; i < listSize; i++){

int value = 1 + rand() % maxValue;

integerList.insertAtIndex(i, value);

}

if (integerList.isUnique()){ // You need to implement the isUnique( ) function in the List class

numUniqueTrials++;

}

}// end trials loop

cout << "Probability for a list to be unique is: " << (((double) numUniqueTrials)/numTrials) << endl;

system("pause");

return 0;

}