4. IntLists

Coming soon: This textbook chapter is incomplete, for more information see the Lecture 4 slides.

Now that we've truly understood the Mystery of the Walrus form Chapter 3, we're ready to build our own list class.

It turns out that a very basic list is trivial to implement, as shown below:

public class IntList {
    public int first;
    public IntList rest;        

    public IntList(int f, IntList r) {
        first = f;
        rest = r;
    }
}

You may remember something like this from 61a called a "Linked List".

Such a list is ugly to use. For example, if we want to make a list of the numbers 5, 10, and 15, we can either do:

IntList L = new IntList(5, null);
L.rest = new IntList(10, null);
L.rest.rest = new IntList(15, null);

Alternately, we could build our list backwards, yielding slightly nicer but harder to understand code:

IntList L = new IntList(15, null);
L = new IntList(10, L);
L = new IntList(5, L);

While you could in principle use the IntList to store any list of integers, the resulting code would be rather ugly and prone to errors. We'll adopt the usual object oriented programming strategy of adding helper methods to our class to perform basic tasks.

size and iterativeSize

We'd like to add a method size to the IntList class so that if you call L.size(), you get back the number of items in L.

Consider writing a size and iterativeSize method before reading the rest of this chapter. size should use recursion, and iterativeSize should not. You'll probably learn more by trying on your own before seeing how I do it. The two videos provide a live demonstration of how one might implement these methods.

My size method is as shown below:

/** Return the size of the list using... recursion! */
public int size() {
    if (rest == null) {
        return 1;
    }
    return 1 + this.rest.size();
}

The key thing to remember about recursive code is that you need a base case. In this situation, the most reasonable base case is that rest is null, which results in a size 1 list.

Exercise: You might wonder why we don't do something like if (this == null) return 0;. Why wouldn't this work?

Answer: Think about what happens when you call size. You are calling it on an object, for example L.size(). If L were null, then you would get a NullPointer error!

My iterativeSize method is as shown below. I recommend that when you write iterative data structure code that you use the name p to remind yourself that the variable is holding a pointer. You need that pointer because you can't reassign "this" in Java. The followups in this Stack Overflow Post offer a brief explanation as to why.

/** Return the size of the list using no recursion! */
public int iterativeSize() {
    IntList p = this;
    int totalSize = 0;
    while (p != null) {
        totalSize += 1;
        p = p.rest;
    }
    return totalSize;
}

get

While the size method lets us get the size of a list, we have no easy way of getting the ith element of the list.

Exercise: Write a method get(int i) that returns the ith item of the list. For example, if L is 5 -> 10 -> 15, then L.get(0) should return 5, L.get(1) should return 10, and L.get(2) should return 15. It doesn't matter how your code behaves for invalid i, either too big or too small.

For a solution, see the lecture video above or the lectureCode repository.

Note that the method we've written takes linear time! That is, if you have a list that is 1,000,000 items long, then getting the last item is going to take much longer than it would if we had a small list. We'll see an alternate way to implement a list that will avoid this problem in a future lecture.