Each linked list node must have three fields (instead of the two in a normal linked list node): the object being stored, its key, and 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. This method returns 0 if the two strings are equal, a negative number if this string is less than the argument, and a positive number otherwise.

You must implement three classes:

the KeyedNode class as a private class of OrderedLinkedList,

the OrderedLinkedList class, and

another class called AddressList that implements an address book similar to what might be found in your phone.

The AddressList is used for testing only.

The OrderedLinkedList class must provide at least the following methods:

A no-arguments constructor public OrderedLinkedList() class 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.

Iterator iterator(); a standard iterator method, which gives an iterator that returns each of the elements in turn (do not implement the remove() method of the iterator).

String toString(); a standard toString method, which uses the iterator or a foreach loop to get all the elements in the iterator. The string representation of the orderered linked list should show all the elements as "(key1,element1),(key2,element2)..."

Adding an object to the linked list must add it at the correct position.

The address book class can provide 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. 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. This code should use the iterator.

display the contents of the entire address book, by calling addressBook.toString();

You should define a private inner class (in your address class) to store whatever values you want in your address book. The values should include names and telephone numbers, but may have more information, such as email addresses.

It will probably be a good idea for you to write a toString() method for this private inner class.

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.