A. Intro

Obtaning the Files

There's no new code for this lab. We'll be modifying the AbstractListNode class from last lab. We recommend creating a new Eclipse project for this lab named lab10 and copying AbstractListNode.java into it. Be sure to check "Use project folder as root for sources and class files." when creating a new project.

Learning Goals for Today

In the last lab, you worked with some basic list operations. Here we'll be working with more. First we'll consider non-destructive operations, that is, operations that when operating on a list actually return a whole new list, rather than changing the original. These operations, while useful, involve copying, and copying can be expensive. So, today we'll also consider destructive list operations, which instead modify the list they're called on. Some of the activities in earlier labs involved keeping close track of pointers and what they point to; this lab has more of the same.

B. Static list processing methods

Exercise: A Smallest-element Method

In the previous lab, you coded several useful methods for dealing with lists. For lists whose items implement the Comparable interface, methods that return the largest and smallest list item would also be useful.

One way to find the smallest item in a list uses a helper function that keeps track of the smallest item seen so far.

• Make a copy of AbstractListNode and put it in your lab10 project. Change the type of list elements in AbstractListNode, NonemptyListNode and EmptyListNode from Object to Comparable. (This means that any Objects stored in myItem will need to implement Comparable methods that you will be able to take advantage of).

• Copy the min method below into your class. Also, add the smallest method below into the AbstractListNode class, and complete it.

  public Comparable smallest() {
    if (isEmpty()) {
      throw new NoSuchElementException("Can't find smallest in empty list.");
    }
    return _____ ;
  }
  
  public Comparable smallestHelper(Comparable smallestSoFar) {
    ...
  }
  
  public static Comparable min(Comparable c1, Comparable c2) {
    if (c1.compareTo(c2) < 0) {
      return c1;
    } else {
      return c2;
    }
  }

Some notes about the code:

• You will need to add: import java.util.NoSuchElementException;
• Eclipse will give you a warning that Comparable is a raw type. Don't worry about this.

Discussion: Why is min a Static Method?

In the above example, why was min a static method?

Helpful Static Helper Methods

A common design pattern we'll be using in this course is to make helper methods static. This can help us deal with null objects easier. It can also improve the clarity of our code if it promotes symmetry in how we treat our arguments.

How did your smallest code work? Did you find it awkward? Here's how we wrote our version, and it has smallestHelper as static. Compare this version to the non-static version you wrote.

public Comparable smallest() {
    if (isEmpty()) {
        throw new NoSuchElementException ("can't find smallest in empty list");
    }
    return smallestHelper(next(), item());
}

public static Comparable smallestHelper(AbstractListNode list, Comparable smallestSoFar) {
    if (list.isEmpty()) {
        return smallestSoFar;
    } else {
        return smallestHelper(list.next(), min(smallestSoFar, list.item()));
    }
}

C. More AbstractListNode methods

Exercise: add, append, and reverse Methods

Add the following three methods to AbstractListNode. You can choose whether you'd prefer to use abstract methods and implement the conrete versions in NonemptyListNode and EmptyListNode, or whether you'd prefer to add the methods to AbstractListNode directly.

We've put them in order of what we believe is easiest to hardest, but you may write them however you choose.

• Write an add method that, given a Comparable c as argument, returns the first node in a new list with the following properties: If this list has n elements, the returned list should have n + 1 elements. The first n elements should be the same as the first n elements of this list; the last element in the return list should be c.

This method should NOT modifiy the original list. Here's a method header,

    public AbstractListNode add (Comparable c){
        ...
    }

Here's a method to add to your JUnit tests from last lab.

public void testAdd() {
    AbstractListNode l1 = new EmptyListNode();
    AbstractListNode l2 = l1.add("a");
    assertEquals("( a )", l2.toString());
    AbstractListNode l3 = l2.add("b");
    assertEquals("( a b )", l3.toString());
    assertEquals("( a )", l2.toString());
}

• Next, write an append method that, given an AbstractListNode as input argument, returns a new list which is the result of concatenating the list represented by this and the list represented by the argument. For example, appending the list ( 4 5 6 ) to the list ( 1 2 3 ) should return the list ( 1 2 3 4 5 6 ). Creating this new list should not modify the original lists.

Here's a method header,

public AbstractListNode append(AbstractListNode list) {
    ...
}

Before you begin coding, write some JUnit tests. Be sure to cover at least the four below cases:

• this list is empty
• the argument is empty
• neither are empty
• the argument and this list remain the same.

Once you've written your JUnit tests, write the method.

• Finally, write JUnit tests for a reverse method that returns a copy of this list with the elements in reverse order. Then write the method. Here's a header,

  public AbstractListNode reverse() {
      ...
  }

D. Destructive list operations

A Source of Inefficiency

Three of the methods we coded in lab, add, append, and reverse, all made calls to new in the process of producing their answers, creating new Java objects. However, these calls can be wasteful when we don't mind modifying a data structure in place. Even though Java reclaims unused storage, the process of doing so takes time, and under some circumstances the effects of needlessly generating and reclaiming objects can be noticeable and even an efficiency bottleneck.

In the next few steps, we'll explore and evaluate the option of destructive list modification, that is, changing pointers without generating any new nodes.

