AMap is a type of collection that associates a key with a value. The mapping of keys to values can be accomplished using different underlying data structures. In this three-part assignment, you will be working with two such data structures and then using them to implement aMap. One is called aLinked List and the other is called aTree.

In part II, you will be implementing a Map that uses your Linked List to store its entries. It's important to remember that the LinkedList should handle its own nodes and data.Your Map should only use the LinkedList by calling its methods. It should not touch inner variables like head or tail or create node objects itself. That is the LinkedList's job to do internally.

Since the key-value pairs stored in the map could be of any type, we will be usingGenerics to implement all our classes. For example, we could have < "Andrew", 1> as a key-value pair (which is of type ) and we could also have < 432, 34> as a key-value pair (which is of type ). Hence, it is important that we provide a way to reuse the same code with different inputs.Generics enabletypes (classes and interfaces) to be parameters when defining classes, interfaces and methods. Much like the more familiarformal parametersused in method declarations, type parameters provide a way for you to re-use the same code with different inputs. The difference is that the inputs to formal parameters are values, while the inputs to type parameters are types.

Note: You areNOT allowed to use any built-in Java data structures for any part of this assignment.

What is a Map?

A map associateskeys withvalues, treating them as akey/value pair. Keys must be unique within the map, so there should be no duplicate keys in a map at any time. Values may or may not be unique. Information is stored in the map by providing a key/value pair, and is looked up by providing the key. There is no concept of indexing in the map and the data's ordering is not guaranteed by the definition of a map. When the same key is given for a new value in the map, it may change the value associated with that key or simply not store the new pair, based on the method that was used.

Program and Starter Code

You are being provided with starter code which is an interface representing aMap. It contains the signatures of the methods that you need to implement. It also contains aninner class to represent anEntry in theMap. Do not changeMap.java.

LinkedList.java

IMPORTANT: You may need to modify your LinkedList methods such as get(Object), contains(Object), and remove(Object) to compare the node's value to the object parameter, and not the other way around.This will allow your map to look things up by using only thekey portion of the data. So if you have a variablenode that you are comparing to the parametero, you should callnode.value.equals(o) rather thano.equals(node.value).

LinkedMap.java inner class Entry

You will need to createLinkedMap.java. It will declare a classLinkedMap, (declared aspublic class LinkedMap implements Map .) When you begin writing the LinkedMap class, you will first need to define its own inner classEntry (declared aspublic class Entryimplements Map.Entry .) It will need to implement the following methods:

public Entry( K key, V value )

The constructor for Entry. It should initialize any necessary fields.

public K getKey()

Returns this entry's key.

public V getValue()

Returns this entry's value.

public String toString()

Returns a string representation of this Entry. It should follow this format:(key, value)

public boolean equals( Object o )

Compares an objecto to this entry. If the object is anEntry (you can detect this usingo instanceof Entry), first casto to a variable of typeEntry, then return whether its key and value both match this entry's key and value. Otherwise, return whethero equals this entry's key.

LinkedMap.java

Your LinkedMap class should use an instance variable of type LinkedList to store its entries. Note that LinkedMap should only call methods from LinkedList,LinkedMap should not edit the LinkedList's nodes directly. You have to implement the following methods for theLinkedMap class:

public LinkedMap( )

The constructor for LinkedMap. It should initialize any necessary fields.

public LinkedList> getList()

Returns the LinkedList being used by this map.Mostly used for testing purposes.

public V put( K key, V value )

Associates the given key with the given value in the map. Should not add duplicate items to the map (items with the same key.) If the map previously contained a mapping for the key, the old value is replaced by the specified value.

public V putIfAbsent( K key, V value )

If the specified key is not already associated with a value (or is mapped to null) associates it with the given value and returns null, else returns the current value.

public String toString()

Returns a string representation of this LinkedMap. It should be in this format:

[(key1, val1), (key2, val2), (key3, val3)]

public void clear( )

Removes all of the elements from this map.

public V get( K key )

Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.

public boolean containsKey( K key )

Returns true if this map contains a mapping for the specified key.

public boolean isEmpty( )

Returns true if this map contains no elements, false otherwise.

public V remove( K key )

Removes the mapping for a key from this map if it is present. Returns the value to which this map previously associated the key, or null if the map contained no mapping for the key.

public int size( )

Returns the number of elements in this map.

public static void main( String[] args )

Provides a user interface for creating and manipulating a Map ofStrings toIntegers. Includes a command for each of the methods above.It should exit when a user enters the commandx.

Command	Method
p	put( K key, V value )
P	putIfAbsent( K key, V value )
c	containsKey( K key )
C	clear()
g	get( K key )
s	size()
e	isEmpty()
r	remove( K key )

Example transcript:

