|
The first digital computer, ENIAC, did not use any data structures to speak of. Its primary function was to quickly perform long sequences of mathematical calculations at speeds that were truly remarkable for its time. As important an achievement as this was, the major impact of ENIAC is not in the actual calculations it performed, but in the computational era it ushered in. Computers are utilized today in a myriad of different ways. For consumers, computers provide real-time control of washing machines, automobiles, and ovens. For scientists and engineers, computers are used to design new airplanes, to model complex molecules, and to simulate galaxies. And computers are essential for modern-day commerce, as they are employed to perform most financial transactions and to facilitate a host of different modes of communication, including the Internet. Indeed, we have come a long way since 1945 when ENIAC was first built. Modern computers routinely have memory capacities that are tens of millions of times larger than ENIAC ever had, and memory capacities continue to grow at astonishing rates. This growth in capacity has brought with it a new and exciting role for computers. Rather than simply being fast calculators, modern computers are information processors. They store, analyze, search, transfer, and update huge collections of complex data. Quickly performing these tasks requires that data be well organized and that the methods for accessing and maintaining data be fast and efficient. In short, modern computers need good data structures and algorithms. Specifying these data structures and algorithms requires that we communicate instructions to a computer, and an excellent way to perform such communication is using a high-level computer language, such as Java. In this chapter, we give a brief overview of the Java programming language, assuming the reader is somewhat familiar with an existing high-level language, such as Pascal, C, or C++. Java possesses a number of features that make it an excellent tool for exploring the implementation of data structures and algorithms. It was designed to allow for secure, platform-independent software execution, which is a big advantage in heterogeneous educational computing environments. Java allows us to use pointers for implementing sophisticated linked structures, but it restricts potentially dangerous programming styles, such as pointer arithmetic and arbitrary array indexing. In addition, it provides for several levels of data protection (such as public and private variables and methods), and it has an extensive collection of meaningfully named error conditions. It has a simple built-in mechanism for memory management and garbage collection, which can be used transparently by the novice programmer, but which has several behind-the-scenes hooks for expert programmers. And, finally, it contains simple constructs for performing fairly sophisticated kinds of computing, such as multiprocessing, network computing, and graphical user interfaces. The specific topics of the Java language we focus on in this chapter are those that are directly related to the implementation of data structures and algorithms, including the following:
Exceptions, interfaces, and casting are covered in Chapter 2. |