Please complete skeleton code

3.1 Task A: Implement the Dictionary and Its Operations Using Array, Linked List, and Trie (12 marks) In this task, you will implement a dictionary of English words that allows Add, Search, Delete, and Auto-completion, using three different data structures: Array (Python’s list), Linked List, and Trie. Each implementation should support the following operations: • Build a dictionary from a list of words and frequencies: create a dictionary that stores words and frequencies taken from a given list. This operation is not tested. • (A)dd a word and its frequency to the dictionary. Return True if successful or False if it already exists in the dictionary. • (S)earch for a word in a dictionary and return its frequency. Return 0 if not found. 4 • (D)elete a word from the dictionary. Returns True if successful and False if it doesn’t exist in the dictionary. • (AC)Auto-complete a given string and return a list of three most frequent words (if any) in the dictionary that have the string as a prefix. The list can be empty.

from dictionary.word_frequency import WordFrequency

# -------------------------------------------------

# Base class for dictionary implementations. DON'T CHANGE THIS FILE.

#

# __author__ = 'Son Hoang Dau'

# __copyright__ = 'Copyright 2022, RMIT University'

# -------------------------------------------------

class BaseDictionary:

def build_dictionary(self, words_frequencies: [WordFrequency]):

"""

construct the data structure to store nodes

@param words_frequencies: list of (word, frequency) to be stored

"""

pass

def search(self, word: str) -> int:

"""

search for a word

@param word: the word to be searched

@return: frequency > 0 if found and 0 if NOT found

"""

pass

def add_word_frequency(self, word_frequency: WordFrequency) -> bool:

"""

add a word and its frequency to the dictionary

@param word_frequency: (word, frequency) to be added

@return: True whether succeeded, False when word is already in the dictionary

"""

pass

def delete_word(self, word: str) -> bool:

"""

delete a word from the dictionary

@param word: word to be deleted

@return: whether succeeded, e.g. return False when point not found

"""

pass

def autocomplete(self, prefix_word: str) -> [WordFrequency]:

"""

return a list of 3 most-frequent words in the dictionary that have 'prefix_word' as a prefix

@param prefix_word: word to be autocompleted

@return: a list (could be empty) of (at most) 3 most-frequent words with prefix 'prefix_word'

"""

pass