CSE131 Module 8: List Structures

Goals

After completing this module, you should be able to... NOTE: To make the goals more concrete, I have written them in terms of what you should be able to do (as opposed to what you should know or understand). This should help you understand expectations, and provide a more concrete way for you to check your progress.


Practice Problems

Expect exercises like these on the quiz. There will be a help session covering these exercises on Wednesday at 10:00am in the Steinberg 105 lecture hall. You will benefit most by doing the exercises before you look at the solutions or attend the Wednesday help session when they will be discussed.

Directions: Consider the following class definition (as presented in lecture) and then answer the questions below.

class ListItem {
   public int number;
   public ListItem next;

   ListItem(int number, ListItem next) {
      this.number = number;
      this.next = next;
   }

   public String toString() {
      if (next == null)
         return "" + number;
      else
         return number + " " + next;
   }
}

  1. Carefully draw an object and reference diagram corresponding to the result of executing the following code. If an object is "shared" by two or more lists, draw it only once with multiple arrows pointing to it. Remember that Java evaluates expressions left to right, but always evaluates parameters before making a procedure call.
    
    ListItem a, b, c, d;
    a = new ListItem(1,null);
    b = new ListItem(2,null);
    b.next = a;
    c = new ListItem(3,b);
    d = new ListItem(4, new ListItem(5, new ListItem(6, b)));
    c = c.next;
    
    System.out.println("a = (" + a + ")");
    System.out.println("b = (" + b + ")");
    System.out.println("c = (" + c + ")");
    System.out.println("d = (" + d + ")");
    
    

  2. What output would be printed as the result of executing the code given in Problem 1?

  3. A ListItem object (as defined above) is stored in memory as two contiguous memory cells (contiguous means that they are consecutive, one immediately following the other). The first cell of the object corresponds to the number being held by the ListItem, and the second cell contains the memory address of the next ListItem. Draw an object and reference diagram for ListItems being held in the following memory. There are two lists, one starting at memory location 112, and the other starting at memory location 104. In memory, the null value is represented as 0.

    Memory AddressMemory Contents
    100107
    1010
    102112
    103116
    104134
    105118
    106109
    107100
    108103
    109114
    110116
    111106
    112111
    113102
    114116
    1150
    116122
    117114
    1180
    119110

  4. In problem 3, which memory locations are not used in either list?

  5. Suppose we store the value 118 into memory location 117. Now what would the object and reference diagram look like? Now which memory locations are not used in either list?

  6. Assuming that memory locations are allocated in order starting from address 200, draw a memory table like the one in Problem 3 that would result at the end of the execution of the code in Problem 1. Which memory locations are not used in any of the lists?


Downloads

Download lab8.zip and import it into your CSE131 project in Eclipse.

IMPORTANT: Do not modify the provided toString method in the ListItem class, since our automated tests depend on the specific formatting it produces.


Project: Linked List Manipulation