Self-test: Nodes Generated for append

Here is our code for the append method.

public AbstractListNode append(AbstractListNode list) {
        return appendHelper(this, list);
}

private static AbstractListNode appendHelper(ListNode list1, ListNode list2) {
        if (list1.isEmpty()) {
            return list2;
        } else {
            return new NonemptyListNode(list1.item(), appendHelper(list1.next(), list2));
        }
}

How many calls to new are made as a result of the call list1.append(list2)? Choose one answer.

Destructive append

The call list3 = list1.append(list2) using the version of append that we coded behaved as shown below.

Before the call (non-destructive)

After the call

Our new append, which we are calling the destructive version of append, should instead produce the following:

Mutator Methods in AbstractListNode Class (and subclasses)

The code from the previous lab did not allow the myItem and myNext instance variables to be changed once initialized; every assignment to either variable came during the construction of a new AbstractListNode. With the addition of two public mutator methods, which we'll name setItem and setNext, we will be able to replace the myItem variable with a reference to any Object and replace myNext with a reference to any AbstractListNode.

In the next step, you'll discuss where these methods should be implemented.

Discussion: Declarations of setItem and setNext?

Should setItem and setNext be declared in the AbstractListNode class, the EmptyListNode class, the NonemptyListNode class, two of the classes, or all three of the classes?

There is more than one good answer, so explain why you made the judgment that you did. What are the advantages of your solution?

Exercise: The appendInPlace Method

If you haven't switched which partner is coding yet in this lab, switch now.

Write the appendInPlace method for AbstractListNode. It is given an AbstractListNode reference list2. There are two cases:

• If this list is empty, list2 is returned.
• If this list isn't empty, the myNext in its last NonemptyListNode is replaced by list2.

Here's a method header,

public AbstractListNode appendInPlace(AbstractListNode list2){
    ...
}

Here are some straightforward test cases to try.

public void testStraightforward() {

    AbstractListNode empty1 = new EmptyListNode();
    AbstractListNode empty2 = new EmptyListNode();

    empty1 = empty1.appendInPlace (empty2);

    assertEquals ("( )", empty1.toString());
    assertEquals ("( )", empty2.toString());

    AbstractListNode a = new NonemptyListNode("a");

    a = a.appendInPlace(empty1);

    assertEquals ("( a )", a.toString());
    assertEquals ("( )", empty1.toString());

    AbstractListNode b = new NonemptyListNode("b");
    AbstractListNode c = new NonemptyListNode("c");

    b = b.appendInPlace(c);

    assertEquals ("( b c )", b.toString());
    assertEquals ("( c )", c.toString());
}

Discussion: Why Can't appendInPlace be a void Method?

Why can't appendInPlace be void ? What would happen if the list were empty?

A Strange appendInPlace Test

Examine the following JUnit method. Draw box-and-arrow diagrams for the resulting structure, and check them with your neighbors. Then run the JUnit method to recheck your diagrams. If something isn't working out, ask yourself: is there a problem with your code, or is there a problem with this test?

public void testTrickyAppendInPlace() {

    AbstractListNode list1 = new EmptyListNode();
    AbstractListNode list2 = new NonemptyListNode ("a");

    list1 = list1.appendInPlace(list2);

    assertEquals ("( a )", list1.toString());
    assertEquals ("( a )", list2.toString());

    list2 = list2.appendInPlace(list1);

    assertEquals ("( a )", list1.toString());
    assertEquals ("( a a )", list2.toString());
}

More Practice

If you had trouble with today's lab activities, try writing the following methods for AbstractListNodes for extra practice (we're not describing each of these in detail, because no matter how you interpret the goal for the method it will be good pratice):

boolean contains1MoreThan(AbstractListNode otherList)
void removeMin()
void removeMax()
void remove(int index)
void insertInto(AbstractListNode otherList, int insertLocation)
void duplicateMax()
int calculateMean() // maybe only use any of the Objects that are Integers.
// Try to think of some more!

E. Merge

Merge Two Lists

Add to your AbstractListNode class a merge method. This method will take as input two (non-null, possibly empty) sorted linked lists of Integers and return the linked list that contains all elements from both input linked lists in sorted order:

public static AbstractListNode merge( AbstractListNode a, AbstractListNode b ) {
    // Fill this out
}

Your implementation should work destructively and should not create any new AbstractListNode objects. Given a list of size l and and a second list of size r, your method should take O(l + r) time. Some casting may be necessary.

Advice: This problem might be pretty tricky! If you find yourself getting stuck, drawing box-and-pointer diagrams of what your code is doing is highly recommended.

F. Conclusion and Submission

Summary

This lab (hopefully) made you wary of using destructive list operations unless you really need the benefits in efficiency they provide.

This lab should also should have given you more practice with tracing through code that involves the use of pointers. Query your partner to figure out how to do this most productively.

Submission

Submit AbstractListNode.java for lab as lab10. We will be checking to make sure that your code meets our timing efficiency standards from part 3.

In addition, please fill out this self-reflection form before this lab is due, as a part of your homework assignment. Self-reflection forms are to be completed individually, not in partnership.