Given the following classes SortedLinkedDataList class, Data…
Given the following classes SortedLinkedDataList class, Data class and DataNode class: You may assume that the code indicated by the …s is correctly completed code that you do not need to worry about. Part 1. Complete the private method recursiveRemoveElement(DataNode pNode, Data pData) such that it will recursively search the list. If there is a node in the list that contains the same information as in the pData argument object, it will return the node’s Data object and remove the node from the SortedLinkedDataList. If the SortedLinkedDataList does not have a node that contains the same information as in the pData argument object, it will return null. You may assume that the SortedLinkedDataList is a sorted list, in ascending order. Your search and removal must be efficient. At least as efficient as it can be given that you are using a linked list. (20 points) Part 2. Given the same classes as above, complete the recursive private method printInReverseRecursive, that displays to the terminal window the information from the list in reverse order. (10 points) Part 3. Given the following RandomList class, that is implemented using an unbound array, complete the two methods: randomAdd(Data pData) that adds a Data element into a random location in the list. (10 points) randomGet() that retrieves and removes a random element from the list. If the list is empty return null. (10 Points) Do not worry about how the list’s array is expanded. Your solutions must run in constant time. This means that the time it take to add or remove an element from the list is independent of the number of elements in the list. There is a little quibbling about this when it becomes necessary to expand the array. Do not worry about the cost of expanding the array. The key to implementing these two methods, with constant time algorithms, is that the list is unsorted. Use int(Math.random() * size) to generate a random index. class Data{ … public boolean equals(Data pData){ boolean isEqual = true; … return isEqual;} public int compareTo(Data pData){ int compareValue = 0; … return compareValue ;} public toString(){ String dataString = null; … return dataString ;}}class DataNode implements Comparable{ private Data data = null; private DataNode link = null; … public Data getData(){ return data;} public boolean equals(DataNode pDataNode){ return this.data.equals(pDataNode.getData());} public int compareTo(DataNode pDataNode){ return this.getData().compareTo(pDataNode.getData());}} class SortedLinkedDataList{ private DataNode head = null; private DataNode tail = null; private size = 0; … public data removeElement(Data pData){ return recursiveRemoveElement(null, head, pData);} private Data recursiveRemoveElement(DataNode pPrevNode, DataNode pNode, Data pData){ //ToDo } public void printListInReverse(){ printInReverseRecursive(head);} private void printInReverseRecursive(DataNode pNode);{ //ToDo }}class RandomList{ private Data[] randomList = null; int size = 0; … public boolean isEmpty(){ return size == 0; public boolean isFull(){ if( size == randomList.length ){ expandList(); return false; private void expandList(){…} public Data randomGet(){ //toDo } public void randomAdd(Data pData){ //toDo }}
Read Details