Data Structures and Algorithms I

Program 5

Linked lists allow rearrangement of list contents without having to move the data items (or references). In this program assignment you will gain experience working with linked lists at the lowest level. The problem also requires sorting. Data will come from a file and consist of a list of strings. Each string will appear on a distinct line of the file. Read the strings until end of file occurs. The strings are to be placed into a linked list and then sorted using a quick sort algorithm. The words will then be output.

You will need to implement a class called WordList that holds the details of the linked list of strings. This is your own primitive linked list, not a LinkedList object. Consider a constructor that takes a file name or a BufferedReader as an argument. You will also need a sort method and an output method (that accepts a PrintStream object that could be the console or a file - application's choice).

You also need a Node class. This may be entirely separate, or might be implemented as a private inner class with public members. A separate class must be used for the actual main program. This will be very short. It should prompt for the required file names and then carry out the basic tasks required.

The wordlist for testing is taken from http://world.std.com/~reinhold/diceware.html, the Diceware PassPhrase Home Page: wordlist.txt

For extra credit, subclass WordList two times. The first will be called BWordList. This is a WordList with an overridden sort method (to use a bubble sort adapted to linked lists). The second class is named MWordList. This overrides sort to use a recursive implementation of merge sort (adapted to a linked list). Your program should then compare the running times of these sorts on the same data.

Quicksort notes: I highly recommend that you follow the basic outline used in an earlier assignment to implement quicksort. I would use the first element of the list as the pivot (which will not be good if the list is already sorted - you can check out how bad by calling sort twice in a row).

Bubble notes: Bubble sort is pretty much sequential and works as well with a linked list as an array (which is not saying much). You will need to swap adjacent elements. This is easiest to do if you swap the node data contents instead of swapping the actual Nodes. Try writing a node swap and see if it does not tye you up in knots!

Merge notes: Merge sort divides a list into two parts. This is accomplished by finding the middle, and unlinking it from the first half. It then recursively sorts each part. The last step merges one into the other in a single sequential pass (possible since the elements are all ordered in both lists).