0. Introduction.

This assignment involves re-implementing the Map class from laboratory #7, but using a linear, singly-linked list instead of an array. Such a list is sometimes called an association list, a term borrowed from the programming language Lisp.

1. Theory.

An association list is a linear, singly-linked list of nodes. Each node in an association list has three slots, called key, value, and next. The key and value slots point to objects of specific types. The next slot points to the next node in the list (or to null). Each node associates its key object with its value object. Association lists have the following operations, all of which involve traversing lists and searching for a node with a given key object.

You can get the value object from a node. Its the object that is associated with the nodes key object.

You can change the value object in a node. After that, the key object is associated with a different value object.

You can delete the node that contains a key. After that, the key object is not associated with a value object.

If you cannot find a node, then you can add a new one that contains a key object and a value object. After that, the key object is associated with the value object.

As a result of these operations, you can use an association list something like a dictionary. For example, the key objects might be Strings that are English words for numbers. The valueobjects might be Integers that correspond to those words. If you give the association list an English word, then you can get back its corresponding number. Association lists work by doing linear search. As a result, if an association list has n keys, then each of the operations described above will require O(n) comparisons. Later in this course, well discuss more efficient alternatives to association lists. These will need only O(log n) or even O(1) comparisons.

2. Implementation.

You must write a Java class called AssociationList that implements an association list. To simplify grading, your class must use the same names for things that are used here. It must have two class parameters, called Key and Value, so it looks like this.

class AssociationList { ? }

Here Key is the type of the association lists key objects, and Value is the type of the association lists value objects. Within the class AssociationList, you must have a private class called Node. The class Node must have three private slots: a slot called key whose type is Key, a slot called valuewhose type is Value, and a slot called next whose type is Node. It must have a constructor that initializes these three slots from its arguments. Dont try to use the node classes from the lectures, or from other lab assignments. They have the wrong number of slots, and the wrong types of slots. Also, you are not allowed to use arrays in any way. If you implement AssociationList using one or more arrays, then you will receive zero points for this lab. Your AssociationList class must also have a private variable called head. It must point to the head Node in a linear singly-linked list of Nodes. The head node is a dummy node that is always at the front of a linked list; it helps eliminate special cases when deleting nodes. Along with Node and head, your class must have these methods. All of them work with head somehow.

public AssociationList()

Constructor. Initialize an empty instance of AssociationList.

public void delete(Key key)

Search the association list for a Node whose key slot equals the key parameter, according to isEqual. Delete that Node from the list. If no Node has a key slot that equals thekey parameter, then do nothing. Your delete method must not use a special case to delete the first Node in the list after head. Hint: use the left-right trick discussed in the lectures.

public Value get(Key key)

Search the association list for a Node whose key slot equals the key parameter, according to isEqual. Return the value slot of that Node. If no Node has a key slot that equals the key parameter, then throw an IllegalArgumentException.

private boolean isEqual(Key leftKey, Key rightKey)

Test if leftKey is equal to rightKey. Either or both may be null. This method is necessary because you must use == when leftKey or rightKey are null, but you must use the equals method when both are not null. (Recall that null has no methods.)

public boolean isIn(Key key)

Search the association list for a Node whose key slot equals the key parameter according to isEqual. Return true if you find such a Node, and return false otherwise.

public void put(Key key, Value value)

Search the association list for a Node whose key slot equals the key parameter, according to isEqual. Change the value slot of that Node to be the value parameter. If there is no such Node, then add a new Node immediately after the head node. The new Nodes key slot is the key parameter, and its value slot is the value parameter.

-------------------------------TESTS.JAVA------------------------

class Hogwarts { // MAIN. Make an instance of ASSOCIATION LIST and test it. public static void main(String[] args) { AssociationList list = new AssociationList(); System.out.println(list.isIn(null)); // false 2 points. try { System.out.println(list.get(null)); } catch (IllegalArgumentException ignore) { System.out.println("No null"); // No null 2 points. } list.put(null, "Wormtail"); list.put("Ron", "Lavender"); list.put("Voldemort", null); list.put("Dean", "Ginny"); System.out.println(list.isIn("Dean")); // true 2 points. System.out.println(list.isIn("Ginny")); // false 2 points. System.out.println(list.isIn("Ron")); // true 2 points. System.out.println(list.isIn("Voldemort")); // true 2 points. System.out.println(list.isIn(null)); // true 2 points. System.out.println(list.isIn("Joanne")); // false 2 points. System.out.println(list.get("Ron")); // Lavender 2 points. System.out.println(list.get("Dean")); // Ginny 2 points. System.out.println(list.get("Voldemort")); // null 2 points. System.out.println(list.get(null)); // Wormtail 2 points. try { System.out.println(list.get("Joanne")); } catch (IllegalArgumentException ignore) { System.out.println("No Joanne"); // No Joanne 2 points. } list.delete(null); System.out.println(list.isIn(null)); // false 2 points. list.put(null, null); list.put("Harry", "Ginny"); list.put("Ron", "Hermione"); System.out.println(list.isIn(null)); // true 2 points. System.out.println(list.get(null)); // null 2 points. System.out.println(list.get("Harry")); // Ginny 2 points. System.out.println(list.get("Dean")); // Ginny 2 points. System.out.println(list.get("Ron")); // Hermione 2 points. list.delete("Dean"); try { System.out.println(list.get("Dean")); } catch (IllegalArgumentException ignore) { System.out.println("No Dean"); // No Dean 2 points. } } }