1.This lab is a multi-file project on sorted linked lists. You have been given BaseLnkLst.jar, a Java archive containing BaseLnkLst.class, the .class file associated with the implementation of an abstract linked list to be used as a base class in addition to Data.class and Node.class. It has most of the necessary components for a sorted linked list . The only missing pieces are bSearch, createFromFile and insSort. bSearch implements a binary search algorithm. It accepts a final Data meant to represent an instance of type Data with the SSN set to the desired search key. bSearch returns the int position of the node who's data matches the search key; a failure status is returned otherwise. Like lSearch, if bSearch finds the key, the list is left at that position; otherwise it is repositioned to where it was before the search began and a failure status is returned. On the other hand, insSort accepts a final Data referring to the record that is to be inserted. It returns a bad status in case of a failure; otherwise, the int position at which the new node was inserted is output. Finally, createFromFile is virtually identical to what you wrote for the unsorted linked list, except that it uses insSort instead of insTail so as to build the list in a sorted fashion.
You are to create SrtrdLnkLst.java to extend the functionality of BaseLnkLst. Make use of your implementation by creating a sorted linked list. With minor modifications, the driver from the previous lab can be used for this assignment. It continuously re-prompts the user for an input file name. The file will be binary and contain the same randomized information as you have seen in previous exercises.
After the file name has been successfully acquired, call the createFromFile method that reads the file one record at a time and then performs a sorted insertion, thereby forming the sorted linked list. This function accepts a String representing the input file name. As in the previous lab, it returns an int representing the number of records read; a failure status otherwise.
insSort must search through the list to find the point where the new node should be inserted. Since the list is being built in a sorted fashion, it is possible to search for the proper location using a binary search algorithm similar to the one you implemented in bSearch. While it is possible to base insSort exclusively on a sequential search of the list, it is sensible to consider the binary search for this insertion function .
Upon returning and only if the status is successful, the driver will continuously re-prompt the user to enter a search SSN. This SSN is used to create a Data object which is a final Data argument to bSearch. If the search is successful, the driver uses the returned int representing the node where the search key was found. The list will be positioned at the appropriate node and can be used to write a report as shown in the output below. This report contains the time it took to perform the binary search if the record with the input SSN is found; otherwise, it reports that the record with the input SSN was not found. The driver should re-prompt the user to see if s/he would like to search for another record or use another file.
Your output should appear as follows:
C:\LAB.DB could not be opened.
Do you wish to enter another input file name (Y/N)? - y
Enter the file you want to read - C:Lab07unsortedDataSmall.bin
Preparing to read C:Lab07unsortedDataSmall.bin
C:Lab07unsortedDataSmall.bin has 25000 records.
Enter the search SSN (no separators please) - oYTy>,wY=
Searching for SSN oYT-y>-,wY=
The key was found in record # 3877.
The binary search required 1 ms to complete.
SSN = oYT-y>-,wY=
fName = cDhr?5yH5'GFIokR<]"$
mName = c
lName = ljdEq472*?HGY]wshP,0x5'Sx`R4m8
addr = Qlf>$7{M$P2zN K6M{#9/|4g(J(#U!WGXBa(/DR
city = ;ZRZsz2WNjUkMp;WTz1t
state = Yx
zip = 1@su[rEq2
Do you wish to continue with another SSN (Y/N)? - n
Do you wish to continue with another file (Y/N)? - n