Program 1

Due: Feb. 5, 2001


This assignment will be use a linked list to store and modify a character string.

Your program will take a character string, and store it as a singly linked list. Suppose the character string is

"the quick brown fox jumped over the lazy dog".

This becomes a linked list with 44 characters, including the blanks that separate the words. (Hint: look at the String class and charAt method to do this). Once you have this, your program should be able to:

  1. set the cursor to the first matching character -- for example, the first "o" in the string
  2. find out and print what word the cursor is in -- for example, if the cursor is pointing to the "o" in brown, the word "brown" (and no blanks) should be printed
  3. substitute a new word for a word in the string --for example, substitute purple for brown. To do this, you will need to write a method that: takes as arguments references to a starting and ending node, and the list containing the replacement word; finds the predecessor to the starting node (if there is more than one matching word, use the first); and replaces the word in the first string.
Your driver program should do all the above in a general way, so that it will work on all words, even the first and last words in the string. Your driver program should contain the above examples when you mail in your program, but make sure you test it on other cases, as we will.

To show that your program works on the cases you test it on, after each of the above, your program should print something (the string, a substring, as appropriate). To help with this assignment some carefully designed methods will be useful. In fact, to help with debugging, one of the first methods you should write is one that prints a substring starting from a given location, and if helpful, ending at a specific location. This method should be in the CharNode class. Everything else is in a different (i.e. your own) class.