Java 101: Datastructures and algorithms, Part 1

Explore datastructures, algorithms, flowcharts, pseudocode, and arrays

Computer science emphasizes two important topics: datastructures and algorithms. Those topics are important because the choices you make for a program's datastructures and algorithms affect that program's memory usage (for datastructures) and CPU time (for algorithms that interact with those datastructures). When choosing a datastructure or algorithm, you sometimes discover an inverse relationship between memory usage and CPU time: the less memory a datastructure uses, the more CPU time associated algorithms need to process the datastructure's data items, which are primitive type values or objects, via references. Also, the more memory a datastructure uses, the less CPU time associated algorithms need to process the data items—and faster algorithms result. This inverse relationship appears in Figure 1.

Figure 1. The inverse relationship between memory usage and CPU time

An example of the inverse relationship between memory usage and CPU time involves the one-dimensional array and doubly-linked list datastructures, and their insertion/deletion algorithms. For any given list of data items, a one-dimensional array occupies less memory than a doubly linked list: a doubly linked list needs to associate links with data items to find each data item's predecessor and successor, which requires extra memory. In contrast, a one-dimensional array's insertion/deletion algorithms are slower than a doubly linked list's equivalent algorithms: inserting a data item into or deleting a data item from a one-dimensional array requires data item movement to expose an empty element for insertion or close an element made empty by deletion. (I explore one-dimensional arrays later in this article, and doubly linked lists in next month's article.)

This article initiates a two-part series that explores datastructures and algorithms. The article begins with a presentation of basic concepts and continues with a tour of the array datastructure. You learn about one-dimensional, two-dimensional, and ragged arrays, plus linear-search, bubble-sort, binary-search, and matrix-multiplication array-oriented algorithms. The article ends by asserting that Java's arrays are objects.

Note: You can download the source code that accompanies this article from Resources.

Datastructure and algorithm basics

Before we explore specific datastructures and algorithms, we need to examine three basic questions: What is a datastructure? What is an algorithm? How do you represent an algorithm? Knowledge of those concepts helps you understand this series.

What is a datastructure?

Datastructures have been around since the structured programming era. A definition from that era: a datastructure is a set of types, a designated type from that type set, a set of functions, and a set of axioms. That definition implies that a datastructure is a type with implementation. In our object-oriented programming era, type with implementation means class.

The datastructure is a class definition is too broad because it embraces Employee, Vehicle, Account, and many other real-world entity-specific classes as datastructures. Although those classes structure various data items, they do so to describe real-world entities (in the form of objects) instead of describing container objects for other entity (and possibly container) objects. This containment idea leads to a more appropriate datastructure definition: a datastructure is a container class that provides storage for data items, and capabilities for storing and retrieving data items. Examples of container datastructures: arrays, linked lists, stacks, and queues. (I will explore the linked-list, stack, and queue datastructures next month.)

What is an algorithm?

Algorithms often associate with datastructures. An algorithm is a sequence of instructions that accomplishes a task in a finite time period. The algorithm receives zero or more inputs, produces at least one output, consists of clear and unambiguous instructions, terminates after a finite number of steps, and is basic enough that a person can carry out the algorithm using a pencil and paper. In contrast, a program is not necessarily finite: the program, such as a Web server, may never terminate without external intervention. Examples of algorithms associated with datastructures: linear-search, bubble-sort, binary-search, matrix-multiplication, linked-list-concatenation, stack-push-and-pop, and queue-insert-and-delete. (I will explore the linked-list-concatenation, stack-push-and-pop, and queue-insert-and-delete algorithms next month.)

Algorithm representation

How do you represent an algorithm? The most obvious representation: Java source code. However, writing source code before you fully understand an algorithm often leads to difficult-to-find bugs. One technique for overcoming those bugs involves flowcharts.

A flowchart is a visual representation of an algorithm's control flow. That representation illustrates statements that need to execute, decisions that need to be made, logic flow (for iteration and other purposes), and terminals that indicate start and end points. To present that visual representation, a flowchart uses various symbols, which Figure 2 shows.

Figure 2. Flowchart symbols for statements, decisions, logic flow, and terminals

