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 7 of 7

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.

About the author

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.
  • Print
  • Feedback

Resources