Lab 16: Cyclic Lists
Intro
You’ll work in this lab with your lab partners.
The two of you will work as a team to solve problems. At any time, one of you will be the Head and the other will be the Hands. The Head does the thinking and the Hands does the typing. Hands type only what the Head tells them to, but you’re free to discuss any issues that pop up. You should switch off during the lab to make sure each of you get practice problem solving, dealing with syntax, and getting finger exercises on the keyboard.
You can start this lab with this project skeleton. In it you’ll find an IntelliJ project with two Java files: Listof.java and Lab16.java. You’ll be editing both files during this lab.
Recall
We’ve been learning about mutable and cyclic data structures in lecture. In this lab we’re going to focus on writing operations on cyclic lists.
Here’s an example of a standard singly-linked list:
+-----------+ +-----------+ +-----------+ +----+ |
| first = 1 | -->| first = 2 | -->| first = 3 | -->| Mt | |
| rest------+--/ | rest------+--/ | rest------+--/ +----+ |
+-----------+ +-----------+ +-----------+ |
The rest field points to the next cell in the list, which eventually reaches its way to an empty list. Let’s see what it takes to handle operations on lists that look like the following:
+-----------+ +-----------+ +-----------+ |
| first = 1 | -->| first = 2 | -->| first = 3 | |
| rest------+--/ | rest------+--/ | rest------+--\ |
+-----------+ +-----------+ +-----------+ | |
^ / |
\ / |
-------------------------------------------/ |
First, A Note on Equality
Equality is a subtle subject in computer science. Most of you have probably noticed that Java includes two main equality operations: the equals method and the operator ==. These don’t always act as you would expect or hope.
Ex 1: Do you expect this test to pass or fail? Uncomment this test in Lab16.java after you’ve talked it over with your partner.
Integer one = 1; |
Integer otherOne = 1; |
t.checkExpect(one == otherOne, ???); |
Ex 2: What about this test?
Integer oneThousand = 1000; |
Integer otherOneThousand = 1000; |
// t.checkExpect(oneThousand == otherOneThousand, ???); |
The salient detail here is that the operator == tests for referential equality. It tells you whether two objects are identical in memory. Java caches small ([-128, 127]) integer objects, which is why (1 == 1) but (1000 != 1000).
Knowing whether two objects are referentially equal can be useful, for example, when trying to identify a cycle in a list.
Identifying Cycles
The list implementation in Listof.java implements a few operations that work fine on regular lists. However, these operations will loop forever if we try to apply them to cyclic lists.
Ex 3: Uncomment and run the four tests on the cyclic list in Lab16.java to confirm they loop forever.
In Listof.java you’ll see the already implemented methods isCyclic and isCyclicHelper.
// In the interface: |
// Is this list a cyclic list? |
Boolean isCyclic(); |
Boolean isCyclicHelper(Cons<X> head); |
|
// In Mt: |
public Boolean isCyclic() { return false; } |
public Boolean isCyclicHelper(Cons<X> head) { return false; } |
|
// In Cons: |
public Boolean isCyclic() { |
return rest.isCyclicHelper(this); |
} |
|
public Boolean isCyclicHelper(Cons<X> head) { |
if (head == this) { |
return true; |
} else { |
return this.rest.isCyclicHelper(head); |
} |
} |
Note that if a list contains an empty list, it cannot contain a cycle. In the Cons case, the method isCyclic passes isCyclicHelper the head of the list, and we recur. If we find the head of the list again, we know we have a cyclic list.
Operations on Cyclic Lists
Each of these operations already work on non-cyclic lists. Extend them with a helper method that maintains a pointer to the head of the list like isCyclic to make them work on cyclic lists as well.
Ex 4: Implement the method length using lengthHelper to ensure termination for cyclic lists.
Ex 5: Implement the method contains using containsHelper to ensure termination for cyclic lists.
Ex 6: Implement the method foldr using foldrHelper to ensure termination for cyclic lists.
Ex 7: Reimplement the methods length, contains using foldr to ensure termination for cyclic lists.