CMUQ 15-121 ArrayList

1. Introduction
2. Side Note: Abstract Data Types vs. Data Structures
3. Our First Abstract Data Type: The List
4. The ArrayList
- 4.1. Important Methods
- 4.2. Usage

1. Introduction

So far, we have found ourselves using arrays to store most of our data. However, we have also noticed some limitations with arrays:

You need to know the maximum size when you allocate it.
You can’t change the size later.
If you over-allocate the array size and leave some empty spaces on the end of the array, then you need a separate integer to keep track of how many items are actually in the array. (This also renders the .length variable basically useless.)
If you remove an item from the array, then you need to “shift” all of the items that come after it, otherwise there are “holes” in the array.

Overall, an array is very useful if you know exactly how many items will be in it at all times, but it isn’t as useful when we want to add and remove items as needed. What what we would really like is a different kind of data structure that is similar to an array, but makes adding and removing items much easier.

2. Side Note: Abstract Data Types vs. Data Structures

Before we continue, we need to take a brief moment to define some terms. We’re getting ready to discuss a new data structure (that isn’t an array), but let’s clarify what we’ll be defining.

Abstract Data Type: An ADT is a formal description of the behavior of a data type. This means that an ADT is where we define what kind of operations we would like the data type to have.
Data Structure: A data structure is a concrete representation/organization/implementation of an ADT.

3. Our First Abstract Data Type: The List

We’ve already discussed the limitations of arrays (an array is a data structure), so let’s define the behavior of an ADT that would be good to replace them: The List. You are already somewhat familiar with lists because Python uses this data type natively.

Behaviors of a list:

You should be able to add items to it.
You should be able to remove items from it.
You should be able to access items that are it.
You should be able to determine how many items are in it.

If we consider these four behaviors of our list ADT, we actually notice that an array is an implementation of a List. It isn’t a very good one (because doing 1 and 2 is can be painful), but it is. What we would really like is a better implementation of this abstract data type.

4. The `ArrayList`

https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html

Java provides a lot of data structures that are lists. The first one we’ll talk about is the ArrayList. You can think of an ArrayList as a variable sized array that solves many of the problems of traditional arrays.

4.1. Important Methods

The full library description (follow the link above) lists a lot of methods, but here are some of the most important ones:

ArrayList Method	Description
`list.add(value)`	Adds value to the end of list
`list.add(index, value)`	Adds value at the specified index
`list.clear()`	Removes all elements from the list
`list.contains(value)`	Returns `true` if value is in the list and `false` otherwise
`list.get(index)`	Returns the element at index
`list.indexOf(value)`	Returns the first index of value, or -1 if value is not found
`list.isEmpty()`	Returns `true` if the list is empty and `false` otherwise
`list.remove(value)`	Removes the first occurrence of value
`list.remove(index)`	Remove the element at index and automatically moves other elements to remove holes
`list.set(index, value)`	Sets the element at index to value
`list.size()`	Returns the number of elements in list

As you can see, there’s a lot you can do with an ArrayList.

4.2. Usage

ArrayLists are declared with the type of item they’ll store:

ArrayList<Type> name = new ArrayList<Type>();

Take a look at this longer example that shows how to use an ArrayList of integers. Note that for the type of the ArrayList we use Integer instead of int. This is related to how Java represents the base types (such int, double, etc) internally.

import java.util.ArrayList;
import java.util.Random;

public class ArrayListDemo {

    public static void main(String[] args) {
        
        // Declare an ArrayList
        ArrayList<Integer> arr = new ArrayList<Integer>();
        
        // Put 10 random numbers in it
        Random r = new Random();
        for(int i = 0; i < 10; i++) {
            arr.add(r.nextInt(100));
        }
               
        // Print out the number of elements in arr
        System.out.println("There are " + arr.size() + " items in arr.");
        
        // Print out one item from arr
        System.out.println("The [2]'d item in arr is " + arr.get(2));
        
        // Print out the contents of arr using a traditional for-loop
        System.out.print("All the items in arr are: ");
        for(int i = 0; i < arr.size(); i++) {
            System.out.print(arr.get(i) + " ");
        }
        System.out.println("");
        
        // Print out the contents of arr using an alternative style for-loop
        System.out.print("All the items in arr are: ");
        for(int v: arr) {
            System.out.print(v + " ");
        }
        System.out.println("");
        
    }
    
}