A. Introduction

Obtaining the Files

As usual, use git to pull your files from the skeleton repository.

Learning Goals for Today

This lab introduces you to the linked list, a data structure you may remember from CS 61A. Much like an array, the linked list stores sequential data using nodes; each node stores one item and a reference to the next node. The last node in a linked list has no next node, so it stores a reference to null instead.

It is possible to implement linked lists that store any type of data by using generics, which you will be learning about in detail in a later lab. For now, this lab will focus only on a Linked List that stores integers - an IntList, for which we have provided a template. In this lab you will implement some basic functional methods for this data structure; in the next lab you will implement some more finicky destructive and non-destructive methods.

Testing your code.

We have provided you with a suite of JUnit tests in IntListTest.java. To run the tests, either compile and run the test file or right click on it in IntelliJ and select Run 'IntListTest.java'. Afterward, you can select IntListTest on upper right corner of your IntelliJ and press the green button to run the tests again.

Tip: It is good practice to read the test code to be familiar with JUnit4, since you will soon be writing your own tests for future labs! We'll go more in depth on JUnit & testing in a later lab.

B. Introduction to Linked Lists

Linked List Introduction

In the next two labs we're going to be working with the linked list. A linked list is similar to an array in that it also stores sequential data, but different operations have different runtimes between linked lists and arrays. Since different problems call for different efficient operations, choosing the right data structure is an important design choice for an engineer, and we'll study this as we go through the course.

Here's a picture of a simple implementation of a linked list that contains the items "A", "B", and "C" (can you draw the corresponding picture for an array that stores these items?). A linked list consists of nodes that are chained together. Here we represent nodes with a generic class ListNode. Each node contains an item called item. As you can see, the items form a sequence. In this example, the linked list items are Strings, though our linked list will contain ints instead, just like int[] array.

A Straightforward Implementation of a Linked List

Here's an implementation of an IntList which could easily be generalized to store different types of data. Notice how it stores an item item and a reference to another node next.

    public class IntList {

        private int item;
        private IntList next;

        public IntList(int item, IntList next) {
            this.item = item;
            this.next = next;
        }

        public IntList(int item) {
            this(item, null);
        }

        public int item() {
            return item;
        }

        public IntList next() {
            return next;
        }

        public static IntList list(int... items) {

            /* Check for cases when we have no element given. */
            if (items.length == 0) {
                return null;
            }

            /* Create the first element. */
            IntList head = new IntList(items[0]);
            IntList last = head;

            /* Create rest of the list. */
            for (int i = 1; i < items.length; i++) {
                last.next = new IntList(items[i]);
                last = last.next;
            }

            return head;
        }
    }

For those of you who know Scheme, the implementation above is very similar to a Scheme list. Lists in Scheme are linked. Each cons pair is a node; the cdr is the link.

It is important that you feel comfortable with this code before moving on. You and your partner should try this on paper:

• Write code that uses the IntList class to make a list that represent the sequence (1, 2, 3) WITHOUT using the given list method.
• Draw a picture of the IntLists involved in the list (1, 2, 3).
• Read and understand IntList.list, a static utility method that is provided for you as a convenience. It takes a variable number of ints , creates a series of IntList objects that correspond to the given list, and returns the start of the list. Explain the code to your partner line by line.
• For a call to IntList.list(1, 2, 3, 4), draw an evolving box-and-pointer diagram following the line-by-line execution of the method.

Exercise: The get Method

Fill in the get method in the IntList class. get takes an int position as an argument, and returns the list element at the given (zero-indexed) position in the list. For example, if get(1) is called, you should return the second item in the list. If the position is out of range, get should throw IllegalArgumentException with an appropriate error message. Assume get is called on the first node in the list.

Test your code by running the provided JUnit tester. If your implementation is correct, you should pass the get method tests.

    public class IntList {
        public int get(int position) {
            ....
        }
    }

Self-test: Testing an Empty List

A CS 61B student suggests that the isEmpty method (tests whether the linked list contains no items) could be implemented as follows:

public class ListNode {

    private int item;
    private IntList next;

    public boolean isEmpty ( ) {
        return (this == null);
    }
    // ...
}

