Lab 10: More Linked Lists; Destructive List Manipulation

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.

Some notes about the code:

Discussion: Why is min a Static Method?

Link to the discussion

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.

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());
}

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:

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

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.

list1.size ( ) - 1
Incorrect. Count carefully!
list1.size ( ) + 1
Incorrect. Count carefully!
list1.size ( ) + list2.size ( )
Incorrect. Notice that the list we create includes list2 without copying it.
list2.size ( )
Incorrect. Notice that the list we create includes list2 without copying it.
list1.size ( )
Correct! We don't need to make any new nodes for list2 , but we create all new nodes for each non-empty node in list .
Check Solution

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)

append1

After the call

append2

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

append3

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?

Link to the discussion

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:

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?

Link to the discussion

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.