Arrays and ArrayLists

Table that shows the relationship between
values in Arrays/ArrayLists and their indicies

Arrays and ArrayLists are extremely powerful data structures that can be used to store large collections of data. The main point of these two data structures it to store multiple variables of the same type, referenced by one central object. Arrays or ArrayLists can be used to replace a large amount of variables. For example you can either have int x1, x2, x3 …; or int[] x = new int[100]; The main similarity between arrays and ArrayLists are that they are both 0-indexed, meaning the first element can be referenced with 0. Their main difference is that the size of an array is immutable, but the size of an ArrayList can be changed dynamically. Arrays are almost always faster than ArrayLists.

Arrays

Arrays can be declared with any type, primitive and non primitive as in the following code example:


int[] x = new int[10]; // Valid
Integer[] x = new Integer[10] // Also valid

Arrays have a length public final variable attached to their reference that can be used to get the array’s length, so it does not need to be stored separately. This is different to other programming languages such as C where you have to store the length of the array. Just because arrays have a final variable, that does not mean that they are instances of a class (there’s a reason the Arrays class exists after all).

Arrays can be more complex than just one list of numbers you can have higher dimensional storage containers. However it is important when looping through the array with a basic for loop to take the length of the current higher array as in the following example:


// Assume x is a 3d array ie. int[][][] x;
for (int i = 0; i < x.length; i++)
	for (int j = 0; j < x[i].length; j++)
		for (int k = 0; k < x[i][j].length; k++)
			/* do something */

It is imperative that you do not make the following common mistakes:


// Assume x is a 3d array ie. int[][][] x;
for (int i = 0; i < x.length; i++)
	for (int j = 0; j < x[0].length; j++)
		for (int k = 0; k < x[0][0].length; k++)
			/* do something */

This is a mistake because Java supports ragged arrays, meaning arrays of different lengths, and thus you cannot be certain that the array is a perfect shape.

ArrayLists

ArrayLists are extremely similar to arrays, however their size is dynamic right from the start. ArrayLists can only be declared with objects, not primitives meaning you cannot have an int ArrayList but you can have an Integer ArrayList. ArrayLists can be declared as follows:


ArrayList<String> words = new ArrayList<String>();
// or
ArrayList<String> words = new ArrayList<String>(100);

In the first declaration words is not declared with a starting capacity, but in the second one the words is initialized to have a capacity of 100. If no capacity is specified, the capacity is 10. The capacity is not too relevant as if you run out of capacity (aka the ArrayList is filled) as the ArrayList will then double its capacity.

ArrayLists have a large amount of instance methods. Here is a table showing the most useful ArrayList methods and what they do (for the purposes of this table E represents the type the ArrayList was declared with):

Method	Summary
`.add(E x)`	Appends x to the ArrayList.
`.add(int i, E x)`	Inserts x into the ArrayList at index i.
`.get(int i)`	Returns the value of the item stored at index i.
`.remove(int i)`	Removes, and returns the item at index i. All other items are shifted if necessary.
`.set(int i, E x)`	Changes the value at index i to x.
`.size()`	Returns the current size of the ArrayList (Number of spaces filled, NOT capacity).

Example

Example Files
CountingCards.java
input.in

One very useful Array and ArrayList problem we had during the course was the counting cards problem. In this problem we had to validate that specific hand was valid for a card game. You can see example usage of an ArrayList in the main program of the section, and example usage and manipulation of a 2D array is used to validate that someone doesn’t have more than 1 of the same cards.