Study problems related to Lab 9.
- Consider implementing OrderedListMap using a doubly linked
list with sentinals (dummy nodes) head and tail.
- 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?
- 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.
- What are the advantages of implementing OrderedListMap with
- Consider a binary search tree for Strings. Given
the following String>s, what order of insertion of those
The strings are:
- a completely unbalanced tree?
- a balanced tree?