Espresso: A Concentrated Introduction to Java


Arrays and Vectors in Java

Summary: We consider one of the central building blocks for data structures: the Array. Arrays group values and permit fast access by numeric index. Vectors are a variant of arrays that also permit fast access by numeric index, but that can grow and shrink dynamically.

Prerequisites: Basics of Java. For loops. Parameterized classes.

Contents:

Background: Grouping Data

As you build larger and larger programs, you will soon find that you have many situations in which you need to group large amounts of similar data. For example, in a grading program, you may need to group students and, for each student, you may need to group grades. Because grouping data is at the center of so many programs, computer scientists study different ways to group data.

As you may have seen in the past, there are two initial approaches one can take. One can describe abstract data types (ADTs), which specify the what of data. That is, ADTs describe the overall philosophy of the collection of data and the primary methods that client algorithms and programs use to access the data. One can also focus on data structures, which specify the how of data. That is, data structures provide the implementation for the methods that ADTs describe.

Arrays play an odd role in this classification. From one perspective, we can think of them as ADTs, in that the design of arrays is guided by a central philosophy, and programmers usually rely on them to provide certain operations. However, from another perspective, arrays are implemented in a particular way, and many programmers take advantage of that implementation as they build other data structures. We will consider both aspects.

After considering arrays, which mix abstraction and implementation, we will then explore the built in Vector structure, which provides a more abstract version of the array.

Array Basics

We begin with the central philosophy of arrays: Arrays group similar kinds of values and allow clients to access those values by number. If we want to use specialized terminology, we say that arrays are homogenous, indexed, collections.

What operations do we expect to have for such a collection?

Because arrays are both simple and central, we also expect most of these operations to be comparatively quick (and, except for the case of creating a collection, to take an amount of time or computation independent of the number of values in the array).

To provide fast access to elements, most languages store arrays as a contiguous area of memory. If the array starts at memory location l, and each value in the array takes space s, and the indices start at 0, then the value in position i can be found at memory location l+is.

Syntax of Arrays in Java

In Java, arrays have a special syntax. In order to use arrays, you will need to mamster this syntax (and master it fairly quickly).

Type type of an array is specified by giving the type of the elements followed by an open square bracket and a close square bracket. So, , for example, the type of an array of integers is int[] and the type of an array of exceptions is Exception[].

We most typically construct an array with the new operator, followed by the type of each element, an open bracket, an integer that gives the size of the array, and a close bracket. To create an array of five integers called grades, we would write

int[] grades = new int[5];

Similarly, to create an array of ten objects in class Student, we would write

Student[] class = new Student[10];

We can also initialize an array during construction by eliding the array size and following the right bracket with a sequence of values separated by commas and surrounded by curly braces. For example, to create an array of the names Jane, Jack, Julie, and John, we would write

String[] names = new String[] { "Jane", "Jack", "Julie", "John" };

Similarly, to create an array of the grades 98, 78, 85, and 90, we would write

int[] grades = new int[] { 98, 78, 85, 90 };

When writing these array initializers, we might also construct objects within the braces. For example,

Fraction[] thirds = new Fraction[] { new Fraction("1/3"),
                                     new Fraction("2/3"),
                                     new Fraction("3/3"),
                                     new Fraction("4/3") };

To obtain the number of values in an array, we use the name of the array, followed by a period, followed by the keyword length. For example,

pen.println("There are " + students.length + " students.");

To get a particular value in the array, we use the name of the array, followed by an open bracket, followed by an expression that gives the index, followed by a close bracket. For example, here is some simple code to print all the fractions in the array of fractions declared above.

for (int i = 0; i < thirds.length; i++) {
  pen.println(thirds[i]);
} // for

Similarly, to set a particular value in the array, we assign to the name of the array, followed by an open bracket, followed by an expression that gives the index, followed by a close bracket. For example, here is some code that increments all the grades in the class by 5.

for (int i = 0; i < grades.length; i++) {
  grades[i] = grades[i] + 5;
} // for

Vectors: More Object-Like Arrays

Many programmers find it odd that arrays have a different syntax than do most objects. Others find it inconvenient that arrays have a fixed size. To handle these, and similar, objects, Java provides an array-like structure called java.util.Vector. Vectors are much like arrays in that Vectors are

However, unlike arrays, vectors are expandable - you can continue to add elements to a vector, even if the vector has grown beyond its original size. As you are likely to discover, it is fairly easy to build your own Vector class from the underlying array structures; in essence, you have a field that contains an array, and you build a new array and copy over values whenever the original array gets too big. For now, you can rely on the built-in class.

The standard vector class, java.util.Vector is a parameterized class. That is, when you create an object in that class, you must supply the underlying type. For example, to create a vector of strings, you would write

Vector<String> stuff = new Vector<String>();

Once you have created a vector (or obtained one from another method or class), you can

Note that java.util.Vector distinguishes between the number of values that are stored in the vector (that is, the size of the vector) from the number of valid spaces in the underlying array, which it calls the capacity of the vector. In general, adding an element to the vector will increment the size, but have no effect on the capacity.

Vectors provide a wide variety of other methods, which you will explore in lab. (As we will consider later, some consider the vector interface in Java somewhat bloated.)

History

Saturday, 5 March 2005 [Samuel A. Rebelsky]

Monday, 6 March 2006 [Samuel A. Rebelsky]


This page was generated by Siteweaver on Thu Mar 30 15:24:21 2006.
The source to the page was last modified on Mon Mar 6 14:40:22 2006.
This page may be found at http://www.cs.grinnell.edu/~rebelsky/Espresso/Readings/arrays.html.

You may wish to validate this page's HTML ; Valid CSS! ; Check with Bobby

Samuel A. Rebelsky
rebelsky@grinnell.edu