What does a flowchart look like? Suppose you have a simple algorithm that initializes a counter to 0, reads characters until a new-line (\n) character is seen, increments the counter for each read digit character, and prints the counter's value after the new-line character has been read. Figure 3's flowchart illustrates this algorithm's control flow.

Figure 3. A flowchart for counting digit characters. Click on thumbnail to view full-size image.

A flowchart's advantages include its simplicity and its ability to present an algorithm's control flow visually. Flowcharts also have disadvantages:

  • Highly-detailed flowcharts can introduce errors or inaccuracies.
  • Extra time is required to position, label, and connect a flowchart's symbols, even though tools speed up this process. This delay might slow your understanding of an algorithm.
  • Because flowcharts are tools of the structured programming era, they aren't as useful in an object-oriented context. The Unified Modeling Language (UML) is more appropriate for providing object-oriented visual representations.

An alternative to flowcharts is pseudocode: a textual representation of an algorithm that approximates the final source code. Pseudocode is useful for quickly writing down an algorithm's representation. Because syntax is not a concern, no rules define how to write pseudocode. Consider the following example:

DECLARE CHARACTER ch
DECLARE INTEGER count = 0
DO
  READ ch
  IF ch IS '0' THROUGH '9' THEN
     count++
  END IF
UNTIL ch IS '\n'
PRINT count
END

The example above presents the pseudocode equivalent of Figure 3's flowchart. Although locating control flow in pseudocode can prove harder than finding it in a flowchart, typically, writing pseudocode takes less time than drawing a flowchart.

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:

AlarmClock [] ac = new AlarmClock [1];
Clock [] c = ac;
c [0] = new Clock ();

The compiler compiles the code fragment above because each line is legal. At runtime, however, c [0] = new Clock (); results in an ArrayStoreException. That exception occurs because we might try to access an AlarmClock-specific member via a reference to a Clock object. For example, suppose AlarmClock contains a public void soundAlarm() method, Clock lacks that method, and the code fragment above executes without throwing an ArrayStoreException object. An attempt to execute ac [0].soundAlarm (); crashes the JVM because we attempt to execute that method in the context of a Clock object (which doesn't incorporate a soundAlarm() method).

Caution
Exercise caution when accessing array elements because you might receive an ArrayIndexOutOfBoundsException or an ArrayStoreException.

Linear-search, bubble-sort, and binary-search algorithms

Developers commonly write code to search for data items in one-dimensional arrays and sort (order) those arrays. Three commonly used algorithms for performing those tasks are linear-search, binary-search, and bubble-sort.

The linear-search algorithm searches a one-dimensional array for a specific data item. The search first examines the element at index 0 and continues examining successive elements until either the data item is found or no more elements remain to examine. The following pseudocode demonstrates this algorithm:

DECLARE INTEGER i, srch = 72
DECLARE INTEGER x [] = [ 20, 15, 12, 30, -5, 72, 456 ]
FOR i = 0 TO LENGTH (x) - 1
    IF x [i] IS srch THEN
       PRINT "Found ", srch
       END
    END IF
NEXT i
PRINT "Did not find ", srch
END

Listing 1 presents the Java equivalent to the pseudocode above:

Listing 1. LSearchDemo.java

// LSearchDemo.java
class LSearchDemo
{
   public static void main (String [] args)
   {
      int i, srch = 72;
      int [] x = { 20, 15, 12, 30, -5, 72, 456 };
      for (i = 0; i <= x.length - 1; i++)
           if (x [i] == srch)
           {
               System.out.println ("Found " + srch);
               return;
           }
      System.out.println ("Did not find " + srch);
   }
}

LSearchDemo produces the following output:

Found 72

Linear-search's two advantages are simplicity and the ability to search either sorted or unsorted one-dimensional arrays. Its sole disadvantage is the time spent examining elements. The average number of elements to examine is half the one-dimensional array's length, and the maximum number of elements to examine is the entire length. For example, a one-dimensional array with 20 million elements requires linear-search to examine an average of 10 million elements and a maximum of 20 million elements. Because this examination time might seriously affect performance, use linear-search for one-dimensional arrays with relatively short lengths.

As with linear-search, the binary-search algorithm searches a one-dimensional array for a specific data item. Unlike linear-search, however, binary-search divides the one-dimensional array into lower and upper sections by calculating the middle element's index. If the data item is found in that element, binary-search ends. If the data item is numerically less than the data item in the middle element, binary-search calculates the index of the middle element in the lower section, ignores the upper section, and repeats. Otherwise, binary-search calculates the index of the middle element in the upper section, ignores the lower section, and repeats. The search continues until either the data item is found or the current section's lower bound exceeds the upper bound (which indicates that the data item is missing). The following pseudocode demonstrates this algorithm:

DECLARE INTEGER x [] = [ -5, 12, 15, 20, 30, 72, 456 ]
DECLARE INTEGER loIndex = 0
DECLARE INTEGER hiIndex = LENGTH (x) - 1
DECLARE INTEGER midIndex, srch = 72
WHILE loIndex <= hiIndex
   midIndex = (loIndex + hiIndex) / 2
   IF srch > x [midIndex] THEN
      loIndex = midIndex + 1
   ELSE
   IF srch < x [midIndex] THEN
      hiIndex = midIndex - 1
   ELSE
      EXIT WHILE
   END IF
END WHILE
IF loIndex > hiIndex THEN
   PRINT srch, " not found"
ELSE
   PRINT srch, " found"
END IF
END            

Listing 2 presents the Java equivalent to the pseudocode above:

Listing 2. BSearchDemo.java

// BSearchDemo.java
class BSearchDemo
{
   public static void main (String [] args)
   {
      int [] x = { -5, 12, 15, 20, 30, 72, 456 };
      int loIndex = 0;
      int hiIndex = x.length - 1;
      int midIndex, srch = 72;
      while (loIndex <= hiIndex)
      {
         midIndex = (loIndex + hiIndex) / 2;
         if (srch > x [midIndex])
             loIndex = midIndex + 1;
         else
         if (srch < x [midIndex])
             hiIndex = midIndex - 1;
         else
             break;
      }
      if (loIndex > hiIndex)
          System.out.println (srch + " not found");
      else
          System.out.println (srch + " found");
   }
}

BSearchDemo produces the following output:

72 found

Binary-search's sole advantage is the reduced time spent examining elements. The maximum number of elements to examine is log2n (where n is the one-dimensional array's length). For example, a one-dimensional array with 1,048,576 elements requires binary-search to examine a maximum of 20 elements. Binary-search's two disadvantages are increased complexity and the need to presort the one-dimensional array.

When it comes to sorting data items, bubble-sort is one of the simplest algorithms. The bubble-sort algorithm makes various passes over a one-dimensional array. For each pass, that algorithm compares adjacent data items to determine which is numerically larger or smaller. Either the larger data item (for ascending order) or the smaller data item (for descending order) swaps with the adjacent data item and moves toward the bottom of the one-dimensional array. By the end of the pass, the largest/smallest data item has moved toward the array's end. This "bubbling" effect is the origin of the bubble-sort algorithm's name. The following pseudocode demonstrates this algorithm (in an ascending sort context):

DECLARE INTEGER i, pass
DECLARE INTEGER x [] = [ 20, 15, 12, 30, -5, 72, 456 ]
FOR pass = 0 TO LENGTH (x) - 2
    FOR i = 0 TO LENGTH (x) - pass - 2
        IF x [i] > x [i + 1] THEN
           SWAP x [i], x [i + 1]
        END IF
    NEXT i
NEXT pass
END

Figure 5 illustrates bubble-sort placing a four-element one-dimensional array into ascending order. There are three passes: pass 0 performs three compares and two swaps, pass 1 performs two compares and one swap, and pass 2 performs one compare and one swap.

Figure 5. The bubble-sort makes three passes over a four-element one-dimensional array to sort its data items in ascending order. Click on thumbnail to view full-size image.

Listing 3 presents the Java equivalent to the pseudocode above:

Listing 3. BSortDemo.java

// BSortDemo.java
class BSortDemo
{
   public static void main (String [] args)
   {
      int i, pass;
      int [] x = { 20, 15, 12, 30, -5, 72, 456 };
      for (pass = 0; pass < = x.length - 2; pass++)
           for (i = 0; i < = x.length - pass - 2; i++)
                if (x [i] >  x [i + 1])
                {
                    int temp = x [i];
                    x [i] = x [i + 1];
                    x [i + 1] = temp;
                }
      for (i = 0; i <  x.length; i++)
           System.out.println (x [i]);
   }
}

