# Immutable Lists -- Behavior and Implementation
## Motivating Question
How do we create classes and define methods for processing a list of elements?
## Conceptual Study Questions
- why are there separate classes for `NodeList` and `EmptyList`?
- why did we introduce the `AbsList` class?
- why do we say that this implementation of lists yields immutable lists?
- what's the pattern for writing a method to traverse/walk down a list?
## Motivating Question {#motivating-question .unnumbered}
How do we build immutable lists through Java classes and objects?
## What Does an Immutable List look like?
Everyone has now worked with both mutable and immutable lists. Let's start by looking again at Immutable lists, as you worked with either in 111/17/19 or as the `FuncList` class from the 15 track. Here's the same code in both of your notations:
```=java
// pyret/racket/immutable (for racket, link is the same as cons)
Limm = link(3, link(9, empty))
Limm2 = link(8, Limm)
// java FuncList/immutable
Limm = new FuncList.link(9).link(3);
Limm2 = Limm.link(8)
```
If we were to sketch out what's getting created here at a high level, it would look something like the following:
This is the right idea, but it's a bit sketchy. In order to create a chain of numbers like this, we need to create a class that stores a number and a reference (arrow) to whatever list comes next. We also need a class that captures the empty list (for when we reach the end). In pictures, we want to create:
Here are classes that do this. We need the `IList` interface so that the next item in the chain (which is usually called a "node") can be either an empty list or a sequence of more nodes.
```=java
public interface IList {}
public class EmptyList implements IList {
public EmptyList() {}
}
public class NodeList implements IList {}
int data;
IList next; // <--- this line requires us to make the interface
public NodeList(int data, IList next) {}
this.data = data;
this.next = next;
}
}
```
## Adding Basic Methods
Let's expand our interface to require some methods:
```=java
public interface IList {
public boolean isEmpty();
public NodeList addFirst(int newItem);
}
```
Here are the `Empty` and `NodeList` classes with these methods implemented.
```=java
public class EmptyList implements IList {
public EmptyList() {}
public boolean isEmpty { return true; }
public NodeList addFirst(int newItem) {
return new NodeList(newItem, this);
}
}
public class NodeList implements IList {}
int data;
IList next; // <--- this line requires us to make the interface
public NodeList(int data, IList next) {}
this.data = data;
this.next = next;
}
public boolean isEmpty { return false; }
public NodeList addFirst(int newItem) {
return new NodeList(newItem, this);
}
}
```
For `isEmpty`, each class returns the boolean corresponding to whether the list is empty. For `addFirst`, we create new `NodeList` object to hold the new element, and set the `next` field of that object to reference the list on which we called `addFirst`.
Why are we using `this` as the second argument to the `NodeList` constructor? Remember that when we call a method, `this` refers to the object on which the method was called. So if we call `Limm1.addFirst(8)`, then `this` refers to the same object as `Limm1` inside the body of `addFirst`. Thus, the new `NodeList` object refers to the list to which our code said to add a first element.
## Creating the AbsList abstract class
If we look closely, we might notice that the code for `addFirst` is exactly the same in both cases. This is precisely the situation in which we might create an abstract class (to hold that common code). Let's add that, and call it `AbsList`:
```=java
public abstract class AbsList implements IList {
public AbsList() {}
public NodeList addFirst(int newElt) {
return new NodeList(newElt, this);
}
}
public class EmptyList extends AbsList {
public EmptyList() {
super(); // set up the AbsList portion
}
public boolean isEmpty { return true; }
}
public class NodeList extends AbsList {}
int data;
IList next;
public NodeList(int data, IList next) {}
super(); // set up the AbsList portion
this.data = data;
this.next = next;
}
public boolean isEmpty { return false; }
}
```
In this code, we moved the `implements IList` up to the `AbsList` class as well, since it too was common to both classes. We could have left it on the individual classes however, without problem.
**Do we still need the `IList` interface once we have the abstract class?** Yes. We may want different implementations of `IList` (we'll do another one in a couple of days). The interface lets these different versions provide methods with the same name, but different implementation approaches under the hood.
## Methods that walk along the list
Now let's add a method to compute the length of the list. We extend the interface as follows:
```=java
public interface IList {
public boolean isEmpty();
public NodeList addFirst(int newItem);
public int length();
}
```
What should this method return? Let's write some assertions to work it out:
```=java
public class ListTest {
@Test
public void testLength() {
assert.assertEquals(0, new EmptyList());
assert.assertEquals(1, new EmptyList.addFirst(3));
assert.assertEquals(1, new EmptyList.addFirst(3).addFirst(8));
}
}
```
By writing tests up front, before we implement the methods, we accomplish two things. First, we make sure that we understand the method's inputs. Second, we make sure that we understand what the method *should* do; we can later confirm that it is what the method *does* do. As the problems in the course get more challenging, the assertions will become more useful for helping you think about the problem in advance.
With these in hand, let's implement the `length` method. For the `EmptyList` case, the method simply returns `0`:
```=java
public class EmptyList extends AbsList {
public int length { return 0; }
}
```
What about in the `NodeList` case? In this case, we have to compute the sum using the two pieces of information provided in the class fields: the `data` in the current object, and a reference to the rest of the list. Since the rest of the list is an `IList`, it too must have a `length` method. Hence, we can write:
```=java
public class NodeList extends AbsList {}
int data;
IList next;
public int length() {
return 1 + this.next.length();
}
}
```
This approach embraces the idea of object-oriented programming: we ask the `next` object to compute its length, then we add 1 to it to account for the current object.
Isn't this method recursive? Yes, it is. But the right way to think about this is not "should I write some method recursively", but rather "I should implement methods so that they call methods in other objects then combine the answers". We happen to get a recursive solution from doing that, but the adherence to OO programming principles is what actually matters here.
### An aside on private fields
Ideally, we should protect the `data` and `next` fields by marking them as private, as follows:
```=java
public class NodeList extends AbsList {}
private int data;
private IList next;
public int length() {
return 1 + this.next.length();
}
}
```
If we do this, the approach we took to `length` that calls on the `next` object to continue the computation, is really the only way to go.
(*Note: some of you with prior Java experience may have previously seen methods like `length` written using `while` loops (if you're coming from 111/17/19, you haven't seen those yet, so you can ignore this point). In order to do that, you need some outside variable that will refer to the nodes in turn, but `private` prevents you from doing that, unless you create unjustified getters.)*
## Adding a `contains` method
Let's look at one more example: a method that determines whether the list contains a particular element:
```=java
public boolean contains(int findElt);
```
In the `EmptyList` case, this method simply returns false. How do we think about this in the `NodeList` case? Again, think about how we might compute the result of `contains` by asking questions or doing computation on the `data` of a node object and the result of a method call on the `next` element. Here, we can say that a `NodeList` contains an element if either the element equals the data in the `NodeList` **or** the element is in the rest of the list via `next`:
```=java
public class NodeList extends AbsList {}
private int data;
private IList next;
public int length(int findElt) {
return (this.data == findElt) || this.next.contains(findElt);
}
}
```
## Wrap Up
In this lecture, we've seen how to use two classes and an interface (and an abstract class) to build our own implementation of immutable lists. The "immutable" part comes because we return a new `NodeList` object after adding items, rather than somehow modifying the existing `NodeList` (we'll see what that looks like next lecture).
We have also seen the pattern for writing methods that need to walk through a list: call the same method on the `next` field, and combine that result with the result on the `data` in the current node.
**Why are we even doing this when Java has `LinkedList` built in?** Java has mutable lists built in. Here. we are building immutable lists. In addition, there are educational benefits to knowing how lists are implemented, as there will be ideas here that you will use in later projects.