The main technique used to process arrays is the for loop. A for
loop is a way of processing each element of the array in a sequential manner.
Here is a typical for
loop:
// Sum the number of elements in an array of ints, myArray.
int sum = 0; // initialize the sum
for(int idx=0; idx < myArray.length; idx++) { //start idx @ 0; end idx at length-1;
//increment idx every time the loop is processed.
sum += myArray[idx]; // add the idx'th element of myArray to the sum
}
There are a number of things going on in the above for
loop:
- Before the loop starts, the index
idx
is being declared and initialized to zero. idx
is visible only within the for
loop body (between the curly braces). - At the begnning of each loop iteration, the index
idx
is being tested in a "termination condition", in this case, idx
is compared to the length of the list. If the termination condition evaluates to false
, the loop will immediately terminate. - During each loop iteration, the value of the
idx
's element in the array is being added to the running sum. - After each loop iteration, the index
idx
is being incremented.
One can traverse an array in any direction one wishes:
// Sum the number of elements in an array of ints, myArray.
int sum = 0; // initialize the sum
for(int idx=myArray.length-1; 0<=idx; idx--) { //start idx @ length-1; end idx at 0;
//decrement idx every time the loop is processed.
sum += myArray[idx]; // add the idx'th element of myArray to the sum
}
The above loop sums the list just as well as the first example, but it does it from back to front. Note however, that we had to be a little careful on how we initialized the index and how we set up the termination condition.
Here's a little more complicated loop:
// Find the index of the smallest element in an array of ints, myArray.
int minIdx = 0; // initialize the index. Must be declared outside the loop.
if(0==myArray.length) throw new NoSuchElementException("Empty array!"); //No good if array
//is empty!
else {
for(minIdx = 0, int j = 1; j<myArray.length; j++) { //start minIdx @ 0, start index @ 1;
//end index at length-1; increment
// index every time the loop is
//processed.
if(myArray[minIdx] > myArray[j])
minIdx = j; // found new minimum
}
}
Some important things to notice about this algorithm:
- The empty case must be checked explicitly — no polymorphism to help you out here!
- The desired result index cannot be declared inside the for loop because otherwise it won't be visible to the outside world.
- Be careful about using the
minIdx
value if the array was indeed empty--it's an invalid value! It can't be set to a valid value because otherwise you can't tell the difference between a value that was never set and one that was. - The
for
loop has two initialization statements separated by a comma. - The loop does work correctly if the array only has one element, but only because the termination check is done before the loop body.
- Notice that to prove that this algorithm works properly, one must make separate arguments about the empty case, the one element case and the n-element case. Contrast this to the much simpler list algorithm that only needs an empty and non-empty cases.
For convenience, Java 5.0 now offers a compact syntax used for traversing all the elements of an array or of anything that subclasses type Iterable
:
MyType[] myArray; // array is initialized with data somewhere
for(MyType x: myArray){
// code involving x, i.e. each element in the array
}
It is important to remember that this syntax is used when one wants to process every element in an array (or an Iterable
object) independent of order of processing because Java does not guarantee a traversal order.
Let's look at an algorithm where we might not want to process the entire array:
// Find the first index of a given value in an array
int idx = -1; // initialize the index to an invalid value.
for(int j=0; j<myArray.length; j++) { //no initialization ; end index at length-1;
//increment index every time the loop is processed.
if(desiredValue == myArray[j]) { // found match!
idx = j; // save the index.
break; // break out of the loop.
}
}
Notes:
- The only way you can tell if the desired value was actually found or not is if the value of
idx
is -1 or not. Thus the value of idx
must be checked before it is ever used. - The resultant
idx
variable cannot be used as the index inside the loop because one would not be able to tell if the desired value was found or not unless one also checked the length of the array. This is because if the desired value was never found, idx
at the end of the loop would equal the length of the array, which is only an invalid value if you already know the length of the array. - The
break
statement stops the loop right away and execution resumes at the point right after end of the loop.
There is a counterpart to break
called continue
that causes the loop to immediately progress to the beginning of the next iteration. It is used much more rarely than break
, usually in situations where there are convoluted and deeply nested if
-else
statements.
Can you see that the price of the compact syntax of for loops is a clear understandability of the process?
for
loops are actually a specialized version of while
loops. while
loops have no special provisions for initialization or loop incrementing, just the termination condition.
while
loops iterate through the loop body until the termination condition evaluates to a false
value.
The following for
loop:
for([initialization statement]; [termination expr] ; [increment statement]) {
[loop body]
}
Is exactly equivalent to the following:
{
[initialization statement];
while([termination expr]) {
[loop body]
[increment statement];
}
}
Note the outermost curly braces that create the scoping boundary that encapsulates any variable declared inside the for
loop.
The Java compiler will automatically convert a for
loop to the above while
loop.
Here is the above algorithm that finds a desired value in an array, translated from a for
loop to a while
loop:
// Find the index of the first occurance of desiredValue in myArray, using a while loop.
{
idx = -1; // initialize the final result
int j = 0; // initialize the index
while(j < myArray.length) { // loop through the array
if(desiredValue == myArray[j]) { // check if found the value
idx = j; // save the index
break; // exit the loop.
}
j++; // increment the index
}
}
Basically, for
loops give up some of the flexibility of a while
loop in favor of a more compact syntax.
while
loops are very useful when the data is not sequentially accessible via some sort of index. Another useful scenario for while
loops is when the algorithm is waiting for something to happen or for a value to come into the system from an outside (relatively) source.
do
-while
loops are the same as while
loops except that the conditional statement is evaluated at the end of the loop body, not its beginning as in a for
or while
loop.
An exceedingly common for
-loop to write is the following;
Stuff[] s_array = new Stuff[n];
// fill s_array with values
for(int i = 0; i < s_array.length; i++) {
// do something with s_array[i]
}
Essentially, the loop does some invariant processing on every element of the array.
To make life easier, Java implements the for-each loop, which is just an alternate for
loop syntax:
Stuff[] s_array = new Stuff[n];
// fill s_array with values
for(Stuff s:s_array) {
// do something with s
}
Simpler, eh?
It turns out that the for-each loop is not simply relegated to array. Any class that implements the Iterable
interface will work. This is discussed in another module, as it involves the use of generics.