Study problems related to Lab 9.

  1. Consider implementing OrderedListMap using a doubly linked list with sentinals (dummy nodes) head and tail.
    1. What property do you want head and tail to have with respect to a key of type K, so that there are no special cases for insertion or deletion?
    2. Write a helper method that performs comparsion for a node (head, tail, or otherwise) and a key of type K. The method should model compareTo, but take in the aforementioned objects and take into account the relation between head, tail and any possible key value.
  2. What are the advantages of implementing OrderedListMap with a CircularList?
  3. Consider a binary search tree for Strings. Given the following String>s, what order of insertion of those strings creates The strings are: