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.

The code is given is:

import java.util.*;

// implementing hash tables as an array of linked lists

class Node{

private int data;

private Node nextNodePtr;

public Node(){}

public void setData(int d){

data = d;

}

public int getData(){

return data;

}

public void setNextNodePtr(Node nodePtr){

nextNodePtr = nodePtr;

}

public Node getNextNodePtr(){

return nextNodePtr;

}

}

class List{

private Node headPtr;

public List(){

headPtr = new Node();

headPtr.setNextNodePtr(null);

}

public Node getHeadPtr(){

return headPtr;

}

public boolean isEmpty(){

if (headPtr.getNextNodePtr() == null)

return true;

return false;

}

public void insert(int data){

Node currentNodePtr = headPtr.getNextNodePtr();

Node prevNodePtr = headPtr;

while (currentNodePtr != null){

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr.getNextNodePtr();

}

Node newNodePtr = new Node();

newNodePtr.setData(data);

newNodePtr.setNextNodePtr(null);

prevNodePtr.setNextNodePtr(newNodePtr);

}

public void insertAtIndex(int insertIndex, int data){

Node currentNodePtr = headPtr.getNextNodePtr();

Node prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != null){

if (index == insertIndex)

break;

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr.getNextNodePtr();

index++;

}

Node newNodePtr = new Node();

newNodePtr.setData(data);

newNodePtr.setNextNodePtr(currentNodePtr);

prevNodePtr.setNextNodePtr(newNodePtr);

}

public int read(int readIndex){

Node currentNodePtr = headPtr.getNextNodePtr();

Node prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != null){

if (index == readIndex)

return currentNodePtr.getData();

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr.getNextNodePtr();

index++;

}

return -1; // an invalid value indicating

// index is out of range

}

public void modifyElement(int modifyIndex, int data){

Node currentNodePtr = headPtr.getNextNodePtr();

Node prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != null){

if (index == modifyIndex){

currentNodePtr.setData(data);

return;

}

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr.getNextNodePtr();

index++;

}

}

public boolean deleteElement(int data){

Node currentNodePtr = headPtr.getNextNodePtr();

Node prevNodePtr = headPtr;

Node nextNodePtr = headPtr;

while (currentNodePtr != null){

if (currentNodePtr.getData() == data){

nextNodePtr = currentNodePtr.getNextNodePtr();

prevNodePtr.setNextNodePtr(nextNodePtr);

return true;

}

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr.getNextNodePtr();

}

return false;

}

public int countList(){

Node currentNodePtr = headPtr.getNextNodePtr();

int numElements = 0;

while (currentNodePtr != null){

numElements++;

currentNodePtr = currentNodePtr.getNextNodePtr();

}

return numElements;

}

public void IterativePrint(){

Node currentNodePtr = headPtr.getNextNodePtr();

while (currentNodePtr != null){

System.out.print(currentNodePtr.getData()+" ");

currentNodePtr = currentNodePtr.getNextNodePtr();

}

System.out.println();

}

public boolean containsElement(int data){

Node currentNodePtr = headPtr.getNextNodePtr();

while (currentNodePtr != null){

if (currentNodePtr.getData() == data)

return true;

currentNodePtr = currentNodePtr.getNextNodePtr();

}

return false;

}

}

class Hashtable{

private List[] listArray;

private int tableSize;

public Hashtable(int size){

tableSize = size;

listArray = new List[size];

for (int index = 0; index < size; index++)

listArray[index] = new List();

}

public int getTableSize(){

return tableSize;

}

public void insert(int data){

int hashIndex = data % tableSize;

listArray[hashIndex].insert(data);

}

public void deleteElement(int data){

int hashIndex = data % tableSize;

while (listArray[hashIndex].deleteElement(data));

}

public boolean hasElement(int data){

int hashIndex = data % tableSize;

return listArray[hashIndex].containsElement(data);

}

public void printHashTable(){

for (int hashIndex = 0; hashIndex < tableSize; hashIndex++){

System.out.print("Hash Index: " + hashIndex + " : ");

listArray[hashIndex].IterativePrint();

}

}

}

class HashTableLinkedList{

public static void main(String[] args){

Scanner input = new Scanner(System.in);

int numElements;

System.out.print("Enter the number of elements you want to store in the two lists: ");

numElements = input.nextInt();

int maxValue;

System.out.print("Enter the maximum value for an element: ");

maxValue = input.nextInt();

int hashTableSize;

System.out.print("Enter the size of the hash table: ");

hashTableSize = input.nextInt();

Random randGen = new Random(System.currentTimeMillis());

List firstList = new List();

System.out.print("Elements generated for the first list: ");

for (int index = 0; index < numElements; index++){

int value = randGen.nextInt(maxValue);

firstList.insert(value);

}

firstList.IterativePrint();

List secondList = new List();

System.out.print("Elements generated for the second list: ");

for (int index = 0; index < numElements; index++){

int value = randGen.nextInt(maxValue);

secondList.insert(value);

}

secondList.IterativePrint();

// finding the union of two lists

// and populating the elements in a new list, unionList

List unionList = new List();

Hashtable hashTable = new 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

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

System.out.print("Elements in the union list: ");

unionList.IterativePrint();

}

}