Dictionary Mini-Lab Using Data Structures for a Dictionary Application
By Sandino Vargas-Pérez, edited by Pamela Cutter, Alyce Brady

---

Consider the task of implementing a Data Structure that holds all of the entries in a Dictionary of Synonyms and Antonyms. This structure will be composed by Entry objects. The Entry object contains the KEY or word and its synonyms and antonyms, SYN and ANT, respectively, like this:

KEY: justice
SYN: impartiality, fairness, right, reasonableness, propriety, uprightness…
ANT: injustice, partiality, unfairness, unreasonableness, unlawfulness…

Choosing a Data Structure

The main operation of this structure will be searching: Given a word, return whether the word exists or not. If the word exists, then also return its synonyms and antonyms. A secondary operation will be adding new words to the dictionary or removing deprecated ones. Given all the ADTs discussed during the quarter (Arrays, ArrayLists, LinkedLists, Queues and Stacks, Binary Trees, BSTs, Minheaps, HashMaps, HashSets, HashTables), choose the one you considered to be the most appropriate for the task.

Think About:

• Whether or not it will be a good fit to use it as the underlying data structure of the Dictionary of Synonyms and Antonyms.
• How Java implements this data structure and its operations (from what you can gather from the documentation or Internet forums).
• Building the structure (how would you implement the dictionary using the particular data structure).
• Time complexity of searching for a given word, adding or removing words.
• Efficiency in terms of memory space for the data structure.