Java programming fundamentals: Datastructures and algorithms in Java

Java 101: Datastructures and algorithms in Java, Part 3

Working with multidimensional arrays and the Matrix Multiplication algorithm

1 2 Page 2
Page 2 of 2
int[][] x = new int[5][];
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];

Figure 5 presents a conceptual view of this second ragged array.

Diagram of a ragged array, which specifies rows with varying numbers of column elements. Jeff Friesen

Figure 5. A ragged array specifies rows with varying numbers of column elements

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 the spreadsheet, we require a great deal of memory. But suppose most of the 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.)

Arrays are objects

According to the first sentence of Chapter 10 in the Java Language Specification arrays are objects in Java. Under the hood, each array is an instance of a hidden class that inherits java.lang.Object's 11 methods. The array instance overrides Object's protected Object clone() throws CloneNotSupportedException method, allowing the array to be shallowly cloned. The hidden class additionally provides a .length field.

Listing 2's ArrayIsObject source code demonstrates the association between arrays and objects.

Listing 2.

public final 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++)

ArrayIsObject creates a-referenced and b-referenced double precision floating-point arrays with the same contents and lengths. For the a-referenced array, a.getClass() returns class [D, where [D is the name of the array's hidden class.

Despite the two arrays having the same contents, a.equals(b) returns false because equals() compares references (not contents), and a and b contain different references. b's reference is assigned 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 this new array is assigned 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. The loop reads the contents of d's read-only .length field to determine over how many elements to iterate.

Compile Listing 2 as follows:


Run the resulting application as follows:

java ArrayIsObject

You should observe 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 

Conclusion to Part 3

This article has introduced multidimensional arrays and the techniques for creating and using them in your Java programs. One very common technique is to multiply one matrix by another matrix. I showed you how to use the Matrix Multiplication algorithm to solve a real-world problem encoded as a pair of two-dimensional arrays. I also introduced ragged arrays and explained why they are especially valuable for big data applications. Finally, I addressed the question of whether arrays are objects in Java. Revealing the hidden class demonstrates that arrays are indeed objects, with all the powers inherited from java.lang.Object.

Stay tuned for Part 4, where we will explore singly linked lists and their algorithms!

1 2 Page 2
Page 2 of 2