You closed module 4 with a promise and a confession. The promise: BiblioTech's provisional arrays will become collections. The confession: every time the project needs to store many things, it falls back on a Material[] catalog = new Material[10] that has to be copied whole to add an element and walked end to end to find one. Before replacing them it is worth understanding them properly, because the array does not go away: ArrayList is an array inside, HashMap is an array of buckets, ArrayDeque is a circular array, and String is an array of bytes. The whole Collections Framework you will see in the next eight lessons is built on arrays.

An array (the term we will use almost always, because it is the one you will see in all real code) is Java's most primitive and fastest data structure: a contiguous block of memory, of fixed size, that holds elements of the same type and lets you reach any one of them by position in constant time. Those four words —contiguous, fixed, homogeneous, constant— explain at once all its power and all its limitations. In this lesson you will see them in detail, you will finally learn the for-each loop left pending in module 2, you will master the Arrays utility class and you will finish with a clear list of the things an array cannot do: exactly the list of reasons why the Collections Framework exists.

1. What an array really is
2. Declaring, creating and initialising
3. Default values
4. Indices, length and the bounds of the array
5. Traversal with a classic for
6. The for-each loop
7. Arrays of primitives versus arrays of objects
8. Multidimensional and jagged arrays
9. The Arrays class
10. Copying arrays
11. Varargs is an array underneath
12. Application: the BiblioTech catalogue
13. The limitations that motivate collections
14. Common Mistakes and Tips
15. Exercises

An array is a contiguous block of memory reserved in one go, divided into cells of the same size. When you write:

the JVM reserves enough space on the heap for five integers (five times four bytes) plus a small header with the type and the length. All the cells sit one right behind the other:

That contiguity is the key to everything. To read daysLate[3], the JVM does not search for anything: it computes base_address + 3 * 4 bytes and reads. One multiplication and one addition, always the same work, whether the array has five elements or five million. We call that constant-time access, or O(1).

