Dictionary ADT Flashcards
1
Q
What is the point of a dictionary ADT?
A
storing, inserting and removing entries for a collection
2
Q
Application of dictionaries?
A
word-definition search
credit card auth
3
Q
What distinguished a dictionary ADT from a map?
A
A dictionary allows for keys to have same key but diff value
4
Q
What is the runtime complexity of the insert and remove & find in the Dictionary ADT?
A
insert take O(1) because it is not inserted in any particular order.
remove & find takes o(n) as you have to search, possibly n elements to find the entry that you are looking for
5
Q
What are the 2 different ways that a dictionary can be implemented?
A
- List
2. Hash table that uses separate chaining as a collision handling strategy
6
Q
What is a search table?
A
A dictionary implemented with a sorted array
