Introduction

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)

In many applications, these strutures are used for storage and retrieval of data.   The exercises are about writing algorithms to perform various types of storage and retrieval tasks.  When writing an algorithm on a particular structure as a visitor, you are forced to break up the algorithm into one (or more) base case(s) (e.g. NullCase (...)), and one (or more recursive case(s) (e.g. NonNullCase (...)). This helps you think more clearly when dealing with recursion.  Also, you are forced to interact with the host data structure vai only its public methods.  This helps you think more in terms of high-level abstraction and not to concern yourself with the low-level implementation details.  Each of the exercises given below are to be done on all three data structures.

Exercises

1. Given an int n, write appropriate visitors to retrieve (not remove) the data object at the n-th position, with 0 being the first position.  Note that for doubly-linked lists, you have a choice of n-th position to the left or to the right.  Also for the circular linked lists, you have a choice of clockwise or counter clockwise.  Do all directions.
   
   
2. Given an int n, write appropriate visitors to remove and return (not retrieve) the data object at the n-th position, with 0 being the first position.  Note that for doubly-linked lists, you have a choice of n-th position to the left or to the right.   Also for the circular linked lists, you have a choice of clockwise or counter clockwise. Do all directions.
   
   
3. Suppose your lists contains Object data of various types: Boolean, Integer, String, etc.  Write appropriate visitors to remove and return the first Interger data object in the lists.   Note that for doubly-linked lists, you have a choice of first to the left or to the right.  Also for the circular linked lists, you have a choice of first clockwise or counter clockwise. Do all directions.  Hint: To compare objects' classes, use the method getClass () (see JPL page 304); for example, suppose you want to know if object a has the same class type as object b, call a.getClass ().equals (b.getClass ()). Your simulation project will need something like this.
   
   
4. Suppose your lists contains Integer data ordered in non-descending order (" current element is less or equal to next element").   Write appropriate visitors to insert a given Integer object into the lists in the appropriate order, with duplication allowed.  Note that for doubly-linked lists, you have a choice of inserting to the left or to the right.  Also for the circular linked lists, you have a choice of inserting clockwise or counter clockwise. Do all directions.