This assignment is based on an ADT called dictionary. A dictionary is a collection of records. Each record consists of a unique key in the whole collection and a value associated with the key. Each record is formed from a pair of key and value, called key- value pair. The notation of the key-value pair is . Hence, the notation of a dictionary is < , , >.

The source code archive attached with this description document provides the following java source code:

File Name	Content Description
ADTDictionary.java	Dictionary ADT as in Java interface
ALDictionary.java	Java class of dictionary ADT implementation using the array-based list
DictionaryJUnitTest.java	JUnit 5 test case of any dictionary ADT implementation. This is optional to your convenience to test.
DictionaryManualTest.java	A Java program to test any dictionary ADT implementation without using JUnit 5. This is optional to your convenience to test.
tf02802349_win32.xltx	Warehouse inventory data samples

The source code package has already provided an example of how the dictionary ADT is implemented using array-based list. The test case Java program using JUnit 5 or without JUnit 5 is also provided to test any implementation. You can choose either DictionaryManualTest.java or DictionaryJUnitTest.java to test your programs.

Problem 3(a) (10 marks) Given above example Java code, please further program a double list-based dictionary implementation.

Problem 3(b). (6 marks) Use the asymptotic analysis to analyze the (1) best case, (2) average case, and (3) worst case time cost of each method implementation of Problem 3.(a) Please fill in the table in the answer sheet.

Asymptotic Analysis for Double List-based Dictionary

Operation	Best cast time cost	Worst case time cost	Average case time cost
clear
insert
remove
removeAny
find
size