BSortDemo produces the following output:

 -5
12
15
20
30
72
456

Although bubble-sort is one of the simplest sorting algorithms, it's also one of the slowest. Faster algorithms include quick-sort and heap-sort. Examine a computer science textbook to learn more about those sorting algorithms.

Tip
Another commonly used algorithm for one-dimensional arrays copies the elements from a source one-dimensional array to a destination one-dimensional array. Rather than write your own code to accomplish that task, use java.lang.System's public static void arraycopy(Object src, int srcindex, Object dst, int dstindex, int length) method, which is the fastest way to perform the copy. (I will explore this method in a future article.)

Two-dimensional arrays

A two-dimensional array, also known as a table or a matrix, where each element associates with a pair of indexes, is another simple array. We conceptualize a two-dimensional array as a rectangular grid of elements divided into rows and columns, and we use the (row, column) notation to identify a specific element. Figure 6 illustrates this conceptual view and the element-specifying notation.

Figure 6. A conceptual view of a two-dimensional array reveals a grid of elements, where each element associates with row and column indexes

Java provides three techniques for creating a two-dimensional array: use only an initializer, use only keyword new, and use keyword new with an initializer.

Use only an initializer to create a two-dimensional array. That technique requires either of the following syntaxes:

type variable_name '[' ']' '[' ']' '=' 
    '{' [ rowInitializer [ ',' ... ] ] '}' ';'
type '[' ']' '[' ']' variable_name '=' 
    '{' [ rowInitializer [ ',' ... ] ] '}' ';'

where rowInitializer has the following syntax:

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

Either syntax:

  • Specifies variable_name as the name of the two-dimensional array variable.
  • Specifies type as the type of each element. Because the two-dimensional array variable holds a reference to the two-dimensional array, the variable's type is type [ ] [ ].
  • Specifies zero or more row initializers between a pair of brace characters ({ }). If no row initializers are specified, the two-dimensional array is empty. Each row initializer specifies zero or more initial values for that row's column entries. If no initial values are specified for that row, the row is empty.
  • Specifies = to assign the two-dimensional array's reference to variable_name.

The following code fragment uses only an initializer to create a two-dimensional array that stores data items based on a primitive type:

double [][] temperatures = { { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } }; // Celsius temperatures

double [][] temperatures declares a two-dimensional array variable (temperatures) along with that variable's type (double [][]). The double [][] reference type signifies that each element must contain a data item of the double-precision floating-point primitive type. { { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } } specifies a two-row by three-column two-dimensional array, where the first row contains column data items 20.5, 30.6, and 28.3, and the second row contains column data items -38.7, -18.3, and -16.2. Behind the scenes, memory is allocated and initialized to those data items. Operator equal-to assigns the two-dimensional array's reference to temperatures. Figure 7 illustrates the resulting two-dimensional array from a conceptual and memory view.

Figure 7. Conceptual and memory views of a two-dimensional array. Click on thumbnail to view full-size image.

Use only keyword new to create a two-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 two-dimensional array variable.
  • Specifies type as the type of each element. Because the two-dimensional array variable holds a reference to the two-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 row elements. new allocates memory for a one-dimensional row array and zeroes all bits in each element's bytes, which means that each element contains a null reference. You must create a separate one-dimensional column array and assign its reference to each row element.
  • Specifies = to assign the two-dimensional array's reference to variable_name.

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

double [][] temperatures = new double [2][]; // Allocate two rows.
temperatures [0] = new double [3]; // Allocate three columns for row 0
temperatures [1] = new double [3]; // Alllocate three columns for row 1
temperatures [0][0] = 20.5; // Populate row 0
temperatures [0][1] = 30.6;
temperatures [0][2] = 28.3;
temperatures [1][0] = -38.7; // Populate row 1
temperatures [1][1] = -18.3;
temperatures [1][2] = -16.2;

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

type variable_name '[' ']' '[' ']' '=' 
    'new' type '[' ']' '[' ']' '{' [ rowInitializer [ ',' ... ] ] '}' ';'
