• An Observation About Arrays:
  • Elements in an array must be "identified" using an int index
• One Example:
  • A (homogenous) collection of university students
  • Each student has a complicated ID number (like a Social Security Number) that either can't or shouldn't be represented as an int and aren't sequential
• Another Example:
  • A (homogeneous) collection of houses in a single city/town
  • Each house has a unique address that can be used to identify it, but this address is not an int

• Design an ADT that has array-like operations but can use an index of any type
• Consider the efficiency of different implementations of this ADT

Map

Values:	Homogeneous elements of any type
Operations:	Name/Operator Arguments Returns Constructor A new instance. put key The key/index of the element to add/insert value The value of the element to add/insert get key The key/index of the element to retrieve The value of the element with the given key/index

In addition, one could add an isEmpty() operation, an isFull() operation (if there is a size limit), a remove() operation, and a makeEmpty() operation.

• Use an array of keys and an array of values
• Use the integer index to "connect" the two arrays

• put():
  • If you keep track of the size then put() and allow duplicate keys, it can be \(O(1)\)
  • Otherwise, it is \(O(n)\)
• get():
  • Requires a \(O(n)\) search to find the key and a \(O(1)\) retrieval of the value

• Another Implementation:
  • One could sort the array of keys (simultaneously re-ordering the array of values)
• What Happens To:
  • put()?
  • get()?

• Can you use two lists (e.g. two linked lists) in place of the arrays?
• Can you use one array/list with "more complicated objects" as the elements