Each ordered linked list is generic, that is, stores objects of type E, where E is a parameter to the class. However, these linked lists also store, for each object, a string identifying the object. We refer to this string as the object's key.

Each linked list node must therefore have three fields (instead of the two in a normal linked list node): the object being stored, its key, and of course the next reference.

The nodes in the linked list are kept in order of increasing key value. For example, the object with key "abc" must be stored in a node that is before any node with key "xyz". Keys will be unique. Keys are compared using the String.compareToIgnoreCase method of the class String.

You must implement the keyed-node class, the orderered linked list class, and a main method in another class (perhaps called AddressList) that will implement an address book similar to what might be found in your cellphone.

Your ordered linked list class must provide at least the following methods:

• A constructor to create an empty ordered linked list.
• int size(); Returns the number of elements in the linked list.
• E add(String key, E value); If the list does not already contain the given key, the key and value are added to the linked list, and add returns null. Otherwise, the existing object with the given key is replaced with the new object (and the new key), and add returns the old (removed) object.
• E find(String key); Returns null if the key is not in the ordered linked list, and the matching object otherwise.
• E get(int position); Returns null if the index is invalid, and the object at the given position otherwise (this is unlike the standard get, which throws an exception if the position is invalid).

Your address book class provides a user interface that allows a user to:

• add a (name, telephone number) pair into the address book. The name is used as the key, but must also be stored as part of the object. If the name replaces a pre-existing name, print an appropriate message.
• search for a name in the address book, printing either the name and telephone number, or reporting that the name is not in the address book.
• display the contents of the entire address book. This is done by calling get with increasing index, until the end of the ordered linked list is reached.

The address book class should have a private inner class that defines the data stored in the address book. That data must have names and telephone numbers, but may have more information, such as email addresses.

The details of the user interface are up to you. At the very least, you could print a prompt and have a user enter the command (one of the strings "add", "find", or "print"), then ask for the appropriate parameters for each. Or if you prefer, you can open a window to get the input from the user and report on the results. Whatever you do, make sure your code is clear enough (and easy enough to use) that it will be easy to use and grade, otherwise your score may be affected.

Sample interaction

Starting program, address book is empty.
enter one of: add, find, print, quit. add
enter name to add. Hello World
enter telephone number for 'Hello World'. 1-800-555-0101

'Hello World' added to telephone book, with number 1-800-555-0101

'Hello World' was found, number is 1-800-555-0101

'foo' was not found

'hello world' added to telephone book, with number 1-800-555-0105
previous phone number for 'Hello World' was 1-800-555-0101.

'foo' added to telephone book, with number 1-800-555-0101

'foo'  1-800-555-0102
'Hello World'  1-800-555-0101

quit, discarding contents of address book.

Note that "Hello World", with uppercase letters, is replaced by "hello world" written with lowercase letters. Using the String.compareToIgnoreCase method, the two appear to be the same, that is, the comparison returns 0, but displaying the values shows that they are not identical.

Also note that when printing, the names are returned in alphabetical order, since the linked list is ordered.

Optional Extension

If you want to make your address book code more useful, you may extend it as follows. This is for your own personal enjoyment and use, and no extra credit will be given.

Add the following method to the Ordered Linked List class:

• E remove(String key); Behaves as find, but also removes the object if it is found.

Also add operations to your address book class. In particular, you can allow the user to:

• save the contents of the address book into a file.
• create a new address book from the contents of a previously saved file (this should only be allowed initially, when the address book is still empty). Each name is read from the file and saved into the linked list. The file format is up to you, as long as all the information originally in the address book is correctly restored.
• remove a name from the address book, printing whether the name was successfully found and removed.

The private inner class that defines the data stored in the address book can have a constructor that creates an address book entry given a string (say, a line read from a file), and a toString() method that produces a string that can be stored in a file. This allows you to make your address book persistent.

Both saving the address book, and printing it, are accomplished by calling get repeatedly, once for each entry in the address book, and calling toString() for each object. You may have different toString() methods (or two methods with different names), so that one is used for saving to the file, and the other for showing the address book to the user. Or you may use the same for both, as long as your constructor can accept the output of the toString() method.

The data is required to have names and telephone numbers, but may, at your choice, also hold additional fields, such as email addresses, postal addresses, perhaps birthdays, and other information.

Turning in the Assignment