type '[' ']' '[' ']' variable_name '=' 
    'new' type '[' ']' '[' ']' '{' [ rowInitializer [ ',' ... ] ] '}' ';'

where rowInitializer has the following syntax:

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

Either syntax:

  • Specifies variable_name as the name of the two-dimensional array variable.
  • Specifies type as the type of each element. Because the two-dimensional array variable holds a reference to the two-dimensional array, the variable's type is type [ ] [ ].
  • Specifies keyword new, followed by type, followed by two pairs of empty square brackets, followed by zero or more row initializers between a pair of brace characters. If no row initializers are specified, the two-dimensional array is empty. Each row initializer specifies zero or more initial values for that row's column entries. If no initial values are specified for that row, the row is empty.
  • Specifies = to assign the two-dimensional array's reference to variable_name.

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

double [][] temperatures = new double [][] { { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } };

The code fragment above behaves identically to the earlier double [][] temperatures = new double [][] { { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } }; code fragment.

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

variable_name '[' integer_expression1 ']' '[' integer_expression2 ']'

integer_expression1 identifies an element's row index and ranges from 0 to one less than the two-dimensional array's length, which variable_name.length returns. Similarly, integer_expression2 identifies an element's column index and ranges from 0 to one less than the length of any row. Because all rows have the same length, you might find it convenient to specify variable_name [0].length to return the number of columns for any row. The following code fragment stores a data item to and retrieves a data item from a two-dimensional array element:

double [][] temperatures = { { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } };
temperatures [0][1] = 18.3; // Replace 30.6 with 18.3
System.out.println (temperatures [1][2]); // Output: -16.2

Matrix-multiplication algorithm

Multiplying one matrix by a second matrix is a common operation in fields ranging from computer graphics, to economics, to the transportation industry. Developers usually use the matrix-multiplication algorithm to complete that multiplication. How does that algorithm work? Let A represent a matrix with m rows and p columns. Similarly, let B represent a matrix with p rows and n columns. Multiply A by B to produce a matrix C, with m rows and n columns, where each cij entry in C is obtained by multiplying all entries in A's ith row by corresponding entries in B's jth column and adding the results. Figure 8 illustrates those operations.

Figure 8. Each of A's rows is multiplied (and added) with each of B's columns to produce an entry in C. Click on thumbnail to view full-size image.
Caution
Matrix-multiplication requires that the number of columns in the left matrix (A) equal the number of rows in the right matrix (B). For example, to multiply a four-row by five-column matrix A by matrix B (as in A x B), B must contain exactly five rows.

The following pseudocode demonstrates the matrix-multiplication algorithm:

// ==      ==   == ==   ==                     ==
// | 10  30 |   | 5 |   | 10 x 5 + 30 x 7 (260) |
// |        | X |   | = |                       | 
// | 20  40 |   | 7 |   | 20 x 5 + 40 * 7 (380) | 
// ==      ==   == ==   ==                     ==
DECLARE INTEGER a [][] = [ 10, 30 ] [ 20, 40 ]
DECLARE INTEGER b [][] =  [ 5, 7 ]
DECLARE INTEGER m = 2 // Number of rows in left matrix (a)
DECLARE INTEGER p = 2 // Number of columns in left matrix (a)
                      // Number of rows in right matrix (b)
DECLARE INTEGER n = 1 // Number of columns in right matrix (b)
// Note: cs1 must equal rs2
DECLARE INTEGER c [m][n] // c holds 2 rows by 1 columns
                         // All elements initialize to 0
FOR i = 0 TO m - 1
    FOR j = 0 TO n - 1
        FOR k = 0 TO p - 1
            c [i][j] = c [i][j] + a [i][k] * b [k][j]
        NEXT k
    NEXT j
NEXT i

The pseudocode above requires three FOR loops to perform the multiplication. The innermost FOR loop multiplies a single row in matrix A with a single column in matrix B and adds the result to a single entry in matrix C (as Figure 8 illustrates). Listing 4 presents the Java equivalent to that pseudocode:

Listing 4. MatMultDemo.java