p word 100

[(word, 100)]

------------------

p word 100

[(word, 100)]

------------------

p another 2

[(word, 100), (another, 2)]

------------------

P word -1

[(word, 100), (another, 2)]

------------------

p word -1

[(word, -1), (another, 2)]

------------------

c word

true

------------------

c not

false

------------------

e

false

------------------

s

2

------------------

g word

-1

------------------

g not

null

------------------

r word

[(another, 2)]

------------------

C

[]

------------------

e

true

------------------

s

0

------------------

x

/** * Specification for a Map ADT. * @author Shubham Chatterjee * @version 03/07/2019 * @param <K> Key type * @param <V> Value type */ public interface Map { /** * Removes all of the mappings from this map. * The map will be empty after this call returns. */ void clear(); /** * Returns true if this map contains a mapping for the specified key. * @param key key whose presence in this map is to be tested * @return true if this map contains a mapping for the specified key */ boolean containsKey(K key); /** * Returns the value to which the specified key is mapped, * or null if this map contains no mapping for the key. * If this map permits null values, then a return value of null does not necessarily indicate * that the map contains no mapping for the key; * it's also possible that the map explicitly maps the key to null. * The Map#containsKey operation may be used to distinguish these two cases. * @param key the key whose associated value is to be returned * @return the value to which the specified key is mapped, * or null if this map contains no mapping for the key */ V get(K key); /** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, * the old value is replaced by the specified value. * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with key, or null if there was * no mapping for key. * (A null return can also indicate that the map previously associated * null with key, if the implementation supports null values.) */ V put(K key, V value); /** * If the specified key is not already associated with a value * (or is mapped to null) associates it with the given value and * returns null, else returns the current value. * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with key, or null if there * was no mapping for key. * (A null return can also indicate that the map previously associated * null with key, * if the implementation supports null values.) */ V putIfAbsent(K key, V value); /** * Returns true if this map contains no key-value mappings. * @return true if this map contains no key-value mappings */ boolean isEmpty(); /** * Removes the mapping for a key from this map if it is present. * Returns the value to which this map previously associated the key, * or null if the map contained no mapping for the key. * If this map permits null values, then a return value of null does not necessarily indicate * that the map contained no mapping for the key; * it's also possible that the map explicitly mapped the key to null. * The map will not contain a mapping for the specified key once the call returns. * @param key key whose mapping is to be removed from the map * @return the previous value associated with key, or null if there was no mapping for key. */ V remove(K key); /** * Returns the number of key-value mappings in this map. * @return the number of key-value mappings in this map */ int size(); /** * Specification of an entry in the map. * @param <K> Key type * @param <V> Value type */ interface Entry { /** * Returns the key corresponding to this entry. * @return the key corresponding to this entry */ K getKey(); /** * Returns the value corresponding to this entry. * @return the value corresponding to this entry */ V getValue(); }/** * Specification for a List ADT. * @author Shubham Chatterjee * @version 04/05/2019 * @param <T> Type */ public abstract class List { /** * Appends the specified value to the end of this list. * * @param value T The value to add * @return boolean True if the value is inserted, false otherwise */ abstract boolean add(T value); /** * Inserts the specified value at the specified position in this list. * * @param index Integer The index at which to insert * @param value T The value to insert */ abstract void add(int index, T value); /** * Removes all of the elements from this list. */ abstract void clear(); /** * Returns true if this list contains the specified element. * * @param t T The element to check if present in the list * @return boolean */ abstract boolean contains(T t); /** * Returns the element at the specified position in this list. * * @param index Integer The index at which to insert * @return T */ abstract T get(int index); /** * Removes the element at the specified position in this list. * Returns the element from the list or null if index is invalid. * * @param index the index of the element to be removed * @return the element previously at the specified position or null */ /** * Get the list entry corresponding to the value provided in the parameter. * @param o to search for * @return T matching data in the list */ abstract T get(Object o); abstract T remove(int index); /** * Removes the first occurrence of the specified element from this * list, if it is present. * If this list does not contain the element, it is unchanged. * Returns true if this list contained the specified element * (or equivalently, if this list changed as a result of the call). * * @param t element to be removed from this list, if present * @return true if this list contained the specified element */ abstract boolean remove(T t); /** * Returns true if this list contains no elements. * * @return true if this list contains no elements */ abstract boolean isEmpty(); /** * Returns the number of elements in this list. * @return int */ abstract int size(); /** * Inner class to represent a List node. */ public class Node { T value; Node prev; Node next; /** * Constructor. * * @param value V The value */ public Node(T value) { this.value = value; this.prev = null; this.next = null; } /** * Set the value of this node. * @param value Value */ public void setValue(T value) { this.value = value; } } }