Implementing ArrayIntList

ed Lesson

Table of contents

• Classes and objects
• Implementing objects
• this instance
• Printing an ArrayIntList
• Clearing an ArrayIntList
• Style
• Private fields

Classes and objects

In most of CSE 142, we developed Java programs inside of a large class that represented a fully-functional program. In CSE 143, we’ll shift towards a different use for classes: as a template for a type of objects. The ArrayList class provides a template for list objects.

Objects combine data and behavior. For example, the final example of our list contained the data, “According to all known laws of aviation” and the behavior of being able to add or remove elements from the list. We saw how clients and implementers can view the same list in two different ways.

This idea of separation between the client and the implementer is known as abstraction.

Abstraction

Think about a radio. Have you used a radio before, such as one in a car? Many of us have interacted with radios or other technology such as computers. But have you built a radio from scratch before? This is much more complicated.

This analogy is similar to the distinction between clients and implementers. As clients of a radio, we know how to use a radio but not necessarily how to build one. This is part of what makes a radio actually useful. If everyone who ever wanted to use a radio needed to learn exactly how a radio functions just to use one, radios would never have been broadly accessible to a large audience.

In this course, we’ll explore both the client and implementer perspectives of Java collections.

Implementing objects

In this lesson, we’ll implement an ArrayIntList from scratch. We might start with the following code.

Implementer

public class ArrayIntList {
    // Constructs an empty list
    public ArrayIntList() {
        elementData = new int[10];
        size = 0;
    }
}

One way to fix the code so that it compiles is to add the variable types to the lefthand side of each assignment statement.

Implementer

public class ArrayIntList {
    // Constructs an empty list
    public ArrayIntList() {
        int[] elementData = new int[10];
        int size = 0;
    }
}

This brings up a different issue. If we want to implement an add method, then it won’t be able to access the elementData or size. (In fact, both of these variables disappear the moment the program leaves the constructor because the variables are declared within the constructor.)

Fields

To address this, we declare fields inside the class but outside of any particular method. Fields are variables that are associated with an individual object. This way, any method in the ArrayIntList class can access the elementData or size variables.

Implementer

public class ArrayIntList {
    int[] elementData = new int[10];
    int size = 0;

    // Constructs an empty list
    public ArrayIntList() { }
}

However, there’s a style issue with this code. Say we want to allow the user to specify the length of elementData. Assigning int[] elementData = new int[10] results in every ArrayIntList object starting with an elementData with capacity for 10 elements.

Instead, we prefer to declare fields in the class but initialize them in the constructors.

Implementer

public class ArrayIntList {
    int[] elementData;
    int size;

    // Constructs an empty list
    public ArrayIntList() {
        elementData = new int[10];
        size = 0;
    }

    // Constructs an empty list with the given capacity
    public ArrayIntList(int capacity) {
        elementData = new int[capacity];
        size = 0;
    }
}

External brain example

As an example of how this section might contribute to your external brain, here’s a list of steps for writing a new Java class. As you complete the rest of this lesson, update this example with new rules and insights that you discover.

1. Create a new Java file named after the class. Inside the file, write, public class [class name] { ... }.
2. Declare fields at the top of the class. (What are fields, and how do they relate to classes and objects?)
3. Define one or more constructors that assign values to each field. Write, public [class name]([constructor args]) { ... } for each constructor.

this instance

When there are multiple instances of a class like list1 and list2, Java determines which one you’re referring to with the help of a secret variable called this. The following implementation of the add method actually uses this even though the code doesn’t say so.

Implementer

public class ArrayIntList {
    int[] elementData;
    int size;

    // appends the given value to the end of the list
    public void add(int value) {
        elementData[size] = value;
        size++;
    }
}

Java knows to reference the current instance’s elementData and size by automatically adding the special variable this before parameters and variables that aren’t declared in the method. The above implementation can be rewritten to include this to make reveal what Java is doing behind the scenes.

Implementer

public class ArrayIntList {
    int[] elementData;
    int size;

    // appends the given value to the end of the list
    public void add(int value) {
        this.elementData[this.size] = value;
        this.size++;
    }
}

When list1.add(1) is evaluated, the add method is called with this as list1. When list2.add(2) is evaluated, the add method is called with this as list2.

These two programs are functionally equivalent. We don’t really consider one version to be better style than the other. What’s important is to pick a rule and stick with it.

Printing an ArrayIntList

In order to view the contents of our ArrayIntList, we had to print out all of the elements individually.

Client

ArrayIntList list = new ArrayIntList();
list.add(1);
list.add(97);
System.out.println(
    "["
    + list.elementData[0] + ", "
    + list.elementData[1]
    + "]"
);

