Introduction

Exam 2 will cover mostly the data structures we have seen so far: singly linked list, doubly linked list, circular list, and binary tree.  The MVC design for GUI will not be covered.  This tutorial consists of a collection of exercises designed to reinforce your understanding of all the mutable linear recursive data structures we have studied so far:

• The singly-linked list structure and its algorithms as visitors (QFList)
• The doubly-linked list structure and its algorithms as visitors (DLListDriver, dllAlgoDoc, dllDoc, list)
• The circular doubly-linked list structure and its algorithms as visitors (Test Driver, Circular list Doc, Circular Visitor Doc, Circular List)
• The binary tree structure and its algorithms as visitors (Binary Tree Framework)

Exercises

1. Write a visitor called Trimmer to keep the first N elements of a list and disregard the rest.  If the list has less than N elements, leave the list unchanged.  Do this for each of the three kinds of lists.
   
   
2. Given L1, L2, both are QFList containing Integer objects sorted in ascending order.    Write a singleton visitor called Merge such the cal L1.execute (Merge.Singleton, L2) will result in L1 containing all of the elements of L1 and L2 before the operation, all in ascending order.  What happens to L2, we don't care! This part of the peril working with mutable lists.
   
   
3. The following is a description for "selection sort" on a list.  Assume the list contains Integer objects.
   Case list is empty: do nothing
   Case list is not empty:
       Find the minimum element of the list.
       Move it to the front of the list.
       Recur on the rest of the list.
   Implement selection sort on each of the three kinds of lists.  Hint: write a visitor to get the min and use  Integer.MAX_VALUE to simplify the code.
   
   
4. For the binary tree structure, write a visitor to return Boolean.TRUE if the host tree is a leaf, i.e. both if its subtrees are empty, Boolean.FALSE otherwise.  Write one version call LeafChecker1 that checks for emptiness of the subtrees.  Write another version called LeafChecker2 that does not check for the emptiness for the subtrees but passes appropriate information to the subtrees to get the job done.  Feel free to write helper visitors to help do the job.
   
   
5. Write a visitor to look up for an element in a binary search tree (BSTDeleter).   Assume the host tree contains Integer objects as discussed in class.  Return Boolean.TRUE if found, Boolean.FALSE if not found.