Will it return the correct answer (false when it is not empty and true when it is empty)?

If you get the answer wrong, try to write it in Java and test it.

Exercise: The size Method

Fill in the size method, which should return the number of elements in this list (namely, the length of the list). For the list (1, 2, 3, 4, 5), the size method should return 5.

Again, test your code using the JUnit test file we have provided.

    public class IntList {
        public int size() {
            ....
        }
    }

Exercise: The toString Method

The toString method for IntList returns the String representation of this list, namely:

1. a left parenthesis, followed by a blank,
2. followed by the String representation of the first element, followed by a blank,
3. followed by the String representation of the second element, followed by a blank,
4. ...
5. followed by a right parenthesis.

The list containing the Integer objects 1, 3, and 5 is represented by the string "( 1 3 5 )".

• Write the toString method and run the tests.

  public class IntList {
      public String toString() {
          ....
      }
  }

Hint: You can always add additional helper methods to help with recursion!

Exercise: The equals Method

Fill in the equals method. Given an Object as argument, this method returns true if this list and the argument list are the same length and store equal items in corresponding positions (determined by using the elements' equals method).

Test your code using the provided JUnit tester.

    public class IntList {
        public boolean equals(Object o) {
            ....
        }
    }

Hint: How would you check if the given object is of type IntList? Check the Java Documentation for a method if you're unsure.

Exercise: The add Method

Fill in the add method, which accepts an int as an argument and appends an IntList with that argument at the end of the list. For a list (1, 2, 3, 4, 5), calling add with 8 would result in the same list modified to (1, 2, 3, 4, 5, 8).

Test your code using the JUnit tests provided.

    public class IntList {
        public void add(int item) {
            ....
        }
    }

C. More Challenging IntList Operations

Exercise: The smallest Method

Implement the smallest method, which returns the smallest int that is stored in the list. For a list (6, 4, 3, 2, 3, 2, 2, 5, 999), a call to smallest would return 2.

    public class IntList {
        public int smallest() {
            ....
        }
    }

Hint: You can use Math.min method! Get into the habit of reading Java Documentation, as it will be invaluable for your projects.

Exercise: the squaredSum Method

Finally, implement the squaredSum method. As the name suggests, this method returns the sum of the squares of all elements in the list. For a list (1, 2, 3), squaredSum should return 1 + 4 + 9 = 14. Does this method remind you of a family of functions you learned about in CS 61A?

    public class IntList {
        public int squaredSum() {
            ....
        }
    }

These are called reducers. In a later lab as we learn how higher order functions can be used in Java, we'll see a way to generalize these operations.

D. Append

Destructive and Non-Destructive Functions

Suppose you have an IntList representing the list of integers (1, 2, 3, 4). You want to find the list that results from squaring every integer in your list, (1, 4, 9, 16).

There are two ways we could go about solving this problem. The first way is to traverse your existing IntList and actually change the items stored in your nodes. Such a method is called destructive, because it mutates (destroys) the original list. The following code snippet

IntList myList = IntList.list(1, 2, 3, 4);
IntList squaredList = IntList.destructiveSquare(myList);
System.out.println(myList);
System.out.println(squaredList);

would print

(1, 4, 9, 16)
(1, 4, 9, 16)

The second way is called non-destructive, because it returns an entirely new set of IntList nodes, allowing you to access both the original and returned lists. The following code snippet

IntList myList = IntList.list(1, 2, 3, 4);
IntList squaredList = IntList.nonDestructiveSquare(myList);
System.out.println(myList);
System.out.println(squaredList);

would print

(1, 2, 3, 4)
(1, 4, 9, 16)

In practice, one approach may be preferred over the other depending on the problem you are trying to solve.

Let's implement a non-destructive method.

Exercise: Implement append

Implement the non-destructive static method append that takes two IntList inputs, L1 and L2, and returns a new Intlist consisting of the elements in L1 followed by the elements in L2. It should not change either IntList.

E. Conclusion

Good job! Linked Lists and recursive operations should feel more familiar to you by now. The next lab will give you more difficult challenges dealing with IntLists!

Submission

Submit IntList.java with all the methods outlined in the exercises implemented. Make sure you pass all the JUnit tests!