CPSC 170 Lab 9: the Set ADT and Linked Structures

Introduction to Linked Structures

1. File TestList.java contains a simple program that uses the LinearNode class to create a 3-element linked list. Save these files to your directory, then compile and run TestList to see what it does.

   Now print out TestList.java and study the code. There are seven lines marked with numbers (//**** 1 ****, etc). For each of these lines, draw a diagram like those in Chapter 4 of the text showing front and temp and everything they refer to. Your diagrams should show the structures after the line executes. Draw the diagrams on the TestList printout.

2. Of course, it's silly to have separate code each time you put something on the front of the list. Modify TestList so that it reads a positive integer N from the user and uses a loop to create a list that holds the integers from N to 1. Add a node to the front of the list each time, as in the example, so the numbers will still be backwards in the list.
   
   
3. Notice that when we print the list, we are using a method called printList(front). This displays the entire list from the front until the end of the list.   Traversing the structure like this is a common operation - but we don't always want to move across the entire structure.  (Think back to our class discussions about searching or finding the nth entry).   To help us do this more generally, we can rely on an Iterator.   An iterator object allows us to keep track of the current location in the structure, and get the next available element (if there is one).   If you think about it, you have been using iterators since the early days of CS 120!   Where?
   
   
   
A Scanner implements the iterator interface - if you think of the input as a structure, you can ask the Scanner if there is more input (hasNext) and you can ask it to give you the next one (next).


• Open the file LinkedIterator.java and fill in the commented sections to complete this class.
• Alter the printList Method to create a LinkedIterator object that can traverse and print the list.
  


4. Suppose that  you wanted to add nodes to the end of a list, not the beginning. There are two standard strategies for this.

   • In the first strategy, each time you add to the end of the list you assign a temporary pointer to the front of the list and move it along until it reaches the last node. You know when it's at the end because the next field of the last node is null. Once you find the last node, you can change its next field to point to the new node.

     Copy TestList.java into TestList1.java and use this strategy to add each node to the end of the list instead of the beginning. Note that inside your loop that adds the nodes you'll need another loop to find the end of the list each time.

     What is the big-Oh complexity of adding a node this way? Write and explain your answer using comments at the top of the code.
     

   • In the second strategy, you keep a variable that you might call back that points to the end of the list. Since it always points to the last node, you can use it to add a new node to the end of the list -- just make the next field of the last node point to the new node, then make back point to the new node as well (so it still points to the last node).

     Copy TestList.java into TestList2.java and use this strategy to add each node to the end of the list instead of the beginning.

     What is the big-Oh complexity of adding a node this way? Write and explain your answer using comments at the top of the code.
     

An Array Based Set Implementation

1. Open TestSet.java and study it to understand how it works. Then compile and run it. Particularly note how the iterators are used to print the sets in table form. Could this be done using just the ArraySet toString method instead of using iterators? Explain how or why not using comments at the top of TestSet.java.
   
   
2. Add an intersection method to SetADT.java and ArraySet.java.  Like with the union method, this method should take a SetADT as a parameter and return a SetADT.     Then modify the TestSet program so that after it prints the union of the two sets it prints their intersection (neatly labeled, of course).
   
   
3. The equals method in the ArraySet class in the text is unnecessarily complicated. The code given would be needed if sets could contain duplicates, but they can't. For two sets to be equal, they must be the same size and every element in one set must be in the other set.  
   
   • Comment out the body of the equals method.
     
   • Rewrite and simplify the equals method to take advantage of the fact that sets cannot contain duplicates.  The new method should be significantly simpler (in terms of code) than the original.
   • Run TestSet again to be sure it still works. 
     
   • Just because we have made the code simpler does not necessarily impact the complexity of the execution in terms of Big-Oh.    Provide a Big-Oh analysis of the two approaches using comments in the equals method.
     
   
   
4. Open Sentences.java. Fill in the code as indicated by the comments so that the program sets up three sets of strings to hold subjects, verbs, and objects respectively. After it reads values for the sets (this code is already in place), it should do the following:
   
   
5. Use iterators to print the elements of each set.
   
   
6. Use removeRandom on each set to make random sentences, each of which uses a different randomly chosen subject, verb, and object. Repeat this until the sets are empty.

HAND IN:

• Turn in hardcopies of your code
• Tar your directory and email to me with cpsc170 lab0 in the Subject line.