In Module 6, you used the LinkedList class as an abstraction to represent the coefficients of polynomials. However, the internal representation was encapsulated within each LinkedList object and you operated on it only in terms of the methods in the List interface. In this lab, you will be working with directly with "raw" list structure, using references to traverse lists and manipulating references to change the structure of lists.
  1. In the file ListItem.java, write methods for the ListItem class that satisfisfy the following specifications. In each case, be sure to use recursion or iteration as specified. Where not indicated, you may choose either approach. Create JUnit test cases that thoroughly test all of your methods.

    Hints: Draw lots of pictures before writing any code. Try small examples and hand simulate how your algorithm will work. Use small lists for testing in JUnit so you can draw the corresponding pictures. Then, if things don't work as expected, use the debugger to examine the list structure itself in memory. To do this, set a breakpoint at a line in the test case where you want the debugger to pause. Then, choose "debug as" instead of "run as" in Eclipse. Use the "step over" and "step into" methods to single step through the code, and examine the list structure in the "variables" view by opening up the "next" references to see what they refer to.

    1. A recursive method duplicate that takes no parameters and returns a new ListItem that begins a list containing the same numbers (but not the same ListItem objects) as the original list. (We did this one in class, but try to do it without looking at your notes.)

    2. A recursive method length that takes no parameters and returns the number of elements in the list. For example, the list (3 5 9 3 2 4) would have length 6.

    3. An iterative method stretch that takes a positive number n as a parameter and returns a new ListItem beginning a list in which each of the numbers in the original list is repeated n times. For example, if the original list is ( 6 7 6 9 ) and the parameter value is 2, then the new list returned is ( 6 6 7 7 6 6 9 9 ).

    4. A method find that takes an integer target and returns the first ListItem in the list that contains the given number. If the target does not occur in the list, then null is returned.

    5. A method max that returns the largest number in the list. Hint: You know that the maximum value must be at least as large as the number in the first ListItem.

  2. In the file ListItem.java, write static methods that satisfy the following specifications. Remember that static methods are called directly on the ListItem class itself, rather than on ListItem objects.

    Create JUnit tests to test each method thoroughly. To call static methods of the ListItem class from your JUnit test methods, you can specify the class name each time, as in ListItem.evenElements(ls). Alternatively, you can save characters and just write evenElements(ls) if you import the static methods from the ListItem class by adding the line
    import static lab8.ListItem.*;
    near the top of your file, after the package declaration.

    As you work through these exercises, be sure to use recursion or iteration as indicated. Where not indicated, you may choose either approach. Each method will take references to list items as parameters. Unless otherwise specified, you should handle the case of a null parameter value.

    1. A recursive procedure evenElements
      PARAMETERS:   a ListItem reference, ls
      RETURN VALUE: a ListItem at the beginning of a list structure
                    containing copies of the even numbers in given list.
                       for example, given input list ( 3 2 6 9 ), the
                       return value would be the list ( 2 6 )
      

    2. A recursive procedure pairwiseSum
      PARAMETERS:   two ListItem references, ls1 an ls2
      RETURN VALUE: a ListItem at the front of a new list containing the pairwise
                    sum of the elements in ls1 and ls2
                       for example, given lists ( 3 2 6 ) and ( 1 4 2), 
                       the return value would be the list ( 4 6 8 )
      
      You may assume that the given lists are the same length.

    3. An iterative procedure smallElements
      PARAMETERS:   a ListItem reference, ls
                    an integer n
      RETURN VALUE: a new list identical to the given list, except
                    that it contains no occurrences of numbers greater than n.
                    for example, given input list ( 3 2 6 3 4 ) and 3,
                       the return value would be the list ( 3 2 3 )
      

    4. An iterative procedure scale
      PARAMETERS:   a ListItem reference, ls
                    an integer n
      RETURN VALUE: none (void)
                    the procedure mutates the list by multiplying
                    each number in the list by the given number n.
                       for example, given input lists ( 3 2 6 3 4) and
                       the number 3,
                       the modified list would be ( 9 6 18 9 12 ).
      
    5. A procedure insertAfter
      PARAMETERS:   a ListItem reference, ls
                    two integers i and j (not equal)
      RETURN VALUE: none (void)
                    the procedure mutates the list by inserting the
                    given number i after each occurrence of j.
                       for example, given input lists ( 3 2 6 3 4) and
                       the number 5 and 3,
                       the modified list would be ( 3 5 2 6 3 5 4 ).
      
      Be sure to do this by creating new list items only for the inserted numbers. Modifying the next references in the existing ListItem objects to insert the new items in the right places. Don't create a whole new list structure.


Optional Extension: Reversing Lists

In the ListItem class, write methods with the following specifications, and write thorough JUnit tests to check that they work correctly.


What To Turn In:

Follow these submission instructions to turn in the following files. Be sure to demo your work in lab session.
  1. cover-page.txt -- Be sure to fill in all information.
  2. ListItem.java
  3. ListItemTest.java

Remember to adhere to the CSE131 Style Guide.


Kenneth J. Goldman