Code in C++ and make it copyable. Include screenshots.

Q2 - 25 pts) Input two Linked Lists of integers (as Strings and then use String Tokenizer to extract the

individual integers and construct the Linked Lists) and use a hash table to construct and print out the

contents of an intersection Linked List that has the common elements of the two Linked Lists. The

intersection Linked List should have the common elements appearing only once.

For example, if L1 = 4 --> 5 --> 2 --> 2 --> 3 --> 6

L2 = 6 --> 7 --> 2 --> 5 --> 2 --> 3

The intersection Linked List L12 = 2 --> 5 --> 3

Note that there are two instances of node '2' in both the Linked Lists L1 and L2, the intersection linked list

should have only one instance of node '2'.

You are given the code discussed in class to find the union of two linked lists such that the union linked

list has only unique integers even though the two linked lists may have duplicates. In this question too,

the two linked lists may have duplicate integers, but the intersection linked list should have only unique

integers.

Test your code with integer sequences of length 15, the maximum value for an integer being 20 and a

hash table size of your choice. Capture the screenshot of your output.

#include #include //srand, rand #include //clock_t, clock, CLOCKS_PER_SEC using namespace std;

// implementing hash tables as an array of linked lists

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 }

bool deleteElement(int deleteData){ Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; Node* nextNodePtr = headPtr; while (currentNodePtr != 0){ if (currentNodePtr->getData() == deleteData){ nextNodePtr = currentNodePtr->getNextNodePtr(); prevNodePtr->setNextNodePtr(nextNodePtr); return true; } prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr->getNextNodePtr(); } return false; } int countList(){ Node* currentNodePtr = headPtr->getNextNodePtr(); int numElements = 0; while (currentNodePtr != 0){ numElements++; currentNodePtr = currentNodePtr->getNextNodePtr(); } return numElements; }

void IterativePrint(){ Node* currentNodePtr = headPtr->getNextNodePtr(); while (currentNodePtr != 0){ cout << currentNodePtr->getData() << " "; currentNodePtr = currentNodePtr->getNextNodePtr(); } cout << endl; } bool containsElement(int searchData){ Node* currentNodePtr = headPtr->getNextNodePtr(); while (currentNodePtr != 0){ if (currentNodePtr->getData() == searchData) return true; currentNodePtr = currentNodePtr->getNextNodePtr(); } return false; } };

class Hashtable{ private: List* listArray; int tableSize; public: Hashtable(int size){ tableSize = size; listArray = new List[size]; } int getTableSize(){ return tableSize; } void insert(int data){ int hashIndex = data % tableSize; listArray[hashIndex].insert(data); } void deleteElement(int data){ int hashIndex = data % tableSize; while (listArray[hashIndex].deleteElement(data)); } bool hasElement(int data){ int hashIndex = data % tableSize; return listArray[hashIndex].containsElement(data); } void printHashTable(){ for (int hashIndex = 0; hashIndex < tableSize; hashIndex++){ cout << "Hash Index: " << hashIndex << " : " ; listArray[hashIndex].IterativePrint(); } } };

int main(){

int numElements; cout << "Enter the number of elements you want to store in the two lists: "; cin >> numElements; int maxValue; cout << "Enter the maximum value for an element: "; cin >> maxValue;

int hashTableSize; cout << "Enter the size of the hash table: "; cin >> hashTableSize; srand(time(NULL)); List firstList; cout << "Elements generated for the first list: "; for (int index = 0; index < numElements; index++){ int value = rand() % maxValue; firstList.insert(value); } firstList.IterativePrint(); List secondList; cout << "Elements generated for the second list: "; for (int index = 0; index < numElements; index++){ int value = rand() % maxValue; secondList.insert(value); } secondList.IterativePrint(); // finding the union of two lists // and populating the elements in a new list, unionList List unionList; Hashtable hashTable(hashTableSize); // populating the hash table based on the first list // only unique elements are inserted in the hash table for (int index = 0; index < numElements; index++){ int value = firstList.read(index); if (!hashTable.hasElement(value)){ hashTable.insert(value); unionList.insert(value); } } // going over the secondList and inserting only those // elements that are not there in the hash table // (i.e., not in the first list) // elements are to be included only once in the union for (int index = 0; index < numElements; index++){

int value = secondList.read(index); if (!hashTable.hasElement(value)){ hashTable.insert(value); unionList.insert(value); }

} // unionList print - only unique elements cout << "Elements in the union list: "; unionList.IterativePrint(); return 0; }