All you need to do is implementing three parts of this class:

1. The nested CacheNode class: This class encapsulates the building block of a cache node. It contains a key and value, as well as a reference to both the next and previous nodes in the list. K is a parametric (generic) type for the key and V is a parametric type for the value.

2. LRUGet(K key): This method returns the value for a given key in the cache and moves the node which contains the key to the end of the list (because it is most recently accessed). The method returns null if there is no node with the given key.

3. LRUPut(K key, V value): This method adds a new node with the given key and value to the end of the list. If the cache is full, the least recently used node (the first node after head) is removed to make room for new node. Since duplicate keys are not allowed, the method must first check to see if a node with a given key already exists in the cache and if so, it updates its value and move the node to the end of the list.

Please follow these guidelines when implementing your class:

1. Do not extend any of the data structure classes or interfaces I provided in the source code (doing so will be more trouble than it is worth). You do not need to use any other file beyond the provided LRULinkedCache.java file.

2. You can add any private helper method you want; but your code will be graded based on the LRUGet and LRUPut methods.

3. The LRULinkedCache.java in its current form is not compiled as its missing the implementations requested above. After you add your implementations you can compile and test your class. For example, if you use the following main method:

public static void main(String[] args) { LRULinkedCache cache = new LRULinkedCache(4); cache.LRUPut(1,5); System.out.println("cache after calling LRUPUT(1,5): "+ cache.toString()); cache.LRUPut(2, 2); System.out.println("cache after calling LRUPUT(2,2): "+ cache.toString()); cache.LRUPut(3, 7); System.out.println("cache after calling LRUPUT(3,7): "+ cache.toString()); cache.LRUPut(4, 9); System.out.println("cache after calling LRUPUT(4,9): "+ cache.toString()); cache.LRUPut(1,9); System.out.println("cache after calling LRUPUT(1,9): "+ cache.toString()); System.out.println("LRUGET(3) returned: " + cache.LRUGet(3)); System.out.println("cache after calling LRUGET(3): "+ cache.toString()); cache.LRUPut(5, 10); System.out.println("cache after calling LRUPUT(5,10): "+ cache.toString()); cache.LRUGet(4); System.out.println("LRUGET(4) returned: " + cache.LRUGet(4)); System.out.println("cache after calling LRUGet(4): "+ cache.toString()); cache.LRUGet(10); System.out.println("cache after calling LRUGet(10): "+ cache.toString());

}

Your program must produce the following output:

cache after calling LRUPUT (1,5): (1,5)

cache after calling LRUPUT (2,2): (1,5) (2,2)

cache after calling LRUPUT (3,7): (1,5) (2,2) (3,7)

cache after calling LRUPUT (4,9): (1,5) (2,2) (3,7) (4,9)

cache after calling LRUPUT (1,9): (2,2) (3,7) (4,9) (1,9)

LRUGET (3) returned: 7

cache after calling LRUPUT (3): (2,2) (4,9) (1,9) (3,7)

cache after calling LRUPUT (5,10): (4,9) (1,9) (3,7) (5,10)

LRUGET (4) returned: 9

cache after calling LRUPUT (4): (1,9) (3,7) (5,10) (4,9)

cache after calling LRUPUT (10): (1,9) (3,7) (5,10) (4,9)

Notice when LRUPput(1,9) is called, since a node with key=1 already exists in the cache, its value is updated to 9 and the node (1,9) is moved to the end of the list. When LRUGet(3) is called the value for key=3 is returned and the node (3,7) is moved to the end of the list.

When LRUPut(5,10) is called the cache has reached its capacity, so the least recently used node (2,2) is removed from the cache and (5,10) is added to the end of the list. When LRUGet(10) is called the cache is remained unchanged as there is no node with key=10 in the cache.

What you need to turn in:

1. Turn in your LRULinkedCache.java containing the implementations described aboveIn addition, you should submit an extra document explaining (Big-Oh) the time efficiency ofthe LRUPut and LRUGet method