Newsletter sign-up
View all newsletters

Enterprise Java Newsletter
Stay up to date on the latest tutorials and Java community news posted on JavaWorld

Sponsored Links

Optimize with a SATA RAID Storage Solution
Range of capacities as low as $1250 per TB. Ideal if you currently rely on servers/disks/JBODs

JavaWorld.com

Datastructures and algorithms, Part 1

Explore datastructures, algorithms, flowcharts, pseudocode, and arrays

By Jeff Friesen, JavaWorld.com, 05/02/03

  • Print
  • Feedback
.

Page 3 of 7

Note
This series uses pseudocode to represent algorithms.


The array datastructure

The array is one of the most widely used datastructures because of its flexibility in deriving complex datastructures and its simplicity. Because arrays are so prevalent and because I needed to use the one-dimensional array variant in several of this column's earlier programs, I briefly introduced the array datastructure in "Non-Object-Oriented Language Basics, Part 1." This section builds on that earlier article's introduction and begins with a definition: an array is a sequence of elements, where each element (a group of memory bytes that stores a single data item) associates with at least one index (nonnegative integer). That definition raises four interesting points:

  • Each element occupies the same number of bytes; the exact number depends on the type of the element's data item.
  • All elements share the same type.
  • We tend to think of an array's elements as occupying consecutive memory locations. When I discuss two-dimensional arrays, you'll discover that isn't always the case.
  • The number of indexes associated with any element is the array's dimension.


Note
This section focuses exclusively on arrays of one and two dimensions because higher-dimensional arrays are not used as frequently.


One-dimensional arrays

The simplest kind of array has one dimension: each element associates with a single index. Java provides three techniques for creating a one-dimensional array: use only an initializer, use only keyword new, and use keyword new with an initializer. Because I showed you how to create a one-dimensional array with only an initializer in "Non-Object-Oriented Language Basics, Part 1," I focus on the latter two techniques in this section.

Use only keyword new to create a one-dimensional array. That technique requires either of the following syntaxes: 

type variable_name '[' ']' '=' 
    'new' type '[' integer_expression ']' ';'
type '[' ']' variable_name '=' 
    'new' type '[' integer_expression ']' ';'


Either syntax:

  • Specifies variable_name as the name of the one-dimensional array variable.
  • Specifies type as each element's type. Because the one-dimensional array variable holds a reference to the one-dimensional array, the variable's type is type [ ].
  • Specifies keyword new, followed by type, followed by integer_expression between square brackets ([ ]), which identifies the number of elements. new allocates memory for a one-dimensional array's elements and zeroes all bits in each element's bytes, which means that each element contains a default value that you interpret based on type.
  • Specifies = to assign the one-dimensional array's reference to variable_name.


Tip
Java developers often place square bracket characters after type (int [] test_scores) rather than after variable_name (int test_scores []) when declaring an array variable. Keeping all type information in one place improves the source code's readability.


The following code fragment use only keyword new to create a one-dimensional array that stores data items based on a primitive type: 

int [] test_scores = new int [4];


int [] test_scores declares a one-dimensional array variable (test_scores) along with that variable's type (int []). The int [] reference type signifies that each element must contain a data item of primitive type integer. new int [4] creates a one-dimensional array by allocating memory for four consecutive integer elements. Each element holds a single integer and initializes to 0. Operator equal-to (=) assigns the one-dimensional array's reference to test_scores. Figure 4 illustrates the resulting one-dimensional array variable and elements.

Figure 4. The test_scores one-dimensional array reference variable contains a reference to a four-element one-dimensional array of integers. Click on thumbnail to view full-size image.

Caution
When creating a one-dimensional array based on a primitive type, the compiler requires the same primitive type keyword to appear on both sides of the equal-to operator. Otherwise, the compiler reports an error. For example, int [] test_scores = new long [20]; is illegal because keywords int and long represent incompatible primitive types.


Primitive type one-dimensional arrays store data items that are primitive values. In contrast, reference type one-dimensional arrays store data items that reference objects. The following code fragment uses only keyword new to create a pair of one-dimensional arrays that each store data items based on a reference type: 

Clock [] c1 = new Clock [3];
Clock [] c2 = new AlarmClock [3];


