CMUQ 15-121 ArrayList



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:

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 be adding and removing items. 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.

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:

  1. You should be able to add items to it.
  2. You should be able to remove items from it.
  3. You should be able to access items that are it.
  4. 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("");
        
    }
    
}