Comp 271 lab 1 - ArrayList<String>
- Introduction to ArrayList
- Introduction to for loops
In this lab you will use ArrayLists; in fact, you will use an ArrayList of
ArrayLists. This lab can also be seen as a preparation for hashing.
Step 1 Instructions:
- Create a big ArrayList HArray in which each element is an empty
ArrayList<String>. The size of the ArrayList will be HMax. (It
would make sense to have HArray be an array rather than an
ArrayList, but Java won't let us create an array of
ArrayList<String>.) Start with HMax around 100 (it may
be best to choose a prime number around 100). Note the value of HMax in
the file is 1000.
- Using .add(), create HMax-many actual ArrayList<String> entries
in HArray (done for you!)
- Read in each word in the file words.text. The words are in
alphabetical order, one per line; there are just under 3,000 of them.
The existing code reads them all into a big ArrayList<String>
called lines. You can then process the words from lines, or modify the
code to process the words as they are read in.
- For each word w, calculate hc = w.hashCode()
- Then reduce hc to the range 0 to HMax-1. You can set hc = hc % HMax if
hc is positive. What should you do if hc<0?
- Add word w to the list HArray.get(hc)! One way is this:
L = HArray.get(hc);
But you can also combine all this into a single statement.
- When you're done, print out each separate list HArray.get(i), for i
from 0 to HMax-1. Use a for loop. Put each separate list on one line.
What does this do to the word order?
Step 2: Now try increasing HMax to 500, or 1000. Do you see any empty
lines in the output?
Step 3: The file words.text contains one word that is duplicated. Find
it, by checking, before adding each word, whether that word is
L = HArray.get(hc);
if (L.contains(w)) System.err.format(...);
A starter BlueJ project, in .zip format, is available
here. The starter file includes code to open the file. Each call to
br.readLine() returns one word of the file.
Submit your work on Sakai (or via email) by putting it all into a zip file
(that is, make a zip file of your BlueJ project directory). I think
that all goes ok if you do this with Java. (For C#, there would be an
included .exe file, which the email system declines to forward.)