While printing each element in elementData works, this is inconvenient for clients (users) of the ArrayIntList class since they need to know the implementation details of ArrayIntList. This is also unsafe since clients might accidentally print out elements that are not contained in the list. Using the same code to print an empty list will lead to unexpected results.

Client

ArrayIntList list = new ArrayIntList();
System.out.println(
    "["
    + list.elementData[0] + ", "
    + list.elementData[1]
    + "]"
);

This prints out [0, 0] since the default value for each int element in the elementData is 0. Unfortunately, printing out the list variable won’t work.

Client

ArrayIntList list = new ArrayIntList();
System.out.println(list);

What actually prints to the console is ArrayIntList@1f89ab83. Thanks, Java!

How println works

When we attempt to print our ArrayIntList object, Java calls its toString() method to get a string representation of the object to print to the console. But we haven’t implemented a toString() method for our ArrayIntList class, so Java calls the default toString() method for objects instead. The default method is responsible for returning the seemingly random output above.

Next, we’ll learn how to override Java’s default toString() method so that printing an ArrayIntList results in a more helpful output.

Clearing an ArrayIntList

It would be nice for clients to be able to completely clear their ArrayIntList rather than having to create a new ArrayIntList object every time they need an empty list. Java’s ArrayList<E> has a clear() method with this exact behavior.

One way to implement clear() is to remember that the elementData in an ArrayIntList object is initially filled with the default value of 0.

Implementer

public void clear() {
    for (int i = 0; i < size; i++) {
        elementData[i] = 0;
    }
    size = 0;
}

This works just fine, but do we really need all of that looping? Remember, size is what controls the client’s view of ArrayIntList.

As implementers, we never rely on any values in elementData outside of the range of 0 <= index < size since the client can’t view or interact with them. For example, anything that is beyond that range of values will be overwritten by the add method. We can now implement clear() more concisely and more efficiently with just a single line of code.

Implementer

public void clear() {
    size = 0;
}

Style

Programming languages communicate algorithms to other people, not the computer. We study computer programming in Java not because it’s the fastest language (it’s not), not because it’s the most well-designed language (it’s not), but primarily because Java is a programming language understood by many other people.

The readability and understandability of code is an important property of a program. Style is a way to describe what makes code easy (or hard) to understand. But every software development organization has its own unique style guidelines. The important skill for us to learn is how to adapt our code to meet particular style guidelines.

Documenting code

Every method needs to have a descriptive comment about its behavior without including implementation details. It would not be useful for the user of a radio to read the manual only for it to say:

If you turn this knob, it changes the electromagnetic signal in this way, which then causes this change…

The goal of documenting code is to describe what happens without going into detail about how. We document code by adding comments above the method header. Here’s a first try at documenting the add method.

Implementer

// Adds a value at index size in elementData and increments size
public void add(int value) {
    elementData[size] = value;
    size++;
}

Here’s another try at documenting the add method.

Implementer

// Adds a value to the list
public void add(int value) {
    elementData[size] = value;
    size++;
}

This comment addresses the problem of going into too much detail. But we might want to improve it by specifying that the value is added to the end of the list: “Adds a value to the end of the list.”

Later, we’ll study a bad ArrayIntList implementation and identify all of the style issues.

Private fields

There’s a big problem with our ArrayIntList class right now. Since fields are just variables, the client can modify the fields!

Client

ArrayIntList list = new ArrayIntList();
list.size = -8;

Every engineering artifact has certain conditions of operation. For example, personal devices such as laptops and smartphones come with warranties. These warranties are broken when unauthorized changes are made to the device.

In programming, this idea of preventing unauthorized changes to the fields of an object is known as encapsulation. Declare fields private so that they can only be accessed and modified by the implementing class.

Implementer

public class ArrayIntList {
    private int[] elementData;
    private int size;

    ...
}

The client code from the first example will no longer compile since it cannot modify the size field. But it also prevents the client from accessing the size as well, so they can no longer know the size of the list. There’s no special Java keyword for making fields read-only.

Getters and setters

Instead, Java programmers often define simple methods known as getters and setters to control field access and modification. We can implement a getter method for the size field by defining a new method getSize() or simply size().

Implementer

public class ArrayIntList {
    private int[] elementData;
    private int size;

    public int size() {
        return size;
    }

    ...
}

This allows the client to get the size of the list by calling the size() method rather than accessing the private size field.

Client

ArrayIntList list = new ArrayIntList();
int currentSize = list.size();
currentSize += 1;

An important getter method for lists is the get method that returns the element at a given index.

Implementer

public class ArrayIntList {
    private int[] elementData;
    private int size;

    public int get(int index) {
        return elementData[index];
    }

    ...
}