// MatMultDemo.java
class MatMultDemo
{
   public static void main (String [] args)
   {
      int [][] a = {{ 10, 30 }, { 20, 40 }};
      int [][] b = {{ 5 }, { 7 }};
      dump (a);
      System.out.println ();
      dump (b);
      System.out.println ();
      int [][] c = multiply (a, b);
      dump (c);
   }
   static void dump (int [][] x)
   {
      if (x == null)
      {
          System.err.println ("array is null");
          return;
      }
      // Dump the matrix's element values to the standard output device
      // in a tabular order
      for (int i = 0; i < x.length; i++)
      {
           for (int j = 0; j < x [0].length; j++)
                System.out.print (x [i][j] + " ");
           System.out.println ();
      }
   }
   static int [][] multiply (int [][] a, int [][] b)
   {
      // =========================================================
      // 1. a.length contains a's row count
      //
      // 2. a [0].length (or any other a [x].length for a valid x)
      //    contains a's column count
      //
      // 3. b.length contains b's row count
      //
      // 4. b [0].length (or any other b [x].length for a valid x)
      //    contains b's column count
      // =========================================================
      // If a's column count != b's row count, bail out
      if (a [0].length != b.length)
      {
          System.err.println ("a's column count != b's row count");
          return null;
      }
      // Allocate result matrix with a size equal to a's row count x b's
      // column count
      int [][] result = new int [a.length][];
      for (int i = 0; i < result.length; i++)
           result [i] = new int [b [0].length];
      // Perform the multiplication and addition
      for (int i = 0; i < a.length; i++)
           for (int j = 0; j < b [0].length; j++)
                for (int k = 0; k < a [0].length; k++) // Or k < b.length
                     result [i][j] += a [i][k] * b [k][j];
      // Return the result matrix
      return result;
   }
}

MatMultDemo produces the following output:

10 30 
20 40 
5 
7 
260 
380 

Let's explore a problem where matrix-multiplication is needed to obtain a solution. A fruit grower in Florida loads a couple of semitrailers with 1,250 boxes of oranges, 400 boxes of peaches, and 250 boxes of grapefruit. A chart of market prices, on a per-box basis, for each kind of fruit in four different cities appears in Figure 9.

Figure 9. Market prices, on a per-box basis, for three kinds of fruit in four different cities. Click on thumbnail to view full-size image.

To obtain maximum gross income, to which city should the fruit grower send the semitrailers? To solve that problem, first consider Figure 9's chart as a four-row by three-column price matrix. We then construct a three-row by one-column quantity matrix, which appears below:

==    ==
| 1250 |
|      |
|  400 |
|      |
|  250 | 
==    ==

Now that we have both matrices, we simply multiply the price matrix by the quantity matrix to produce a gross income matrix:

==                  ==              ==        ==
| 10.00  8.00  12.00 |   ==    ==   | 18700.00 | New York
|                    |   | 1250 |   |          |
| 11.00  8.50  11.55 |   |      |   | 20037.50 | Los Angeles
|                    | X |  400 | = |          |
|  8.75  6.90  10.00 |   |      |   | 16197.50 | Miami 
|                    |   |  250 |   |          |
| 10.50  8.25  11.75 |   ==    ==   | 19362.50 | Chicago
==                  ==              ==        ==

Sending both semitrailers to Los Angeles produces the highest gross income. But when distance and fuel costs are considered, perhaps New York is a better bet for yielding the highest net income.

Ragged arrays

Suppose your source code contains the following matrix declaration: int [][] x = new int [5][];. The declaration yields an integer matrix that contains five rows, and x.length returns that row count. Normally, you complete that matrix's creation by specifying the same number of column elements for each row. For example, specify 10 columns for each row via the following code fragment:

for (int i = 0; i < x.length; i++)
     x [i] = new int [10];

In contrast to many computer languages, Java does not force you to specify the same number of columns for each row. Using the previous code fragment, assign three columns to row 0, two columns to row 1, three columns to row 2, five columns to row 3, and one column to row 4; which the following code fragment demonstrates:

x [0] = new int [3];
x [1] = new int [2];
x [2] = new int [3];
x [3] = new int [5];
x [4] = new int [1];

After the code fragment above executes, you end up with a degenerate matrix known as a ragged array. Figure 10 illustrates that ragged array.

Figure 10. A ragged array specifies rows with varying numbers of column elements. Click on thumbnail to view full-size image.

