CMSC 206 (Data Structures)
Due: March 1, 2012
The goal of this assignment is
implement and use the LinkedList ADT in a real
You are STRONGLY encouraged to
work with one
partner on this assignment. If you do work with a
should submit only ONE assignment for both people.
A spell checker is a common application used in conjunction
document preparation. Since many documents focus on one
words in a document are often repeated. Hence, it makes sense
checking the spelling of repeated words should be made as fast
possible. In this project you will implement a rudimentary
checker that provides for faster access to frequently used
spell checker will be implemented as a List of Lists.
We will implement two variations of the linked list ADT by
deriving two new kinds of linked lists using inheritance. This
require you to implement your own linked list ADT and create
derived list implementations. One new list is called a
used (MRU) list. Every time an element of
an MRU List is "found" it is moved to the front of the list.
way, frequently accessed data is always close to the front of
so subsequent "finds" for that data are quicker. New words are
at the front of the MRU List. For our spell-checker this means
repeated words in a document are checked more quickly.
The other new Linked List is the "Sorted Linked List" (SLL). A
keeps its data sorted at all times by inserting new elements
appropriate place in the list.
Assignment 2 will be invoked with multiple command line
first argument is the name of the text file which will be
spelling errors. The second argument is the name of the
file. The third command line argument is the number of words
for each letter on the command line. The remaining argument(s)
single lower-case characters [a-z] for which recently used
word lists are printed.
I have already provided a substantial amount of code to get
as well as skeletons for all the classes you'll need to
implement. You can find this code in your dropbox
submission folder. Just replace the version I placed
These spelling rules are already implemented for you in the
removePunctuation() functions in Assignment2.java.
ensure a thorough understanding of how the program works and to
with debugging, you should read them over several times.
- A word in the text file is defined to be a sequence of
surrounded by whitespace. Any sequence of characters
something other than the letters A-Z and a-z should be
misspelled, but see below concerning punctuation characters.
example, in the string "This.example shows many_things."
there are 3
"This.example", "shows", and "many_things.".
- All words should be considered to be case-sensitive.
if you find the word monday in the text
file and that
word is not found in the dictionary, then you have a
since Monday would be in the
- Punctuation is removed from words using the following
punctuation characters tailing a word should be removed.
Punctuation characters are defined as periods, exclamation
question marks, semi-colons, and commas.
are the only punctuation that can be removed from the
middle of a word
- Quotation marks and parenthesis must be removed from
the beginning and end of words.
- For example, in the sentence "Hi,
looking nice today?", you would remove the
comma, and the question mark and search the dictionary for
the words Hi, you're, looking, nice and today.
To complete the assignment, you will need to implement the
first three abstract data types (ADTs). I strongly
suggest you complete
them in the order they are presented.
Four other ADTs are provided for you in their entirety:
Dictionary, WordList, MisspelledWordList and
CountedWord. You may use the classes
as-is; there is no need to implement anything for them.
The Linked List ADT
You must complete the provided Linked List skeleton, including
implementing LinkedList, ListNode, and ListIterator
can be a single or doubly linked list, and should use the List
The MRU List ADT
The Most Recently Used (MRU) List is derived from LinkedList.
provides no other functionality. It differs from a LinkedList
one way -- elements which are successfully found are moved to
of the list. The list is unchanged in the event of an
operation. Since an MRU list is inherently NOT sorted, new
be inserted anywhere in the MRU list.
The Sorted List ADT
The Sorted List is derived from LinkedList. It provides no
functionality. It differs from a LinkedList in just one way --
elements are always in ascending sorted order.
The Dictionary ADT [Provided]
The dictionary contains Strings which represent the complete
correctly spelled words. To facilitate fast look-up, these
stored based on their first letter in an MRU list for each
the alphabet. The Dictionary is essentially a SortedList
MRU word lists. Note that it does not matter whether the
letter of each word is upper or lowercase.
The Dictionary ADT defines the following operations
- void insert( String word ) -- adds the
to the dictionary.
- boolean contains( String word ) -- searches
for the specified word.
- String printMRU( char letter, int n ) -- returns a
String of the n
most recently used words in the
dictionary that begin with the specified letter, formatted
appropriately for output. If less than n words start with
letter, then all words beginning with that letter are
words must be printed
in a neat columnar format, 4 words per row.
Each column must be separated by a minimum of 2
whitespaces. The width
of the columns will depend on the length of the longest
word to be
operation is case-INsensitive. The parameter
passed to the function may be upper- or lower-case. In
words that begin with the same upper- or lower-case letter
For example, printMRU('a',
10) and printMRU('A',
print words which
begin with 'a' OR 'A'.
- A default constructor which creates an empty dictionary.
Word List ADT [Provided]
The WordList associates some
information with the MRU list for each letter of the alphabet.
WordList ADT encapsulates this information and becomes an
the MRU list. The WordList ADT defines the following
- appropriate constructor(s)
- appropriate comparison and equals methods
- an appropriate toString() function
- void insert( String word ) -- inserts
word into the WordList
- boolean contains( String word ) -- finds the
in the WordList
Misspelled Word List ADT [Provided]
The spell checker must maintain a list of misspelled words
number of times each misspelled word appears. To do so, we've
the MisspelledList ADT which defines the following operations:
- appropriate constructor(s)
- void insert( String word ) -- inserts
word into the MisspelledList. If the word is already in
the list, its
count is incremented.
- String toString( ) -- prints the
list in alphabetical order.
CountedWord ADT [Provided]
Since the printed list of misspelled words also includes the
times each misspelled word appears, good object-oriented
dictates that these data items be stored together in a simple
which we are calling a CountedWord.
The CountedWord ADT defines the following operations
- appropriates constructor(s) that takes in the word as a
and initializes its count at 1.
- void increment( ) -- increments
- appropriate comparison operators
- String toString( ) that outputs
the word and
and count in the format "<word> : <count>"
The main() function and spell checking application is already
for you in Assignment2.java. Do not rename the
class. For your understanding and to help debugging, you
understand the steps that the Assignment2.main() follows for
- ALL LISTS used
this assignment must
be linked lists. This
JAVA ARRAYLISTS, LINKED LIST, ARRAYS are permitted.
- The MRU list and Sorted Linked List (SLL) must be
implemented using inheritance. They are both derived from
- All possible exceptions discussed pertaining to a
linked list must be caught and dealt with appropriately.
should continue processing after an exception if at all
may include any private data and private
functions to any class.
- Be prepared for your code to work on large data
- You must bulletproof your code as much as
possible, e.g. making sure that the command line
parameters are all
valid, that the files named in it all exist, and that
there is at least
one report command. In case of invalid report parameters,
should print them and a message indicating that the
command is in error.
the Dictionary and MisspelledList classes
are instantiated in main() or in functions called from
classes should be placed in the package
may modify any of the provided code however you
like, providing that it
meets the project requirements.
- The program reads in the following command line
order (see the Sample Output section for an example):
name of the file containing the text.
name of the file containing the dictionary.
integer n, specifying the number of words to print
from each MRU list.
(optional, but must be paired with item 4)
or more letters for the MRU lists to print.
(optional, but must be
paired with item 3)
- Reads the file of words and puts them into the
include one word per line. There is no need
punctuation from this file, as it will have already been
- Reads the text file and checks each word for
proper spelling according to the spelling rules above.
To do this, it removes punctuation as described above and
check to see if the word is in the dictionary. If it
is not, then
is misspelled. Misspelled words will then
be inserted into the misspelled word list.
- Prints the list of misspelled words and the number of
each misspelled word appeared. This list is printed in
The words must be printed in a neat columnar format, 4
words per row.
The format is shown in the sample output. For formatting
we assume that no misspelled word will appear more than 99
- For each letter found on the command line, prints the
first n (taken
from the command line)
from that letter's MRU list in the dictionary.