Introduction

Almost every application beyond "Hello World" needs to keep track of a certain amount of data. A simple numeric problem might work with three or four numbers only, but most applications have groups of similar data items. A GUI-based application may need to keep track of a number of dialog windows. A personal information manager or PIM needs to keep track of a number of, well, persons. An operating system needs to keep track of who is allowed to log in, who is currently logged in, and what those users are doing. A library needs to keep track of who has books checked out and when they're due. A network server may need to keep track of its active clients. A pattern emerges here, and it revolves around variations of what has traditionally been called data structuring.

There are data structures in the memory of a running program; there is structure in the data in a file on disk, and there is structure in the information stored in a database. In this chapter, we concentrate on the first aspect: in-memory data. We'll cover the second aspect in Chapter 10 and the third in Chapter 20.

If you had to think about in-memory data, you might want to compare it to a collection of index cards in a filing box, or to a treasure hunt where each clue leads to the next. Or you might think of it like my desk apparently scattered, but actually a very powerful collection filled with meaningful information. Each of these is a good analogy for a type of data structuring that Java provides. An array is a fixed-length linear collection of data items, like the card filing box: it can only hold so much, then it overflows. The treasure hunt is like a data structure called a linked list . Until JDK 1.2, Java had no standard linked list class, but you could (and still can) write your own "traditional data structure" classes. The complex collection represents Java's Collection classes. A document entitled Collections Framework Overview, distributed with the Java Development Kit documentation (and stored as file /jdk1.x/docs/guide/collections/overview.html ), provides a detailed discussion of the Collections Framework. The framework aspects of Java collections are summarized in Recipe Recipe 7.16.

Beware of some typographic issues. The word Arrays (in constant width font) is short for the class java.util.Arrays , but in the normal typeface, the word "arrays" is simply the plural of "array" (and will be found capitalized at the beginning of a sentence). Also, note that HashMap and HashSet, added in JDK 1.2, follow the rule of having a "midcapital" at each word boundary, while the older Hashtable does not (the "t" is not capitalized).

Several classes in java.util are not covered in this chapter. All the classes whose names begin with Abstract are, in fact, abstract, and we discuss their nonabstract subclasses. BitSet is used less frequently than some of the classes discussed here and is simple enough to learn on your own; I have examples of it in Recipes Recipe 2.6 and Recipe 5.10. The StringTokenizer class is covered in Recipe 3.2.

We start our discussion of data structuring techniques with one of the oldest structures, the array. Then we'll go through a variety of fancier structuring techniques using classes from java.util. At the end, we discuss the overall structure of the java.util's Collections Framework.