Fortress of Solitude

Our First Data Structure

So far we’ve learned how to create objects of different types and manipulate those objects. Now we will study how to store objects in a large collection. In many programming languages, entities such as data structures are created in order to hold a list of objects. There exist several different kinds of data structures, each with its own specific purpose. Different circumstances require different data structures. The first data structure we will study is called the ArrayList.

ArrayList - a data structure that contains a list of elements, all of type E, stored with an index reference from 0 to n-1, where n is the size of the ArrayList. Unlike the array, a close cousin of the ArrayList, there is no limit to the capacity. The following are a few major points about ArrayLists:

• An ArrayList automatically expands as data is added.
• Access to any element of an ArrayList is O(1). Insertions and deletions are O(N).
• An ArrayList has methods for inserting, deleting, and searching.
• An ArrayList can be traversed using a foreach loop, iterators, or indexes.

Creating an ArrayList

Not The Simple Object Instantiation

We’ve learned that in order to instantiate a class into an object, we need to follow a two step process: declare the object as a variable and initialize it with the class’ constructor, like so:

SmileyFace mySmiley = new SmileyFace();

Well, ArrayList is also a class. In fact, it is a class found in the Java library. So in order to use the ArrayList data structure, we will need to include this line at the top of whichever program we may use this:

import java.util.ArrayList;

Now that we have imported the class, we can create an object of the ArrayList class. This class however is different because it is a generic data structure; that is, the class is built to handle and store any type of object, as long as all objects inserted into the ArrayList are of the same type. In order to use the ArrayList, the type must be specified at instantiation. We specify this using angle braces:

ArrayList<String> myList = new ArrayList<String>();

Inserting Into ArrayLists

The add Method

The ArrayList class comes equiped with an add method that allows you to insert an object into the ArrayList. There are in fact two add methods, each taking a different number of parameters. This is known as overloading.

• add(E element);
  This method requires an object of type E passed in as the parameter, where E represents the type of object accepted by the ArrayList. The method then inserts the object into the first available position.

  String myString = “Hello World!”;
  myList.add(myString);

• add(E element, int index);

  This method requires an object of type E passed in as one of the two parameters, where E represents the type of object accepted by the ArrayList. It also requires the second parameter to be an integer representing the index position where the object shall be added.

  String myString = “Hello World!”;
  myList.add(myString, 5);

An ArrayList automatically expands as data is added. Remember, unlike an array, there is no limitation on size besides the system’s available memory. When an ArrayList reaches its capacity, it doubles the size of its capacity and continues inserting new data.

Removing From ArrayLists

The remove Method

The ArrayList class comes equiped with a remove method that allows you to remove objects from an ArrayList. This method takes one parameter, an integer representation of the position of the object in the ArrayList. When an object is removed, all the subsequent elements are shifted over one.

• remove(int index);
  This method requires an integer representing the index position where the object is currently located.

  int pos = 5;
  myList.remove(pos);

Retrieving From ArrayLists

The get Method

The ArrayList class comes equiped with a get method that allows you to retrieve objects from an ArrayList. This method takes one parameter, an integer representation of the position of the object in the ArrayList. Since this method is an accessor method, it will return an object of type E, where E is the type of objects stored by the ArrayList.

• get(int index);
  This method requires an integer representing the index position where the object is currently located.

  String myString;
  int pos = 5;
  myString = myList.get(pos);

Traversing ArrayLists

The For-Each Loop

When we discussed loops, I mentioned a type of loop called a For Each loop. This loop is different from every other loop because it takes an ArrayList and iterates through each objects stored in the ArrayList. The block of code is executed for each object. We will now example how this loop might work with an ArrayList.

The basic structure of a For Each loop follows:

for (Object o : someArrayList)
{
     statement

}

Let us examine how a For Each loop might work with an ArrayList of Strings.

// Construct a new ArrayList of Strings
ArrayList≶String> myList = new ArrayList≶String>();

// Add String objects to ArrayList
myList.add(”hello,”);
myList.add(”i”);
myList.add(”heart”);
myList.add(”java!”);

// Iterate Through ArrayList
for(String myString : myList)
{
    System.out.print(myString.toUpperCase() + ” “);
}

The code above should print out something like this in the console window.

HELLO, I HEART JAVA!