O() notation: how to read it. Throughout this module you will compare data structures by their cost. O() notation describes how the time of an operation grows as the number of elements n grows, ignoring constants and machine details. O(1) means constant time: whether there are 10 or 10 million elements, it costs the same. O(n) means linear: twice the elements, twice the time (walking a whole array). O(log n) means that doubling the elements adds just one more step (binary search: with a million elements, about 20 steps). O(n²) means that doubling the elements quadruples the time (two nested loops; that is what BiblioTech's reportByType does today). It is not a measure of seconds, it is a measure of how it scales.

And there is a second, less obvious advantage: cache locality. Modern processors do not read memory byte by byte, but in blocks (cache lines, typically 64 bytes). When reading daysLate[0], the processor brings in the following elements "for free" as well. That is why walking an array is dramatically faster than walking a structure whose elements are scattered around memory: you will see it with numbers in 05-04, when you compare ArrayList with LinkedList.

The three properties that define an array in Java:

That third point surprises a lot of people: an array is an object, even though there is no Array class you can look at. int[], String[] and Material[] are real types that inherit from Object, so an array has hashCode(), toString() and getClass(). That will have important consequences in section 9.

These are three distinct operations and it pays not to confuse them.

Declaring only creates the variable that will hold the reference. There is no array yet:

Always use the first form. The second compiles, but hides information: in Material catalog[], other;, catalog is an array and other is not, which is a classic source of confusion.

Creating reserves the memory with new, and this is where the size is fixed forever:

The size can be a variable computed at run time, which is flexible enough:

What it cannot do is change afterwards. selection will be howMany long forever.

Initialising with a literal creates and fills in a single expression, and the size is inferred from the elements:

This shorthand only works in the declaration. If you want to assign an array literal to an already declared variable, or pass it directly as an argument, you need the full form with new:

When you create an array with new, Java fills every cell with the default value for the type. This is no minor detail: it means a freshly created array never contains garbage, unlike what happens in C.

The most important practical consequence is the last row. A new Material[10] does not contain ten materials: it contains ten null references. Filling them is still your job:

It also explains the classic trap of counting elements: if you create new Material[10] and only fill three, catalog.length is 10, not 3. The array does not know how many cells you have used; that is why the whole BiblioTech of module 4 drags around helper variables such as int n = 0 to keep the count by hand. Collections remove exactly that problem.

Array indices run from 0 to length - 1. Starting at 0 is not a whim: the index is literally the offset from the start of the block. The first element is at distance zero from the base.

length is a field, not a method. You write array.length, without parentheses. It is one of Java's historical inconsistencies that causes the most confusion, because for String it is a method (text.length()) and for collections it is yet another method (list.size()). Memorise all three:

If you go out of range, the JVM detects it and throws ArrayIndexOutOfBoundsException:

This is a virtue, not a defect: Java checks every access and stops the program at the exact point of the error, instead of silently reading somebody else's memory the way C would. The cost of that check is minimal and the JIT compiler removes it when it can prove the index is safe. How to catch and handle that exception is the subject of module 6; for now, avoid it by checking the bounds before you access.

The for loop you have known since 02-02 is the complete way to walk an array, and it is still the right one when you need the index:

Three details that prevent most traversal bugs:

• i < fines.length, never i <= fines.length. The last valid index is length - 1.
• Use fines.length, not a literal constant such as 4. If the array grows tomorrow, the loop adapts on its own.
• Start at 0, unless you have an explicit reason not to.

The classic for is essential when the traversal needs more than the values:

That last one is the most important to remember for the next section.

In module 2 the for-each was postponed because there was no point explaining it without something to walk. Now you have it.

The enhanced for loop or for-each (Java 5) walks every element of an array or of any Iterable object —which includes all the collections you will see in this module— without managing indices:

It reads literally as "for each element of type Type in collectionOrArray". The colon is pronounced "in".

Compare the two versions of the same traversal:

And with the project's objects, where it really shines:

• Less code and fewer mistakes. The three classic sources of failure disappear: starting at 1, ending with <=, forgetting the i++ (infinite loop).
• Impossible to go out of range. There is no index to get wrong: ArrayIndexOutOfBoundsException cannot happen.
• It expresses the intent. "I walk every element, one by one, forwards." Whoever reads your code knows it instantly.
• It works the same with arrays and with collections. The same loop serves Material[] and List<Material>, which will make the refactoring in section 12 painless.

And now the three things it cannot do, which are the reason the classic for still exists:

1. It does not give you the index. If you need to number, compare with the neighbour or write at position i, you need the classic for (or keep a separate counter, which is exactly what the for-each was trying to avoid).

2. It cannot modify the array cell. This is the limitation that is most often misunderstood, so it is worth seeing precisely:

The variable n is a copy of the cell's value (pass by value, 03-03). Reassigning it changes the copy, not the array. The same happens with objects:

m is a copy of the reference. Reassigning it points the copy at another object; the array cell still points at the original.

But you can modify the object it points to, because there you reassign nothing, you invoke methods on the same object:

The rule, in one line: the for-each cannot change what each cell points at, but it can change the state of the object pointed at.

3. It only goes forwards and one at a time. There is no reverse traversal, no jumps, no partial traversals.

Use for-each by default and drop down to the classic for only when you need what the for-each does not give you. In 05-02 you will see that the for-each is not a magic construct: the compiler translates it into a classic for when it walks an array, and into an Iterator when it walks a collection.

Here is the structural difference that explains half of the surprises with arrays: what each cell really holds.

In an array of primitives, the cell contains the value:

In an array of objects, the cell contains a reference to the object, which lives elsewhere on the heap:

Four consequences follow from that diagram, and they are worth keeping very clear:

1. An array of objects is smaller than it looks but more expensive to walk. The cells only hold references (4 or 8 bytes), but following each reference means a jump to another area of the heap, which breaks the cache locality of section 1.
2. Two cells can point at the same object (aliasing, 03-02). catalog[2] = catalog[0]; does not copy the book: it creates a second path to it. Modifying it through one route is visible through the other.
3. null is a legitimate value in the cells, and every access to catalog[i].something() can throw NullPointerException if that cell was never filled.
4. The array is covariant, and that has a trap. Material[] accepts any subclass of Material (Book, Magazine, Dvd), which is convenient and is what makes the polymorphic catalogue possible. But it also allows this:

The compiler accepts it because Book[] is a subtype of Object[], but the JVM checks the real type on every write and throws ArrayStoreException. It is a type-safety hole that Java 1.0 accepted out of pragmatism and that generics fixed: List<Book> is not a List<Object>, precisely so that this error is caught at compile time. The full theory (invariance, wildcards, type erasure) is lesson 10-01.

In Java there are no true two-dimensional arrays: what exists are arrays whose elements are, in turn, arrays. Understanding that clears up every doubt at once.

This creates an array of 3 elements, each of which is a reference to an array of 12 integers:

Access takes two indices, in row-column order:

The natural traversal is two nested loops, one per dimension:

Or, if you do not need the indices, with a nested for-each:

Notice the type of the outer loop variable: int[] row, not int. Every element of an int[][] is an int[].

There is literal initialisation too, and here it is plain to see that these are arrays of arrays:

Since each row is an independent array, the rows can have different lengths. That is called a jagged array:

Notice the syntax new String[3][]: you state the number of rows and leave the second dimension empty, because each row will be created later with its own size. If you leave the rows uncreated, they are null, and accessing loansPerEmployee[0][0] would give a NullPointerException.

This structure —"for each employee, a list of titles of varying length"— is exactly the one you will replace in 05-05 with a Map<Employee, List<Loan>>, far more expressive and with no numeric indices to keep in sync with another array of names.

java.util.Arrays is a utility class with static methods that solve almost everything you need to do with arrays. It is one of the first things to import in any serious program:

An array is an object that does not override toString(), so printing it directly shows the Object representation from 03-09 (type name, at sign, hash in hexadecimal):

For arrays of more than one dimension, toString is not enough —it would print the reference of each row— and you need deepToString, which descends recursively:

Arrays.toString is your number one tool for debugging arrays. Use it in every trace.

Arrays.sort sorts the array in place: it modifies the array it receives and returns nothing.

With objects there are two variants. Without a Comparator, it requires the elements to implement Comparable —which Card does, as you saw in 04-07— and uses their natural order:

And with a Comparator, which is where the whole of module 4 connects:

There is also a variant that sorts only a range, useful when the array has unused cells at the end:

The full theory —the compareTo contract, stability, which algorithm Java uses— is this module's closing lesson, 05-09.

It looks for an element with a binary search: it checks the middle element, discards half and repeats. Cost O(log n): in an array of a million elements, about twenty checks instead of a million.

Two essential warnings:

• The array must be sorted beforehand, by the same criterion you are searching with. On an unsorted array the result is garbage, and there is no warning whatsoever.
• The negative value is not "-1 and that's it": it is -(insertion_point) - 1. In the example, -4 means 400 would go at index 3. If you want the insertion point: int pos = -result - 1;.

Fills the whole array (or a range) with the same value:

copyOf creates a new array of the given size, copying what fits and filling the rest with the default value:

This is exactly the trick BiblioTech has been using since module 3 to "grow" an array, and also, literally, what ArrayList does internally (05-03).

copyOfRange copies a stretch, with the lower bound included and the upper one excluded:

Here is a trap that costs many people hours. Since an array does not override equals, comparing two arrays with == or with .equals() compares references, not contents:

And for arrays of more than one dimension, Arrays.equals compares the rows by reference and also fails; you need deepEquals:

The same goes for the hash: use Arrays.hashCode and Arrays.deepHashCode, never array.hashCode(), if you are going to put arrays into hash-based structures (which is, moreover, an idea 05-05 will argue you out of).

Arrays.asList creates a List from an array, and it is tempting because it looks like the obvious conversion. But it returns a fixed-size view backed by the original array, not a normal list:

If you want a real list, independent and modifiable, wrap the view:

And one extra trap that shows up with primitives: Arrays.asList is generic and generics do not accept primitive types, so an int[] is interpreted as a single element:

With Integer[] it would work the way you expect. The deep cause —generics only operate on reference types— is explained in 10-01.

There are four ways to copy, and choosing badly is a common source of subtle bugs.

The first row is the blunder: Material[] a = original; creates a second name for the same array. Writing a[0] = other; also changes original[0]. It is the aliasing of 03-02 applied to arrays, and that is why the constructor of Catalog does Arrays.copyOf(materials, materials.length): a defensive copy (03-07) so that whoever built the array cannot alter the catalogue through the back door.

All copies are shallow. They copy the references, not the objects:

For a deep copy you have to clone element by element, and that is why the immutability of 03-07 is so convenient: if the objects do not change, a shallow copy is enough and there is no risk.

System.arraycopy is the most awkward of the four but the most powerful, because it copies into an array that already exists, at whatever position you want, and it allows overlap with the same array as source and destination. It is what ArrayList.remove(int) uses to close the gap:

It is an O(n) operation: every element after it has to be moved. Remember this detail, because it is exactly the cost ArrayList.remove(0) will pay in 05-03 and the one LinkedList avoids in 05-04.

In 03-03 you used varargs to write methods with a variable number of arguments:

The secret is that double... fines is exactly double[] fines with syntactic sugar at the call site: the compiler packs the loose arguments into an array before invoking the method.

Three practical rules follow from that:

• A varargs parameter is never null if it is called with the normal syntax: with no arguments a zero-length array arrives. You can walk it without checking anything.
• There can be only one and it must come last: method(String label, double... values) is valid; the other way round, it is not.
• You can pass it an already built array, which is very useful for forwarding arguments between methods.

Let us bring it all together in the project's catalogue, still in its array version, and sort it with the Comparators from module 4.

And its use, applying the comparators from 04-06:

It works. And it contains, written by hand, three pieces that in the next lesson the JDK will hand you ready-made: automatic growth, the shift on removal and the distinction between capacity and occupied size.

Look at ArrayCatalog with a critical eye. Everything it has beyond a List is infrastructure, not business logic:

None of those limitations makes the array obsolete. An array is still the right choice when:

• The size is known and fixed (a 3×12 matrix, a board, a 4096-byte buffer).
• You work with primitives and performance matters: an int[] of a million elements takes 4 MB; a List<Integer> can take five times more because of autoboxing (05-02).
• You need maximum traversal speed and cache locality is decisive.
• You are implementing a data structure, as ArrayList, HashMap and ArrayDeque do internally.

For everything else —which in a business application is practically everything— the answer is the Collections Framework.

length with parentheses. array.length() does not compile. It is a field on arrays, a method on String and size() on collections. Keep it in your head as a three-row table.

Confusing capacity with content. new Material[10] has length == 10 but zero materials. If you have only filled three cells, walking all ten will give you seven NullPointerExceptions. Always keep a counter or trim with Arrays.copyOf(array, n) before returning.

Printing an array directly. System.out.println(array) shows [I@1b6d3586. Use Arrays.toString(array) and, with more than one dimension, Arrays.deepToString(array).

Comparing arrays with equals or ==. Both compare references. Use Arrays.equals and, with more dimensions, Arrays.deepEquals.

Believing the for-each modifies the array. for (int n : numbers) { n = 0; } changes nothing: n is a copy. If you write into the cells, use a classic for. If you only call methods on the object, the for-each is perfect.

Assigning instead of copying. Material[] copy = original; does not copy; it creates an alias. Use original.clone() or Arrays.copyOf(original, original.length). And remember that both are shallow: the objects pointed at are shared.

Treating Arrays.asList as a normal list. It is a fixed-size view backed by the array: set yes, add/remove throw UnsupportedOperationException. If you need to modify it, wrap it in new ArrayList<>(...).

binarySearch on an unsorted array. It returns meaningless results, with no warning at all. Sort first, by the same criterion you are searching with. And remember that the negative returned is -(insertion point) - 1, not a plain "not found".

Forgetting to null out the freed cell on removal. In remove, after the arraycopy, the last cell still points at the object that is no longer part of the catalogue. As long as the array lives, that object cannot be collected: it is a silent memory leak. ArrayList does exactly that elementData[--size] = null for the same reason.

Style tip: for-each by default. If the loop does not need the index, write for (Material m : catalog). It is shorter, clearer and impossible to break on the bounds. Drop down to the classic for only when the index is genuinely necessary.

Write a class CatalogStatistics with static methods that take a Material[]:

• int countByType(Material[] catalog, String type): how many materials of that type there are.
• Material mostExpensive(Material[] catalog): the one with the highest daily rate, or null if the array is empty or null.
• double averageRate(Material[] catalog): the average of the daily rates, 0.0 if there are no elements.
• String[] titles(Material[] catalog): a new array with the titles only.

All of them must ignore null cells and use for-each whenever possible.

Create MonthlyReport managing an int[][] loans of 3 rows (Book, Magazine, DVD) by 12 columns (months). Implement:

• void register(int type, int month): increments the corresponding cell.
• int totalByType(int type) and int totalByMonth(int month).
• int busiestMonth(): the index of the month with the most loans overall.
• String table(): a table formatted with printf showing rows, columns and totals.

Write CatalogUtils with static methods that apply the Arrays class:

• Material[] add(Material[] catalog, Material item): returns a new array with one more element (without modifying the original).
• Material[] removeAt(Material[] catalog, int index): returns a new array without that element.
• Material[] sortedByTitle(Material[] catalog): returns a sorted copy, leaving the original untouched.
• int findByReference(Material[] catalog, String reference): use Arrays.sort + Arrays.binarySearch on a copy and explain in a comment why the returned index is not usable on the original array.

Solution 1

The four methods share the same defensive skeleton: check null on the array, skip null elements and return a neutral value (0, a documented null, an empty array) when there is no data. The important detail in titles is the "create at maximum size, count, trim" pattern: it is the only way to return an array of the exact size when you do not know in advance how many elements there will be. It is also, exactly, what ArrayList.toArray() does for you.

Solution 2

Notice the deliberate alternation between the two loops. totalByType walks a row with for-each because it does not need to know which month each value belongs to. totalByMonth walks the rows with for-each but indexes the column, because the month is given. And busiestMonth needs the classic for because what it returns is the index. Each loop uses the tool that belongs to it.

Solution 3

This exercise lays bare how awkward the array is for everyday operations. add builds a whole array to insert one element: O(n) every time. removeAt needs two arraycopy calls. And findByReference costs more than the linear search it meant to avoid, because sorting the copy is O(n log n) and then the index has to be translated. The honest conclusion is that for searching by key, the array is the wrong structure: the right answer is a Map<String, Material>, with O(1) lookup and no copies or probes. That is lesson 05-05.

You now master the structure everything else is built on. You know that an array is a contiguous block of memory of fixed size and homogeneous type, that it is a heap object even though it has no visible class, and that its contiguity gives it O(1) access by index and a cache locality no other structure matches. You distinguish declaring, creating with new and initialising with a literal; you know the default values and you know that new Material[10] contains ten nulls, not ten materials; and you are clear that length is a field, that indices run from 0 to length - 1 and that going outside throws ArrayIndexOutOfBoundsException —an exception that module 6 will teach you to handle.

You have finally learned the for-each that was postponed in module 2: its syntax for (Type e : source), its advantages —less code, impossible to go out of range, the same shape for arrays and collections— and its three exact limitations: it does not give the index, it cannot reassign the cell (though it can modify the object pointed at) and it only goes forwards. And you have the criterion: for-each by default, classic for when the index is indispensable.

You know what each cell really holds —values in arrays of primitives, references in arrays of objects—, with everything that follows: aliasing, null, worse locality and the covariance that can throw ArrayStoreException at run time, the hole that the generics of 10-01 came along to plug. You handle multidimensional arrays understanding them as arrays of arrays, including jagged ones with rows of different lengths. And you have the Arrays class in your hands: toString/deepToString for debugging, sort with and without a Comparator, binarySearch with its two warnings, fill, copyOf, copyOfRange, equals/deepEquals versus the inherited equals that compares references, and asList with its fixed-size-view trap. You know how to copy in four ways, and that all of them are shallow. And you know that a varargs parameter is literally an array, never null, always last.

BiblioTech now has an ArrayCatalog that grows on its own, removes by closing the gap, returns defensive copies and sorts itself with any Comparator from module 4. It works. And three quarters of its code is infrastructure that should not be there: a counter n running parallel to length, an Arrays.copyOf to double the capacity, a System.arraycopy to shift, a manual null to avoid leaking memory. None of that talks about libraries or loans. On top of that, it still cannot guarantee there are no duplicate ISBNs without an O(n) loop, nor search by reference in less than O(n), nor group loans by employee without nested O(n²) loops.

In the next lesson, The Collections Framework, you will see the full map of the structures the JDK already has solved: the Iterable → Collection → List/Set/Queue hierarchy, the Map that stands apart and why, the golden rule "declare by the interface, instantiate the implementation", the master table comparing the ten implementations you will use for the rest of your professional life, how the for-each you have just learned works inside —with the Iterator underneath and the dreaded ConcurrentModificationException— and a decision tree for choosing the right collection first time. From there on, each lesson in the module will develop one row of that table, and the ArrayCatalog you have just written will shrink to half the lines.