Ragged arrays are useful datastructures because of their memory-saving capability. For example, consider a spreadsheet with the potential for 100,000 rows by 20,000 columns. If we attempt to use a matrix to hold that spreadsheet, we require a great deal of memory. But suppose that most of that spreadsheet's cells contain default values, such as 0 for numeric cells and null for nonnumeric cells. If we use a ragged array instead of a matrix, we store only those cells that contain nonnumeric data. (Of course, we need some kind of mapping mechanism that maps spreadsheet (row, column) coordinates to ragged array (row, column) coordinates.)

Java's arrays are objects

The first sentence of Chapter 10 in the Java Language Specification states the following: In the Java programming language, arrays are objects. Behind the scenes, each array is an instance of a hidden class that inherits Object's 11 methods and overrides Object's protected Object clone() throws CloneNotSupportedException method so that the array can be shallowly cloned. Furthermore, that hidden class provides a length field. Listing 5 demonstrates the association between arrays and objects:

Listing 5. ArrayIsObject.java

// ArrayIsObject.java
class ArrayIsObject
{
   public static void main (String [] args)
   {
      double [] a = { 100.5, 200.5, 300.5 };
      double [] b = { 100.5, 200.5, 300.5 };
      double [] c = b;
      System.out.println ("a's class is " + a.getClass ());
      System.out.println ("a and b are " + ((a.equals (b)) ? "" : "not ") +
                          "equal ");
      System.out.println ("b and c are " + ((b.equals (c)) ? "" : "not ") +
                          "equal ");
      double [] d = (double []) c.clone ();
      System.out.println ("c and d are " + ((c.equals (d)) ? "" : "not ") +
                          "equal ");
      for (int i = 0; i < d.length; i++)
           System.out.println (d [i]);
   }
}

When run, ArrayIsObject produces the following output:

a's class is class [D
a and b are not equal 
b and c are equal 
c and d are not equal 
100.5
200.5
300.5

ArrayIsObject creates a-referenced and b-referenced double-precision floating-point arrays with the same contents and the same lengths. For the a-referenced array, a.getClass () returns class [D, where [D is the name of that array's hidden class. Despite both arrays containing the same contents, a.equals (b) returns false because equals() compares references (not contents), and a and b contain different references. b's reference assigns to c, and b.equals (c) returns true because b and c reference the same array. c.clone() creates a shallow clone of c, and a reference to that new array assigns to d. To prove that the d-referenced array contains the same contents as the c-referenced array, the for loop iterates over all elements and prints their contents to the standard output device. That loop reads the contents of d's read-only length field to determine over how many elements to iterate.

Tip
In source code, specify .length (as in d.length) instead of an array's actual length. That way, you eliminate the risk of introducing length-related bugs into your code should you later change the array's length in that array's creation code.

Review

A study of datastructures and algorithms is important because they affect program performance in terms of memory usage (for datastructures) and CPU time (for algorithms that interact with datastructures). After introducing you to basic concepts, this article explored the array datastructure in terms of its one-dimensional, two-dimensional, and ragged variants. While exploring those variants, the article also explored the array-oriented linear-search, binary-search, bubble-sort, and matrix-multiplication algorithms, where you saw the importance of matrix multiplication. The article concluded by asserting that Java's arrays are objects.

I encourage you to email me with any questions you might have involving either this or any previous article's material. (Please keep such questions relevant to material discussed in this column's articles.) Your questions and my answers will appear in the relevant study guides.

Next month, I will conclude this series by exploring linked lists, stacks, queues, and trees.

Jeff Friesen has been involved with computers for the past 23 years. He holds a degree in computer science and has worked with many computer languages. Jeff has also taught introductory Java programming at the college level. In addition to writing for JavaWorld, he has written his own Java book for beginners— Java 2 by Example, Second Edition (Que Publishing, 2001; ISBN: 0789725932)—and helped write Using Java 2 Platform, Special Edition (Que Publishing, 2001; ISBN: 0789724685). Jeff goes by the nickname Java Jeff (or JavaJeff). To see what he's working on, check out his Website at http://www.javajeff.com.

Learn more about this topic

Join the discussion
Be the first to comment on this article. Our Commenting Policies