Lab 6: Resizing Arrays & Exam Review

Before You Begin

Open up IntelliJ and import the lab folder that came with the skeleton. Repeat the Project Setup steps from Lab 4 Setup and don’t forget to import the javalib libraries!

In this lab, you will learn about array-based lists, in contrast to the linked lists we’ve seen so far. This lab is designed to be a bit shorter than usual to give you the opportunity to ask any questions about the exam in lab.

Read Arrays, Chapter 2.4 of the online textbook.

Most of this information shouldn’t be too new as we’ve worked with arrays as part of the Java introduction assignment, labs from last week, and also in the project. Revisit those assignments for more practice.

The appendix has a few important pointers for students who are familiar with array-like structures in other languages.

Compared to arrays in other languages, Java arrays:

Have no special syntax for “slicing” (such as in Python).

Cannot be shrunk or expanded (such as in Ruby).

Do not have member methods (such as in Javascript).

Must contain values only of the same type (unlike Python).

If you’ve taken CS 61A or Data 8 before, it’s important to separate arrays from lists in Python. As we’ll learn more about in this lab, they’re fundamentally different structures. The most important difference is that arrays have a fixed size determined when the array is first initialized, whereas lists can contain as many items as desired.

Resizing Arrays

Read The AList, Chapter 2.5 of the online textbook.

All of the exercises in this chapter are optional. While solutions are included in the textbook, we recommend thinking through each of the questions on your own first before checking the answer.

For this lab, we will be making a few additional improvements to the final version of AList presented in the textbook (with resizing and generic types).

Exercise: `add`

We’ve supplied you with a two-argument add method already, but it has a bug. Discuss the code with your partner until you’re both satisfied you understand the bug. If you’re having trouble finding it, try writing some tests!

Then, fix the two-argument add method so that it works properly. If the index is not in the range of the list, your program can do anything (including error out).

Exercise: `contains`

Implement contains, which returns true if the list contains the given item.

Remember that Item is a generic type, and generic types are always reference types. To check if two objects are equal, use .equals rather than ==.

Exercise: `remove`

Implement remove, which requires maintaining the list’s invariants. Make sure that your implementation avoids ‘loitering’ by leaving around unused references to removed objects.

Once you’re done, congrats! We’ve implemented a simple version of an ArrayList.

Recap: Resizing Arrays

Arrays

Recall that variables are just boxes of bits. For example, int x; gives us a memory box of 32 bits. Arrays are a special object which consists of a numbered sequence of memory boxes! To get the i-th item of array A, use A[i]. The length of an array cannot change, and all the elements of the array must be of the same type (this is different from a Python list). The boxes are zero-indexed, meaning that for a list with N elements, the first element is at A[0] and the last element is at A[N - 1]. Unlike regular classes, arrays do not have methods! Arrays do have a length variable though.

Instantiating Arrays

There are three valid notations for creating arrays. The first way specifies the size of the array, and fills the array with default values:

int[] y = new int[3];

The second and third ways fill up the array with specific values.

int[] x = new int[]{1, 2, 3, 4, 5};
int[] w = {1, 2, 3, 4, 5};

We can set a value in an array by using array indexing. For example, we can say A[3] = 4;. This will access the fourth element of array A and sets the value at that box to 4.

Arraycopy

In order to make a copy of an array, we can use System.arraycopy. It takes 5 parameters; the syntax is hard to memorize, so we suggest using online references and adding it to your course notes for quick reference.

2D Arrays

We can declare multidimensional arrays. For 2D integer arrays, we use the syntax:

  int[][] array = new int[4][];

This creates an array that holds integer arrays. Note that we have to manually create the inner arrays like follows:

  array[0] = new int[]{0, 1, 2, 3};

Java can also create multidemensional arrays with the inner arrays created automatically. To do this, use the syntax:

  int[][] array = new int[4][4];

We can also use the following notation to get arrays with specific values.

  int[][] array = new int[][]{ {1}, {1, 2}, {1, 2, 3} };

Arrays vs. Classes

Both are used to organize a bunch of memory.
Both have a fixed number of “boxes”.
Arrays are accessed via square bracket notation. Classes are accessed via dot notation.
Elements in the array must be all be the same type. Elements in a class may be of different types.
Array indices are computed at runtime. We cannot compute class member variable names.

Lists vs. Arrays

Our DLList has a drawback. Getting the ith item is slow; we have to scan through each item in the list, starting from the beginning or the end, until we reach the ith item. For an array named A, however, we can quickly access the ith item using bracket notation, A[i]. Thus, our goal is to implement a list with an array.

AList

The AList will have the same API has our DLList, meaning it will have the same methods as DLList (addLast(), getLast(), removeLast(), and get(int i)). The AList will also have a size variable that tracks its size.

AList Invariants

There are a few invariants for our AList.

addLast: The next item we want to add, will go into position size.
getLast: The item we want to return is in position size - 1.
size: The number of items in the list should be size.

Implementing AList

Each AList has an int[] called items.

For addLast, we place our item in items[size].
For getLast, we simply return items[size - 1].
For removeLast, we simply decrement size (we don’t need to change items). Thus, if addLast is called next, it simply overwrites the old value, because size was decremented. However, it is good practice to null out objects when they are removed, as this will save memory.

Notice how closely these methods were related to the invariants.

Abstraction

One key idea of this course is that the implementation details can be hidden away from the users. For example, a user may want to use a list, but we, as implementers, can give them any implementation of a list, as long as it meets their specifications. A user should have no knowledge of the inner workings of our list.

Array Resizing

When the array gets too full, we can resize the array. However, we have learned that array size cannot change. The solution is, instead, to create a new array of a larger size, then copy our old array values to the new array. Now, we have all of our old values, but we have more space to add items.

Resizing Speed

In the lecture video, we started off resizing the array by one more each time we hit our array size limit. This turns out to be extremely slow, because copying the array over to the new array means we have to perform the copy operation for each item. The worst part is, since we only resized by one extra box, if we choose to add another item, we have to do this again each time we add to the array.

Improving Resize Performance

Instead of adding by an extra box, we can instead create a new array with size * FACTOR items, where FACTOR could be any number, like 2 for example. We will discuss why this is fast later in the course.

Downsizing Array Size

What happens if we have a 1 million length array, but we remove 990,000 elements of the array? Well, similarly, we can downsize our array by creating an array of half the size, if we reach 250,000 elements, for example. Again, we will discuss this more rigorously later in the course.

Aside: Breaking Code Up

Sometimes, we write large methods that do multiple things. A better way is to break our large methods up into many smaller methods. One advantage of this is that we can test our code in parts.

Generic AList

Last time, we discussed how to make a generic DLList. We can do something similar for AList. But we find that we error out on array creation. Our problem is that generic arrays are not allowed in Java. Instead, we will change the line:

items = new Item[100];

to:

items = (Item[]) new Object[100];

This is called a cast, and we will learn about it in the future.

Exam Review

The remainder of the lab is optional exam review and there is nothing to turn in for this portion. We’ve included a number of suggested practice resources on the Midterm 1 Exam information page, so look there for review material, as well as Piazza!

If you haven’t already given it a read, the Exam Studying Guide is also a highly recommended resource.