Clock [] c1 = new Clock [3]; declares a one-dimensional array variable, (c1) of type Clock [], allocates memory for a one-dimensional Clock array consisting of three consecutive elements, and assigns the Clock array's reference to c1. Each element must contain a reference to either a Clock object (assuming Clock is a concrete class) or an object created from a concrete Clock subclass, and initializes to null. Clock [] c2 = new AlarmClock [3]; resembles the previous declaration, except that a one-dimensional AlarmClock array is created, and its reference assigns to Clock [] variable c2. (Assume AlarmClock subclasses Clock.)

Use keyword new with an array initializer to create a one-dimensional array. That technique requires either of the following syntaxes: 

type variable_name '[' ']' '=' 
    'new' type '[' ']' initializer ';'
type '[' ']' variable_name '=' 
    'new' type '[' ']' initializer ';'


where initializer has the following syntax: 

'{' [ initial_value [ ',' ... ] ] '}'


Either syntax:

  • Specifies variable_name as the name of the one-dimensional array variable.
  • Specifies type as the type of each element. Because the one-dimensional array variable holds a reference to the one-dimensional array, the variable's type is type [ ].
  • Specifies keyword new, followed by type, followed by empty square brackets, followed by initializer. You do not specify the number of elements between the square brackets because the compiler determines that count from the number of initializer's entries. new allocates memory for a one-dimensional array and assigns each of initializer's entries to an element in a left-to-right fashion.
  • Specifies = to assign the one-dimensional array's reference to variable_name.


Note
A one-dimensional array (or an array of higher dimension) created by keyword new with an array intializer is sometimes referred to as an anonymous array.


The following code fragment uses keyword new with an array initializer to create a one-dimensional array that stores data items based on a primitive type: 

int [] test_scores = new int [] { 70, 80, 20, 30 };


int [] test_scores declares a one-dimensional array variable (test_scores) along with that variable's type (int []). Code new int [] { 70, 80, 20, 30 } creates a one-dimensional array by allocating memory for four consecutive integer elements; and stores 70 in the first element, 80 in the second element, 20 in the third element, and 30 in the fourth element. The one-dimensional array's reference assigns to test_scores.

Caution
Do not specify an integer expression between the square brackets on the right side of the equal-to operator. Otherwise, the compiler reports an error. For example, new int [3] { 70, 80, 20, 30 } causes the compiler to report an error because the compiler can already determine the number of elements from the initializer. Furthermore, the discrepancy arising from the 3 between the square brackets and the four entries in the initializer signifies a probable mistake.


The technique of creating one-dimensional arrays with keyword new and an array initializer also supports the creation of one-dimensional arrays that hold object references. The following code fragment uses that technique to create a pair of one-dimensional arrays that each store data items based on a reference type: 

Clock [] c1 = new Clock [] { new Clock () };
Clock [] c2 = new AlarmClock [] { new AlarmClock () };


Clock [] c1 = new Clock [3]; declares a one-dimensional array variable (c1) of type Clock [], allocates memory for a one-dimensional Clock array consisting of a single element, creates a Clock object and assigns its reference to that element, and assigns the Clock array's reference to c1. Code Clock [] c2 = new AlarmClock [3]; resembles the previous declaration, except that it creates a single-element one-dimensional AlarmClock array that initializes to an AlarmClock object.

After you create a one-dimensional array, store and retrieve data items in its elements. Accomplish that task with the syntax below: 

variable_name '[' integer_expression ']'


integer_expression identifies an element's index and must evaluate to an integer ranging from 0 to one less than the one-dimensional array's length (which variable_name.length returns). An index less than 0 or greater than or equal to the length causes an ArrayIndexOutOfBoundsException object to be thrown. The following code fragment illustrates legal and illegal element access: 

String [] months = new String [] { "Jan", "Feb", "Mar", "Apr", "May", "Jun"
                                   "Jul", "Aug", "Sep", "Oct", "Nov", "Dec" };
System.out.println (months [0]); // Output: Jan
// The following method call results in an ArrayIndexOutOfBoundsException
// because index equals the month's length
System.out.println (months [months.length]);
System.out.println (months [months.length - 1]); // Output: Dec
// The following method call results in an ArrayIndexOutOfBoundsException 
// because index < 0
System.out.println (months [-1]);


An interesting situation occurs when you assign a subclass one-dimensional array variable's reference to a superclass one-dimensional array variable, because a one-dimensional array subtype is a kind of one-dimensional array supertype. If you then try to assign a superclass object reference to one of the subclass one-dimensional array's elements, an ArrayStoreException object is thrown. The following code fragment demonstrates:

  • Print
  • Feedback

Resources