Dictionaries and Keyed Dictionaries

Question 1

What is a dictionary?

Answer 1

A type of container ADT which supports certain operations

Question 2

What type of operations can a dictionary support?

Answer 2

• insert(x)
• deleteItem()
• search(x)- set the current item in the container to be x
• obtain(x)- get the item that matches item x
• delete(x)-delete the item that matches item x
• insert(x)-insert the item x into the container
• Supports a cursor, which can only be affected by using search()

*Note that deleteItem() can only remove the current item, whereas delete(X) can remove any arbitrary item x

Question 3

What are keyed dictionaries?

Answer 3

Keyed dictionaries are dictionaries that can store items with a special property called a key that is used as an identifier for a section of the dictionary

Question 4

Why do we need keyed data for keyed dictionaries?

Answer 4

To use compound data with dictionary ADTs that have efficient search capabilities, we need to be able to tell whether one compound data item is larger or smaller than
another

Question 5

List Keyed Dictionary Operations

Answer 5

• obtain(k) — get the entire item that has key k
• delete(k) — remove from the container the item that has key k
• has(k) — test whether the container has an item with key k
• search(k) — position the cursor at the item with key k
• setItem(x) — If the item at the cursor and x have the same key, replace the item at the cursor
  with x

Question 6

What is the main advantage of a keyed dictionary?

Answer 6

Can search for and delete items from the dictionary with knowledge of only the item’s key, rather than the entire item