1. Overview
1.1 What Are Data Structures andAlgorithms Good For?
The subject of this tutorial is data structures and algorithms. A data structure is an arrangement of data in a computer’s memory (or sometimes on a disk). Data structures include arrays, linked lists, stacks, binary trees, and hash tables,
among others. Algorithms manipulate the data in these structures in various ways, such as searching for a particular data item and sorting the data.
What sorts of problems can you solve with a knowledge of these topics? As a rough approximation, we might divide the situations in which they’re useful into three categories:
• Real-world data storage
• Programmer’s tools
• Modeling
These are not hard-and-fast categories, but they may help give you a feeling for the usefulness of this tutorial’s subject matter. Let’s look at them in more detail.
1.2 Real-World Data Storage
Many of the structures and techniques we’ll discuss are concerned with how to
handle real-world data storage. By real-world data, we mean data that describes physical entities external to the computer. As some examples, a personnel record
describes an actual human being, an inventory record describes an existing car part or grocery item, and a financial transaction record describes, say, an actual check written to pay the electric bill.
A non-computer example of real-world data storage is a stack of 3-by-5 index cards. These cards can be used for a variety of purposes. If each card holds a person’s name, address, and phone number, the result is an address book. If each card holds the name, location, and value of a household possession, the result is a home inventory.
Of course, index cards are not exactly state-of-the-art. Almost anything that was
once done with index cards can now be done with a computer. Suppose you want to update your old index-card system to a computer program. You might find yourself with questions like these:
• How would you store the data in your computer’s memory?
• Would your method work for a hundred file cards? A thousand? A million?
• Would your method permit quick insertion of new cards and deletion of old
ones?
• Would it allow for fast searching for a specified card?
• Suppose you wanted to arrange the cards in alphabetical order. How would you sort them?
In this tutorial, we will be discussing data structures that might be used in ways similar to a stack of index cards.
Of course, most programs are more complex than index cards. Imagine the database the Department of Motor Vehicles (or whatever it’s called in your state) uses to keep track of drivers’ licenses, or an airline reservations system that stores passenger and flight information. Such systems may include many data structures. Designing such complex systems requires the application of software engineering techniques, which we’ll mention toward the end of this chapter.
Programmer’s Tools
Not all data storage structures are used to store real-world data. Typically, real-world data is accessed more or less directly by a program’s user. Some data storage structures, however, are not meant to be accessed by the user, but by the program itself. A programmer uses such structures as tools to facilitate some other operation. Stacks, queues, and priority queues are often used in this way. We’ll see examples as we go along.
Real-World Modeling
Some data structures directly model real-world situations. The most important data structure of this type is the graph. You can use graphs to represent airline routes between cities or connections in an electric circuit or tasks in a project. We’ll cover graphs in Chapter 13, “Graphs,” and Chapter 14, “Weighted Graphs.” Other data structures, such as stacks and queues, may also be used in simulations. A queue, for example, can model customers waiting in line at a bank or cars waiting at a toll booth.
1.3 Overview of Data Structures
Another way to look at data structures is to focus on their strengths and weaknesses. In this section we’ll provide an overview, in the form of a table, of the major data storage structures we’ll be discussing in this tutorial. This is a bird’s-eye view of a landscape that we’ll be covering later at ground level, so don’t be alarmed if the terms used are not familiar. Table 1.1 shows the advantages and disadvantages of the various data structures described in this tutorial.
The data structures shown in Table 1.1, except the arrays, can be thought of as
Abstract Data Types, or ADTs. We’ll describe what this means in Chapter 5, “Linked Lists.”
1.4 Overview of Algorithms
Many of the algorithms we’ll discuss apply directly to specific data structures. For most data structures, you need to know how to
• Insert a new data item.
• Search for a specified item.
• Delete a specified item.
You may also need to know how to iterate through all the items in a data structure, visiting each one in turn so as to display it or perform some other action on it. Another important algorithm category is sorting. There are many ways to sort data, and we devote Chapter 3, “Simple Sorting,” and Chapter 7, “Advanced Sorting,” to these algorithms.
The concept of recursion is important in designing certain algorithms. Recursion
involves a method calling itself. We’ll look at recursion in Chapter 6, “Recursion.”
(The term method is used in Java. In other languages, it is called a function, procedure, or subroutine.)
1.5 Some Definitions
Let’s look at a few of the terms that we’ll be using throughout this tutorial
Database
We’ll use the term database to refer to all the data that will be dealt with in a particular situation. We’ll assume that each item in a database has a similar format. As an example, if you create an address book using index cards, these cards constitute a database. The term file is sometimes used in this sense.
Record
Records are the units into which a database is divided. They provide a format for
storing information. In the index card analogy, each card represents a record. A
record includes all the information about some entity, in a situation in which there are many such entities. A record might correspond to a person in a personnel file, a car part in an auto supply inventory, or a recipe in a cook book file.
Field
A record is usually divided into several fields. A field holds a particular kind of data. On an index card for an address book, a person’s name, address, or telephone number is an individual field.
More sophisticated database programs use records with more fields. Figure 1.1 shows such a record, where each line represents a distinct field.
In Java (and other object-oriented languages), records are usually represented by
objects of an appropriate class. Individual variables within an object represent data fields. Fields within a class object are called fields in Java (but members in some other languages such as C++).
A record with multiple fields.
Key
To search for a record within a database, you need to designate one of the record’s fields as a key (or search key). You’ll search for the record with a specific key. For instance, in an address book program, you might search in the name field of each record for the key “Brown.” When you find the record with this key, you can access all its fields, not just the key. We might say that the key unlocks the entire record.
You could search through the same file using the phone number field or the address field as the key. Any of the fields in Figure 1.1 could be used as a search key.
1.6 Object-Oriented Programming
This section is for those of you who haven’t been exposed to object-oriented
programming. However, caveat emptor. We cannot, in a few pages, do justice to all the innovative new ideas associated with OOP. Our goal is merely to make it possible for you to understand the example programs in the text.
If, after reading this section and examining some of the example code in the following chapters, you still find the whole OOP business as alien as quantum physics, you may need a more thorough exposure to OOP. See the reading list in Appendix B, “Further Reading,” for suggestions.
Problems with Procedural Languages
OOP was invented because procedural languages, such as C, Pascal, and early
versions of BASIC, were found to be inadequate for large and complex programs. Why was this?
There were two kinds of problems. One was the lack of correspondence between the program and the real world, and the other was the internal organization of the program.
Poor Modeling of the Real World
Conceptualizing a real-world problem using procedural languages is difficult.
Methods carry out a task, while data stores information, but most real-world objects do both of these things. The thermostat on your furnace, for example, carries out tasks (turning the furnace on and off) but also stores information (the current temperature and the desired temperature).
If you wrote a thermostat control program in a procedural language, you might end up with two methods, furnace_on() and furnace_off(), but also two global variables, currentTemp (supplied by a thermometer) and desiredTemp (set by the user).
However, these methods and variables wouldn’t form any sort of programming unit; there would be no unit in the program you could call thermostat. The only such concept would be in the programmer’s mind.
For large programs, which might contain hundreds of entities like thermostats, this procedural approach made things chaotic, error-prone, and sometimes impossible to implement at all. What was needed was a better match between things in the program and things in the outside world.
Crude Organizational Units
A more subtle, but related, problem had to do with a program’s internal organization. Procedural programs were organized by dividing the code into methods. One difficulty with this kind of method-based organization was that it focused on methods at the expense of data. There weren’t many options when it came to data. To simplify slightly, data could be local to a particular method, or it could be global—accessible to all methods. There was no way (at least not a flexible way) to specify that some methods could access a variable and others couldn’t. This inflexibility caused problems when several methods needed to access the same data. To be available to more than one method, such variables needed to be global, but global data could be accessed inadvertently by any method in the program. This lead to frequent programming errors. What was needed was a way to fine-tune data accessibility, allowing data to be available to methods with a need to access it, but hiding it from other methods.
Objects in a Nutshell
The idea of objects arose in the programming community as a solution to the problems with procedural languages.
Objects
Here’s the amazing breakthrough that is the key to OOP: An object contains both
methods and variables. A thermostat object, for example, would contain not only
furnace_on() and furnace_off() methods, but also variables called currentTemp
and desiredTemp. In Java, an object’s variables such as these are called fields.
This new entity, the object, solves several problems simultaneously. Not only does an object in a program correspond more closely to an object in the real world, but it also solves the problem engendered by global data in the procedural model. The furnace_on() and furnace_off() methods can access currentTemp and desiredTemp.
These variables are hidden from methods that are not part of thermostat, however, so they are less likely to be accidentally changed by a rogue method.
Classes
You might think that the idea of an object would be enough for one programming
revolution, but there’s more. Early on, it was realized that you might want to make several objects of the same type. Maybe you’re writing a furnace control program for an entire apartment building, for example, and you need several dozen thermostat objects in your program. It seems a shame to go to the trouble of specifying each one separately. Thus, the idea of classes was born.
A class is a specification—a blueprint—for one or more objects. Here’s how a thermostat class, for example, might look in Java:
class thermostat
{
private float currentTemp();
private float desiredTemp();
public void furnace_on()
{
// method body goes here
}
public void furnace_off()
{
// method body goes here
}
} // end class thermostat
The Java keyword class introduces the class specification, followed by the name you want to give the class; here it’s thermostat. Enclosed in curly brackets are the fields and methods that make up the class. We’ve left out the bodies of the methods; normally, each would have many lines of program code.
C programmers will recognize this syntax as similar to a structure, while C++
programmers will notice that it’s very much like a class in C++, except that there’s no semicolon at the end. (Why did we need the semicolon in C++ anyway?)
Creating Objects
Specifying a class doesn’t create any objects of that class. (In the same way, specifying a structure in C doesn’t create any variables.) To actually create objects in Java, you must use the keyword new. At the same time an object is created, you need to store a reference to it in a variable of suitable type—that is, the same type as the class.
What’s a reference? We’ll discuss references in more detail later. In the meantime, think of a reference as a name for an object. (It’s actually the object’s address, but you don’t need to know that.)
Here’s how we would create two references to type thermostat, create two new thermostat objects, and store references to them in these variables:
thermostat therm1, therm2; // create two references
therm1 = new thermostat(); // create two objects and
therm2 = new thermostat(); // store references to them
Incidentally, creating an object is also called instantiating it, and an object is often referred to as an instance of a class.
Accessing Object Methods
After you specify a class and create some objects of that class, other parts of your program need to interact with these objects. How do they do that?
Typically, other parts of the program interact with an object’s methods, not with its data (fields). For example, to tell the therm2 object to turn on the furnace, we would say
therm2.furnace_on();
The dot operator (.) associates an object with one of its methods (or occasionally
with one of its fields).
At this point we’ve covered (rather telegraphically) several of the most important
features of OOP. To summarize:
• Objects contain both methods and fields (data).
• A class is a specification for any number of objects.
• To create an object, you use the keyword new in conjunction with the class name.
• To invoke a method for a particular object, you use the dot operator.
These concepts are deep and far reaching. It’s almost impossible to assimilate them the first time you see them, so don’t worry if you feel a bit confused. As you see more classes and what they do, the mist should start to clear.
1.7 A Runnable Object-Oriented Program
Let’s look at an object-oriented program that runs and generates actual output. It features a class called BankAccount that models a checking account at a bank. The program creates an account with an opening balance, displays the balance, makes a deposit and a withdrawal, and then displays the new balance.
The bank.java Program
// bank.java
// demonstrates basic OOP syntax
// to run this program: C>java BankApp
////////////////////////////////////////////////////////////////
class BankAccount
{
private double balance;
// account balance
public BankAccount(double openingBalance) // constructor
{
balance = openingBalance;
}
public void deposit(double amount) // makes deposit
{
balance = balance + amount;
}
public void withdraw(double amount) // makes withdrawal
{
balance = balance - amount;
}
public void display()
// displays balance
{
System.out.println(“balance=” + balance);
}
}
class BankApp
{
public static void main(String[] args)
{
BankAccount ba1 = new BankAccount(100.00); // create acct
System.out.print(“Before transactions, “);
ba1.display();
// display balance
ba1.deposit(74.35);
ba1.withdraw(20.00);
// make deposit
// make withdrawal
System.out.print(“After transactions, “);
ba1.display();
// display balance
} // end main()
}
// end class BankApp
Here’s the output from this program:
Before transactions, balance=100
After transactions, balance=154.35
There are two classes in bank.java. The first one, BankAccount, contains the fields and methods for our bank account. We’ll examine it in detail in a moment. The second class, BankApp, plays a special role.
The BankApp Class
To execute the program in Listing 1.1 from an MS-DOS prompt, you type java
BankApp following the C: prompt:
C:\>java BankApp
This command tells the java interpreter to look in the BankApp class for the method called main(). Every Java application must have a main() method; execution of the program starts at the beginning of main(), as you can see in Listing 1.1. (You don’t need to worry yet about the String[] args argument in main().)
The main() method creates an object of class BankAccount, initialized to a value of 100.00, which is the opening balance, with this statement:
BankAccount ba1 = new BankAccount(100.00); // create acct
The System.out.print() method displays the string used as its argument, Before
transactions:, and the account displays its balance with this statement:
ba1.display();
The program then makes a deposit to, and a withdrawal from, the account:
ba1.deposit(74.35);
ba1.withdraw(20.00);
Finally, the program displays the new account balance and terminates.
The BankAccount Class
The only data field in the BankAccount class is the amount of money in the account, called balance. There are three methods. The deposit() method adds an amount to the balance, withdrawal() subtracts an amount, and display() displays the balance.
Constructors
The BankAccount class also features a constructor, which is a special method that’s called automatically whenever a new object is created. A constructor always has exactly the same name as the class, so this one is called BankAccount(). This constructor has one argument, which is used to set the opening balance when the account is created.
A constructor allows a new object to be initialized in a convenient way. Without the constructor in this program, you would have needed an additional call to deposit() to put the opening balance in the account.
Public and Private
Notice the keywords public and private in the BankAccount class. These keywords are access modifiers and determine which methods can access a method or field. The balance field is preceded by private. A field or method that is private can be accessed only by methods that are part of the same class. Thus, balance cannot be accessed by statements in main() because main() is not a method in BankAccount.
All the methods in BankAccount have the access modifier public, however, so they can be accessed by methods in other classes. That’s why statements in main() can call deposit(), withdrawal(), and display().
Data fields in a class are typically made private and methods are made public. This protects the data; it can’t be accidentally modified by methods of other classes. Any outside entity that needs to access data in a class must do so using a method of the same class. Data is like a queen bee, kept hidden in the middle of the hive, fed and cared for by worker-bee methods.
1.8 Inheritance and Polymorphism
We’ll briefly mention two other key features of object-oriented programming: inheritance and polymorphism.
Inheritance is the creation of one class, called the extended or derived class, from another class called the base class. The extended class has all the features of the base class, plus some additional features. For example, a secretary class might be derived from a more general employee class and include a field called typingSpeed that the employee class lacked.
In Java, inheritance is also called subclassing. The base class may be called the superclass, and the extended class may be called the subclass.
Inheritance enables you to easily add features to an existing class and is an important aid in the design of programs with many related classes. Inheritance thus makes it easy to reuse classes for a slightly different purpose, a key benefit of OOP.
Polymorphism involves treating objects of different classes in the same way. For polymorphism to work, these different classes must be derived from the same base class.
In practice, polymorphism usually involves a method call that actually executes
different methods for objects of different classes.
For example, a call to display() for a secretary object would invoke a display
method in the secretary class, while the exact same call for a manager object would invoke a different display method in the manager class. Polymorphism simplifies and clarifies program design and coding.
For those not familiar with them, inheritance and polymorphism involve significant additional complexity. To keep the focus on data structures and algorithms, we have avoided these features in our example programs. Inheritance and polymorphism are important and powerful aspects of OOP but are not necessary for the explanation of data structures and algorithms.
1.9 Software Engineering
In recent years, it has become fashionable to begin a book on data structures and algorithms with a chapter on software engineering. We don’t follow that approach, but let’s briefly examine software engineering and see how it fits into the topics we discuss in this tutorial.
Software engineering is the study of ways to create large and complex computer
programs, involving many programmers. It focuses on the overall design of the
programs and on the creation of that design from the needs of the end users.
Software engineering is concerned with the life cycle of a software project, which includes specification, design, verification, coding, testing, production, and maintenance.
It’s not clear that mixing software engineering on one hand and data structures and algorithms on the other actually helps the student understand either topic. Software engineering is rather abstract and is difficult to grasp until you’ve been involved yourself in a large project. The use of data structures and algorithms, on the other hand, is a nuts-and-bolts discipline concerned with the details of coding and data storage.
Accordingly, we focus on the essentials of data structures and algorithms. How do they really work? What structure or algorithm is best in a particular situation? What do they look like translated into Java code? As we noted, our intent is to make the material as easy to understand as possible. For further reading, we mention some books on software engineering in Appendix B.
1.10 Java for C++ Programmers
If you’re a C++ programmer who has not yet encountered Java, you might want to read this section. We’ll mention several ways that Java differs from C++.
This section is not intended to be a primer on Java. We don’t even cover all the
differences between C++ and Java. We’re interested in only a few Java features that might make it hard for C++ programmers to figure out what’s going on in the example programs.
No Pointers
The biggest difference between C++ and Java is that Java doesn’t use pointers. To a C++ programmer, not using pointers may at first seem quite amazing. How can you get along without pointers?
Throughout this tutorial we’ll use pointer-free code to build complex data structures. You’ll see that this approach is not only possible, but actually easier than using C++ pointers.
Actually, Java only does away with explicit pointers. Pointers, in the form of memory addresses, are still there, under the surface. It’s sometimes said that, in Java, everything is a pointer. This statement is not completely true, but it’s close. Let’s look at the details.
References
Java treats primitive data types (such as int, float, and double) differently than
objects. Look at these two statements:
int intVar;
BankAccount bc1;
// an int variable called intVar
// reference to a BankAccount object
In the first statement, a memory location called intVar actually holds a numerical
value such as 127 (assuming such a value has been placed there). However, the
memory location bc1 does not hold the data of a BankAccount object. Instead, it
contains the address of a BankAccount object that is actually stored elsewhere in
memory. The name bc1 is a reference to this object; it’s not the object itself.
Actually, bc1 won’t hold a reference if it has not been assigned an object at some
prior point in the program. Before being assigned an object, it holds a reference to a special object called null. In the same way, intVar won’t hold a numerical value if it’s never been assigned one. The compiler will complain if you try to use a variable that has never been assigned a value.
In C++, the statement BankAccount bc1;
actually creates an object; it sets aside enough memory to hold all the object’s data. In Java, all this statement creates is a place to put an object’s memory address. You can think of a reference as a pointer with the syntax of an ordinary variable. (C++ has reference variables, but they must be explicitly specified with the & symbol.)
Assignment
It follows that the assignment operator (=) operates differently with Java objects than with C++ objects. In C++, the statement
bc2 = bc1;
copies all the data from an object called bc1 into a different object called bc2.
Following this statement, there are two objects with the same data. In Java, on the other hand, this same assignment statement copies the memory address that bc1 refers to into bc2. Both bc1 and bc2 now refer to exactly the same object; they are references to it.
This can get you into trouble if you’re not clear what the assignment operator does.
Following the assignment statement shown above, the statement
bc1.withdraw(21.00);
and the statement
bc2.withdraw(21.00);
both withdraw $21 from the same bank account object.
Suppose you actually want to copy data from one object to another. In this case you must make sure you have two separate objects to begin with and then copy each field separately. The equal sign won’t do the job.
The new Operator
Any object in Java must be created using new. However, in Java, new returns a reference, not a pointer as in C++. Thus, pointers aren’t necessary to use new. Here’s one way to create an object:
BankAccount ba1;
ba1 = new BankAccount();
Eliminating pointers makes for a more secure system. As a programmer, you can’t find out the actual address of ba1, so you can’t accidentally corrupt it. However, you probably don’t need to know it, unless you’re planning something wicked.
How do you release memory that you’ve acquired from the system with new and no longer need? In C++, you use delete. In Java, you don’t need to worry about releasing memory. Java periodically looks through each block of memory that was obtained with new to see if valid references to it still exist. If there are no such references, the block is returned to the free memory store. This process is called garbage collection.
In C++ almost every programmer at one time or another forgets to delete memory blocks, causing “memory leaks” that consume system resources, leading to bad performance and even crashing the system. Memory leaks can’t happen in Java (or at least hardly ever).
Arguments
In C++, pointers are often used to pass objects to functions to avoid the overhead of copying a large object. In Java, objects are always passed as references. This approach also avoids copying the object:
void method1()
{
BankAccount ba1 = new BankAccount(350.00);
method2(ba1);
}
void method2(BankAccount acct)
{
}
In this code, the references ba1 and acct both refer to the same object. In C++ acct would be a separate object, copied from ba1.
Primitive data types, on the other hand, are always passed by value. That is, a new variable is created in the method and the value of the argument is copied into it.
Equality and Identity
In Java, if you’re talking about primitive types, the equality operator (==) will tell you whether two variables have the same value:
int intVar1 = 27;
int intVar2 = intVar1;
if(intVar1 == intVar2)
System.out.println(“They’re equal”);
This is the same as the syntax in C and C++, but in Java, because relational operators use references, they work differently with objects. The equality operator, when applied to objects, tells you whether two references are identical—that is, whether they refer to the same object:
carPart cp1 = new carPart(“fender”);
carPart cp2 = cp1;
if(cp1 == cp2)
System.out.println(“They’re Identical”);
In C++ this operator would tell you if two objects contained the same data. If you want to see whether two objects contain the same data in Java, you must use the equals() method of the Object class:
carPart cp1 = new carPart(“fender”);
carPart cp2 = cp1;
if( cp1.equals(cp2) )
System.out.println(“They’re equal”);
This technique works because all objects in Java are implicitly derived from the
Object class.
Overloaded Operators
This point is easy: There are no overloaded operators in Java. In C++, you can redefine +, *, =, and most other operators so that they behave differently for objects of a particular class. No such redefinition is possible in Java. Use a named method instead, such as add() or whatever.
Primitive Variable Types
The primitive or built-in variable types in Java are shown in Table 1.2.
Unlike C and C++, which use integers for true/false values, boolean is a distinct type in Java.
Type char is unsigned, and uses two bytes to accommodate the Unicode character representation scheme, which can handle international characters.
The int type varies in size in C and C++, depending on the specific computer platform; in Java an int is always 32 bits.
Literals of type float use the suffix F (for example, 3.14159F); literals of type double need no suffix. Literals of type long use suffix L (as in 45L); literals of the other integer types need no suffix.
Java is more strongly typed than C and C++; many conversions that were automatic in those languages require an explicit cast in Java.
All types not shown in Table 1.2, such as String, are classes.
Input/Output
There have been changes to input/output as Java has evolved. For the console-mode applications we’ll be using as example programs in this tutorial, some clunky-looking but effective constructions are available for input and output. They’re quite different from the workhorse cout and cin approaches in C++ and printf() and scanf() in C.
Older versions of the Java Software Development Kit (SDK) required the line
import java.io.*;
at the beginning of the source file for all input/output routines. Now this line is
needed only for input.
Output
You can send any primitive type (numbers and characters), and String objects as
well, to the display with these statements:
System.out.print(var);
System.out.println(var);
// displays var, no linefeed
// displays var, then starts new line
The print() method leaves the cursor on the same line; println() moves it to the
beginning of the next line.
In older versions of the SDK, a System.out.print() statement did not actually write anything to the screen. It had to be followed by a System.out.println()or
System.out.flush() statement to display the entire buffer. Now it displays
immediately.
You can use several variables, separated by plus signs, in the argument. Suppose in this statement the value of ans is 33:
System.out.println(“The answer is “ + ans);
Then the output will be
The answer is 33
Inputting a String
Input is considerably more involved than output. In general, you want to read any input as a String object. If you’re actually inputting something else, say a character or number, you then convert the String object to the desired type.
As we noted, any program that uses input must include the statement
import java.io.*;
at the beginning of the program. Without this statement, the compiler will not
recognize such entities as IOException and InputStreamReader.
String input is fairly baroque. Here’s a method that returns a string entered by the user:
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
This method returns a String object, which is composed of characters typed on the keyboard and terminated with the Enter key. The details of the InputStreamReader and BufferedReader classes need not concern us here.
Besides importing java.io.*, you’ll need to add throws IOException to all input
methods, as shown in the preceding code. In fact, you’ll need to add throws
IOException to any method, such as main(), that calls any of the input methods.
Inputting a Character
Suppose you want your program’s user to enter a character. (By enter, we mean
typing something and pressing the Enter key.) The user may enter a single character or (incorrectly) more than one. Therefore, the safest way to read a character involves reading a String and picking off its first character with the charAt() method:
public static char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
The charAt() method of the String class returns a character at the specified position in the String object; here we get the first character, which is number 0. This approach prevents extraneous characters being left in the input buffer. Such characters can cause problems with subsequent input.
Inputting Integers
To read numbers, you make a String object as shown before and convert it to the
type you want using a conversion method. Here’s a method, getInt(), that converts input into type int and returns it:
public int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
The parseInt() method of class Integer converts the string to type int. A similar
routine, parseLong(), can be used to convert type long.
In older versions of the SDK, you needed to use the line
import java.lang.Integer;
at the beginning of any program that used parseInt(), but this convention is no
longer necessary.
For simplicity, we don’t show any error-checking in the input routines in the
example programs. The user must type appropriate input, or an exception will occur.
With the code shown here the exception will cause the program to terminate. In a serious program you should analyze the input string before attempting to convert it and should also catch any exceptions and process them appropriately.
Inputting Floating-Point Numbers
Types float and double can be handled in somewhat the same way as integers, but the conversion process is more complex. Here’s how you read a number of type double:
public int getDouble() throws IOException
{
String s = getString();
Double aDub = Double.valueOf(s);
return aDub.doubleValue();
}
The String is first converted to an object of type Double (uppercase D), which is a “wrapper” class for type double. A method of Double called doubleValue() then
converts the object to type double.
For type float, there’s an equivalent Float class, which has equivalent valueOf()
and floatValue() methods.
1.11 Java Library Data Structures
The java.util package contains data structures, such as Vector (an extensible array), Stack, Dictionary, and Hashtable. In this tutorial we’ll usually ignore these built-in classes. We’re interested in teaching fundamentals, not the details of a particular implementation. However, occasionally we’ll find some of these structures useful.
You must use the line
import java.util.*;
before you can use objects of these classes.
Although we don’t focus on them, such class libraries, whether those that come with Java or others available from third-party developers, can offer a rich source of versatile, debugged storage classes. This tutorial should equip you with the knowledge to know what sort of data structure you need and the fundamentals of how it works. Then you can decide whether you should write your own classes or use someone else’s.
- 1.1 What Are Data Structures andAlgorithms Good For?
- 1.2 Real-World Data Storage
- 1.3 Overview of Data Structures
- 1.4 Overview of Algorithms
- 1.5 Some Definitions
- 1.6 Object-Oriented Programming
- 1.7 A Runnable Object-Oriented Program
- 1.8 Inheritance and Polymorphism
- 1.9 Software Engineering
- 1.10 Java for C++ Programmers
- 1.11 Java Library Data Structures
1.1 What Are Data Structures andAlgorithms Good For?
The subject of this tutorial is data structures and algorithms. A data structure is an arrangement of data in a computer’s memory (or sometimes on a disk). Data structures include arrays, linked lists, stacks, binary trees, and hash tables,
among others. Algorithms manipulate the data in these structures in various ways, such as searching for a particular data item and sorting the data.
What sorts of problems can you solve with a knowledge of these topics? As a rough approximation, we might divide the situations in which they’re useful into three categories:
• Real-world data storage
• Programmer’s tools
• Modeling
These are not hard-and-fast categories, but they may help give you a feeling for the usefulness of this tutorial’s subject matter. Let’s look at them in more detail.
1.2 Real-World Data Storage
Many of the structures and techniques we’ll discuss are concerned with how to
handle real-world data storage. By real-world data, we mean data that describes physical entities external to the computer. As some examples, a personnel record
describes an actual human being, an inventory record describes an existing car part or grocery item, and a financial transaction record describes, say, an actual check written to pay the electric bill.
A non-computer example of real-world data storage is a stack of 3-by-5 index cards. These cards can be used for a variety of purposes. If each card holds a person’s name, address, and phone number, the result is an address book. If each card holds the name, location, and value of a household possession, the result is a home inventory.
Of course, index cards are not exactly state-of-the-art. Almost anything that was
once done with index cards can now be done with a computer. Suppose you want to update your old index-card system to a computer program. You might find yourself with questions like these:
• How would you store the data in your computer’s memory?
• Would your method work for a hundred file cards? A thousand? A million?
• Would your method permit quick insertion of new cards and deletion of old
ones?
• Would it allow for fast searching for a specified card?
• Suppose you wanted to arrange the cards in alphabetical order. How would you sort them?
In this tutorial, we will be discussing data structures that might be used in ways similar to a stack of index cards.
Of course, most programs are more complex than index cards. Imagine the database the Department of Motor Vehicles (or whatever it’s called in your state) uses to keep track of drivers’ licenses, or an airline reservations system that stores passenger and flight information. Such systems may include many data structures. Designing such complex systems requires the application of software engineering techniques, which we’ll mention toward the end of this chapter.
Programmer’s Tools
Not all data storage structures are used to store real-world data. Typically, real-world data is accessed more or less directly by a program’s user. Some data storage structures, however, are not meant to be accessed by the user, but by the program itself. A programmer uses such structures as tools to facilitate some other operation. Stacks, queues, and priority queues are often used in this way. We’ll see examples as we go along.
Real-World Modeling
Some data structures directly model real-world situations. The most important data structure of this type is the graph. You can use graphs to represent airline routes between cities or connections in an electric circuit or tasks in a project. We’ll cover graphs in Chapter 13, “Graphs,” and Chapter 14, “Weighted Graphs.” Other data structures, such as stacks and queues, may also be used in simulations. A queue, for example, can model customers waiting in line at a bank or cars waiting at a toll booth.
1.3 Overview of Data Structures
Another way to look at data structures is to focus on their strengths and weaknesses. In this section we’ll provide an overview, in the form of a table, of the major data storage structures we’ll be discussing in this tutorial. This is a bird’s-eye view of a landscape that we’ll be covering later at ground level, so don’t be alarmed if the terms used are not familiar. Table 1.1 shows the advantages and disadvantages of the various data structures described in this tutorial.
The data structures shown in Table 1.1, except the arrays, can be thought of as
Abstract Data Types, or ADTs. We’ll describe what this means in Chapter 5, “Linked Lists.”
1.4 Overview of Algorithms
Many of the algorithms we’ll discuss apply directly to specific data structures. For most data structures, you need to know how to
• Insert a new data item.
• Search for a specified item.
• Delete a specified item.
You may also need to know how to iterate through all the items in a data structure, visiting each one in turn so as to display it or perform some other action on it. Another important algorithm category is sorting. There are many ways to sort data, and we devote Chapter 3, “Simple Sorting,” and Chapter 7, “Advanced Sorting,” to these algorithms.
The concept of recursion is important in designing certain algorithms. Recursion
involves a method calling itself. We’ll look at recursion in Chapter 6, “Recursion.”
(The term method is used in Java. In other languages, it is called a function, procedure, or subroutine.)
1.5 Some Definitions
Let’s look at a few of the terms that we’ll be using throughout this tutorial
Database
We’ll use the term database to refer to all the data that will be dealt with in a particular situation. We’ll assume that each item in a database has a similar format. As an example, if you create an address book using index cards, these cards constitute a database. The term file is sometimes used in this sense.
Record
Records are the units into which a database is divided. They provide a format for
storing information. In the index card analogy, each card represents a record. A
record includes all the information about some entity, in a situation in which there are many such entities. A record might correspond to a person in a personnel file, a car part in an auto supply inventory, or a recipe in a cook book file.
Field
A record is usually divided into several fields. A field holds a particular kind of data. On an index card for an address book, a person’s name, address, or telephone number is an individual field.
More sophisticated database programs use records with more fields. Figure 1.1 shows such a record, where each line represents a distinct field.
In Java (and other object-oriented languages), records are usually represented by
objects of an appropriate class. Individual variables within an object represent data fields. Fields within a class object are called fields in Java (but members in some other languages such as C++).
Key
To search for a record within a database, you need to designate one of the record’s fields as a key (or search key). You’ll search for the record with a specific key. For instance, in an address book program, you might search in the name field of each record for the key “Brown.” When you find the record with this key, you can access all its fields, not just the key. We might say that the key unlocks the entire record.
You could search through the same file using the phone number field or the address field as the key. Any of the fields in Figure 1.1 could be used as a search key.
1.6 Object-Oriented Programming
This section is for those of you who haven’t been exposed to object-oriented
programming. However, caveat emptor. We cannot, in a few pages, do justice to all the innovative new ideas associated with OOP. Our goal is merely to make it possible for you to understand the example programs in the text.
If, after reading this section and examining some of the example code in the following chapters, you still find the whole OOP business as alien as quantum physics, you may need a more thorough exposure to OOP. See the reading list in Appendix B, “Further Reading,” for suggestions.
Problems with Procedural Languages
OOP was invented because procedural languages, such as C, Pascal, and early
versions of BASIC, were found to be inadequate for large and complex programs. Why was this?
There were two kinds of problems. One was the lack of correspondence between the program and the real world, and the other was the internal organization of the program.
Poor Modeling of the Real World
Conceptualizing a real-world problem using procedural languages is difficult.
Methods carry out a task, while data stores information, but most real-world objects do both of these things. The thermostat on your furnace, for example, carries out tasks (turning the furnace on and off) but also stores information (the current temperature and the desired temperature).
If you wrote a thermostat control program in a procedural language, you might end up with two methods, furnace_on() and furnace_off(), but also two global variables, currentTemp (supplied by a thermometer) and desiredTemp (set by the user).
However, these methods and variables wouldn’t form any sort of programming unit; there would be no unit in the program you could call thermostat. The only such concept would be in the programmer’s mind.
For large programs, which might contain hundreds of entities like thermostats, this procedural approach made things chaotic, error-prone, and sometimes impossible to implement at all. What was needed was a better match between things in the program and things in the outside world.
Crude Organizational Units
A more subtle, but related, problem had to do with a program’s internal organization. Procedural programs were organized by dividing the code into methods. One difficulty with this kind of method-based organization was that it focused on methods at the expense of data. There weren’t many options when it came to data. To simplify slightly, data could be local to a particular method, or it could be global—accessible to all methods. There was no way (at least not a flexible way) to specify that some methods could access a variable and others couldn’t. This inflexibility caused problems when several methods needed to access the same data. To be available to more than one method, such variables needed to be global, but global data could be accessed inadvertently by any method in the program. This lead to frequent programming errors. What was needed was a way to fine-tune data accessibility, allowing data to be available to methods with a need to access it, but hiding it from other methods.
Objects in a Nutshell
The idea of objects arose in the programming community as a solution to the problems with procedural languages.
Objects
Here’s the amazing breakthrough that is the key to OOP: An object contains both
methods and variables. A thermostat object, for example, would contain not only
furnace_on() and furnace_off() methods, but also variables called currentTemp
and desiredTemp. In Java, an object’s variables such as these are called fields.
This new entity, the object, solves several problems simultaneously. Not only does an object in a program correspond more closely to an object in the real world, but it also solves the problem engendered by global data in the procedural model. The furnace_on() and furnace_off() methods can access currentTemp and desiredTemp.
These variables are hidden from methods that are not part of thermostat, however, so they are less likely to be accidentally changed by a rogue method.
Classes
You might think that the idea of an object would be enough for one programming
revolution, but there’s more. Early on, it was realized that you might want to make several objects of the same type. Maybe you’re writing a furnace control program for an entire apartment building, for example, and you need several dozen thermostat objects in your program. It seems a shame to go to the trouble of specifying each one separately. Thus, the idea of classes was born.
A class is a specification—a blueprint—for one or more objects. Here’s how a thermostat class, for example, might look in Java:
class thermostat
{
private float currentTemp();
private float desiredTemp();
public void furnace_on()
{
// method body goes here
}
public void furnace_off()
{
// method body goes here
}
} // end class thermostat
The Java keyword class introduces the class specification, followed by the name you want to give the class; here it’s thermostat. Enclosed in curly brackets are the fields and methods that make up the class. We’ve left out the bodies of the methods; normally, each would have many lines of program code.
C programmers will recognize this syntax as similar to a structure, while C++
programmers will notice that it’s very much like a class in C++, except that there’s no semicolon at the end. (Why did we need the semicolon in C++ anyway?)
Creating Objects
Specifying a class doesn’t create any objects of that class. (In the same way, specifying a structure in C doesn’t create any variables.) To actually create objects in Java, you must use the keyword new. At the same time an object is created, you need to store a reference to it in a variable of suitable type—that is, the same type as the class.
What’s a reference? We’ll discuss references in more detail later. In the meantime, think of a reference as a name for an object. (It’s actually the object’s address, but you don’t need to know that.)
Here’s how we would create two references to type thermostat, create two new thermostat objects, and store references to them in these variables:
thermostat therm1, therm2; // create two references
therm1 = new thermostat(); // create two objects and
therm2 = new thermostat(); // store references to them
Incidentally, creating an object is also called instantiating it, and an object is often referred to as an instance of a class.
Accessing Object Methods
After you specify a class and create some objects of that class, other parts of your program need to interact with these objects. How do they do that?
Typically, other parts of the program interact with an object’s methods, not with its data (fields). For example, to tell the therm2 object to turn on the furnace, we would say
therm2.furnace_on();
The dot operator (.) associates an object with one of its methods (or occasionally
with one of its fields).
At this point we’ve covered (rather telegraphically) several of the most important
features of OOP. To summarize:
• Objects contain both methods and fields (data).
• A class is a specification for any number of objects.
• To create an object, you use the keyword new in conjunction with the class name.
• To invoke a method for a particular object, you use the dot operator.
These concepts are deep and far reaching. It’s almost impossible to assimilate them the first time you see them, so don’t worry if you feel a bit confused. As you see more classes and what they do, the mist should start to clear.
1.7 A Runnable Object-Oriented Program
Let’s look at an object-oriented program that runs and generates actual output. It features a class called BankAccount that models a checking account at a bank. The program creates an account with an opening balance, displays the balance, makes a deposit and a withdrawal, and then displays the new balance.
The bank.java Program
// bank.java
// demonstrates basic OOP syntax
// to run this program: C>java BankApp
////////////////////////////////////////////////////////////////
class BankAccount
{
private double balance;
// account balance
public BankAccount(double openingBalance) // constructor
{
balance = openingBalance;
}
public void deposit(double amount) // makes deposit
{
balance = balance + amount;
}
public void withdraw(double amount) // makes withdrawal
{
balance = balance - amount;
}
public void display()
// displays balance
{
System.out.println(“balance=” + balance);
}
}
class BankApp
{
public static void main(String[] args)
{
BankAccount ba1 = new BankAccount(100.00); // create acct
System.out.print(“Before transactions, “);
ba1.display();
// display balance
ba1.deposit(74.35);
ba1.withdraw(20.00);
// make deposit
// make withdrawal
System.out.print(“After transactions, “);
ba1.display();
// display balance
} // end main()
}
// end class BankApp
Here’s the output from this program:
Before transactions, balance=100
After transactions, balance=154.35
There are two classes in bank.java. The first one, BankAccount, contains the fields and methods for our bank account. We’ll examine it in detail in a moment. The second class, BankApp, plays a special role.
The BankApp Class
To execute the program in Listing 1.1 from an MS-DOS prompt, you type java
BankApp following the C: prompt:
C:\>java BankApp
This command tells the java interpreter to look in the BankApp class for the method called main(). Every Java application must have a main() method; execution of the program starts at the beginning of main(), as you can see in Listing 1.1. (You don’t need to worry yet about the String[] args argument in main().)
The main() method creates an object of class BankAccount, initialized to a value of 100.00, which is the opening balance, with this statement:
BankAccount ba1 = new BankAccount(100.00); // create acct
The System.out.print() method displays the string used as its argument, Before
transactions:, and the account displays its balance with this statement:
ba1.display();
The program then makes a deposit to, and a withdrawal from, the account:
ba1.deposit(74.35);
ba1.withdraw(20.00);
Finally, the program displays the new account balance and terminates.
The BankAccount Class
The only data field in the BankAccount class is the amount of money in the account, called balance. There are three methods. The deposit() method adds an amount to the balance, withdrawal() subtracts an amount, and display() displays the balance.
Constructors
The BankAccount class also features a constructor, which is a special method that’s called automatically whenever a new object is created. A constructor always has exactly the same name as the class, so this one is called BankAccount(). This constructor has one argument, which is used to set the opening balance when the account is created.
A constructor allows a new object to be initialized in a convenient way. Without the constructor in this program, you would have needed an additional call to deposit() to put the opening balance in the account.
Public and Private
Notice the keywords public and private in the BankAccount class. These keywords are access modifiers and determine which methods can access a method or field. The balance field is preceded by private. A field or method that is private can be accessed only by methods that are part of the same class. Thus, balance cannot be accessed by statements in main() because main() is not a method in BankAccount.
All the methods in BankAccount have the access modifier public, however, so they can be accessed by methods in other classes. That’s why statements in main() can call deposit(), withdrawal(), and display().
Data fields in a class are typically made private and methods are made public. This protects the data; it can’t be accidentally modified by methods of other classes. Any outside entity that needs to access data in a class must do so using a method of the same class. Data is like a queen bee, kept hidden in the middle of the hive, fed and cared for by worker-bee methods.
1.8 Inheritance and Polymorphism
We’ll briefly mention two other key features of object-oriented programming: inheritance and polymorphism.
Inheritance is the creation of one class, called the extended or derived class, from another class called the base class. The extended class has all the features of the base class, plus some additional features. For example, a secretary class might be derived from a more general employee class and include a field called typingSpeed that the employee class lacked.
In Java, inheritance is also called subclassing. The base class may be called the superclass, and the extended class may be called the subclass.
Inheritance enables you to easily add features to an existing class and is an important aid in the design of programs with many related classes. Inheritance thus makes it easy to reuse classes for a slightly different purpose, a key benefit of OOP.
Polymorphism involves treating objects of different classes in the same way. For polymorphism to work, these different classes must be derived from the same base class.
In practice, polymorphism usually involves a method call that actually executes
different methods for objects of different classes.
For example, a call to display() for a secretary object would invoke a display
method in the secretary class, while the exact same call for a manager object would invoke a different display method in the manager class. Polymorphism simplifies and clarifies program design and coding.
For those not familiar with them, inheritance and polymorphism involve significant additional complexity. To keep the focus on data structures and algorithms, we have avoided these features in our example programs. Inheritance and polymorphism are important and powerful aspects of OOP but are not necessary for the explanation of data structures and algorithms.
1.9 Software Engineering
In recent years, it has become fashionable to begin a book on data structures and algorithms with a chapter on software engineering. We don’t follow that approach, but let’s briefly examine software engineering and see how it fits into the topics we discuss in this tutorial.
Software engineering is the study of ways to create large and complex computer
programs, involving many programmers. It focuses on the overall design of the
programs and on the creation of that design from the needs of the end users.
Software engineering is concerned with the life cycle of a software project, which includes specification, design, verification, coding, testing, production, and maintenance.
It’s not clear that mixing software engineering on one hand and data structures and algorithms on the other actually helps the student understand either topic. Software engineering is rather abstract and is difficult to grasp until you’ve been involved yourself in a large project. The use of data structures and algorithms, on the other hand, is a nuts-and-bolts discipline concerned with the details of coding and data storage.
Accordingly, we focus on the essentials of data structures and algorithms. How do they really work? What structure or algorithm is best in a particular situation? What do they look like translated into Java code? As we noted, our intent is to make the material as easy to understand as possible. For further reading, we mention some books on software engineering in Appendix B.
1.10 Java for C++ Programmers
If you’re a C++ programmer who has not yet encountered Java, you might want to read this section. We’ll mention several ways that Java differs from C++.
This section is not intended to be a primer on Java. We don’t even cover all the
differences between C++ and Java. We’re interested in only a few Java features that might make it hard for C++ programmers to figure out what’s going on in the example programs.
No Pointers
The biggest difference between C++ and Java is that Java doesn’t use pointers. To a C++ programmer, not using pointers may at first seem quite amazing. How can you get along without pointers?
Throughout this tutorial we’ll use pointer-free code to build complex data structures. You’ll see that this approach is not only possible, but actually easier than using C++ pointers.
Actually, Java only does away with explicit pointers. Pointers, in the form of memory addresses, are still there, under the surface. It’s sometimes said that, in Java, everything is a pointer. This statement is not completely true, but it’s close. Let’s look at the details.
References
Java treats primitive data types (such as int, float, and double) differently than
objects. Look at these two statements:
int intVar;
BankAccount bc1;
// an int variable called intVar
// reference to a BankAccount object
In the first statement, a memory location called intVar actually holds a numerical
value such as 127 (assuming such a value has been placed there). However, the
memory location bc1 does not hold the data of a BankAccount object. Instead, it
contains the address of a BankAccount object that is actually stored elsewhere in
memory. The name bc1 is a reference to this object; it’s not the object itself.
Actually, bc1 won’t hold a reference if it has not been assigned an object at some
prior point in the program. Before being assigned an object, it holds a reference to a special object called null. In the same way, intVar won’t hold a numerical value if it’s never been assigned one. The compiler will complain if you try to use a variable that has never been assigned a value.
In C++, the statement BankAccount bc1;
actually creates an object; it sets aside enough memory to hold all the object’s data. In Java, all this statement creates is a place to put an object’s memory address. You can think of a reference as a pointer with the syntax of an ordinary variable. (C++ has reference variables, but they must be explicitly specified with the & symbol.)
Assignment
It follows that the assignment operator (=) operates differently with Java objects than with C++ objects. In C++, the statement
bc2 = bc1;
copies all the data from an object called bc1 into a different object called bc2.
Following this statement, there are two objects with the same data. In Java, on the other hand, this same assignment statement copies the memory address that bc1 refers to into bc2. Both bc1 and bc2 now refer to exactly the same object; they are references to it.
This can get you into trouble if you’re not clear what the assignment operator does.
Following the assignment statement shown above, the statement
bc1.withdraw(21.00);
and the statement
bc2.withdraw(21.00);
both withdraw $21 from the same bank account object.
Suppose you actually want to copy data from one object to another. In this case you must make sure you have two separate objects to begin with and then copy each field separately. The equal sign won’t do the job.
The new Operator
Any object in Java must be created using new. However, in Java, new returns a reference, not a pointer as in C++. Thus, pointers aren’t necessary to use new. Here’s one way to create an object:
BankAccount ba1;
ba1 = new BankAccount();
Eliminating pointers makes for a more secure system. As a programmer, you can’t find out the actual address of ba1, so you can’t accidentally corrupt it. However, you probably don’t need to know it, unless you’re planning something wicked.
How do you release memory that you’ve acquired from the system with new and no longer need? In C++, you use delete. In Java, you don’t need to worry about releasing memory. Java periodically looks through each block of memory that was obtained with new to see if valid references to it still exist. If there are no such references, the block is returned to the free memory store. This process is called garbage collection.
In C++ almost every programmer at one time or another forgets to delete memory blocks, causing “memory leaks” that consume system resources, leading to bad performance and even crashing the system. Memory leaks can’t happen in Java (or at least hardly ever).
Arguments
In C++, pointers are often used to pass objects to functions to avoid the overhead of copying a large object. In Java, objects are always passed as references. This approach also avoids copying the object:
void method1()
{
BankAccount ba1 = new BankAccount(350.00);
method2(ba1);
}
void method2(BankAccount acct)
{
}
In this code, the references ba1 and acct both refer to the same object. In C++ acct would be a separate object, copied from ba1.
Primitive data types, on the other hand, are always passed by value. That is, a new variable is created in the method and the value of the argument is copied into it.
Equality and Identity
In Java, if you’re talking about primitive types, the equality operator (==) will tell you whether two variables have the same value:
int intVar1 = 27;
int intVar2 = intVar1;
if(intVar1 == intVar2)
System.out.println(“They’re equal”);
This is the same as the syntax in C and C++, but in Java, because relational operators use references, they work differently with objects. The equality operator, when applied to objects, tells you whether two references are identical—that is, whether they refer to the same object:
carPart cp1 = new carPart(“fender”);
carPart cp2 = cp1;
if(cp1 == cp2)
System.out.println(“They’re Identical”);
In C++ this operator would tell you if two objects contained the same data. If you want to see whether two objects contain the same data in Java, you must use the equals() method of the Object class:
carPart cp1 = new carPart(“fender”);
carPart cp2 = cp1;
if( cp1.equals(cp2) )
System.out.println(“They’re equal”);
This technique works because all objects in Java are implicitly derived from the
Object class.
Overloaded Operators
This point is easy: There are no overloaded operators in Java. In C++, you can redefine +, *, =, and most other operators so that they behave differently for objects of a particular class. No such redefinition is possible in Java. Use a named method instead, such as add() or whatever.
Primitive Variable Types
The primitive or built-in variable types in Java are shown in Table 1.2.
Unlike C and C++, which use integers for true/false values, boolean is a distinct type in Java.
Type char is unsigned, and uses two bytes to accommodate the Unicode character representation scheme, which can handle international characters.
The int type varies in size in C and C++, depending on the specific computer platform; in Java an int is always 32 bits.
Literals of type float use the suffix F (for example, 3.14159F); literals of type double need no suffix. Literals of type long use suffix L (as in 45L); literals of the other integer types need no suffix.
Java is more strongly typed than C and C++; many conversions that were automatic in those languages require an explicit cast in Java.
All types not shown in Table 1.2, such as String, are classes.
Input/Output
There have been changes to input/output as Java has evolved. For the console-mode applications we’ll be using as example programs in this tutorial, some clunky-looking but effective constructions are available for input and output. They’re quite different from the workhorse cout and cin approaches in C++ and printf() and scanf() in C.
Older versions of the Java Software Development Kit (SDK) required the line
import java.io.*;
at the beginning of the source file for all input/output routines. Now this line is
needed only for input.
Output
You can send any primitive type (numbers and characters), and String objects as
well, to the display with these statements:
System.out.print(var);
System.out.println(var);
// displays var, no linefeed
// displays var, then starts new line
The print() method leaves the cursor on the same line; println() moves it to the
beginning of the next line.
In older versions of the SDK, a System.out.print() statement did not actually write anything to the screen. It had to be followed by a System.out.println()or
System.out.flush() statement to display the entire buffer. Now it displays
immediately.
You can use several variables, separated by plus signs, in the argument. Suppose in this statement the value of ans is 33:
System.out.println(“The answer is “ + ans);
Then the output will be
The answer is 33
Inputting a String
Input is considerably more involved than output. In general, you want to read any input as a String object. If you’re actually inputting something else, say a character or number, you then convert the String object to the desired type.
As we noted, any program that uses input must include the statement
import java.io.*;
at the beginning of the program. Without this statement, the compiler will not
recognize such entities as IOException and InputStreamReader.
String input is fairly baroque. Here’s a method that returns a string entered by the user:
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
This method returns a String object, which is composed of characters typed on the keyboard and terminated with the Enter key. The details of the InputStreamReader and BufferedReader classes need not concern us here.
Besides importing java.io.*, you’ll need to add throws IOException to all input
methods, as shown in the preceding code. In fact, you’ll need to add throws
IOException to any method, such as main(), that calls any of the input methods.
Inputting a Character
Suppose you want your program’s user to enter a character. (By enter, we mean
typing something and pressing the Enter key.) The user may enter a single character or (incorrectly) more than one. Therefore, the safest way to read a character involves reading a String and picking off its first character with the charAt() method:
public static char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
The charAt() method of the String class returns a character at the specified position in the String object; here we get the first character, which is number 0. This approach prevents extraneous characters being left in the input buffer. Such characters can cause problems with subsequent input.
Inputting Integers
To read numbers, you make a String object as shown before and convert it to the
type you want using a conversion method. Here’s a method, getInt(), that converts input into type int and returns it:
public int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
The parseInt() method of class Integer converts the string to type int. A similar
routine, parseLong(), can be used to convert type long.
In older versions of the SDK, you needed to use the line
import java.lang.Integer;
at the beginning of any program that used parseInt(), but this convention is no
longer necessary.
For simplicity, we don’t show any error-checking in the input routines in the
example programs. The user must type appropriate input, or an exception will occur.
With the code shown here the exception will cause the program to terminate. In a serious program you should analyze the input string before attempting to convert it and should also catch any exceptions and process them appropriately.
Inputting Floating-Point Numbers
Types float and double can be handled in somewhat the same way as integers, but the conversion process is more complex. Here’s how you read a number of type double:
public int getDouble() throws IOException
{
String s = getString();
Double aDub = Double.valueOf(s);
return aDub.doubleValue();
}
The String is first converted to an object of type Double (uppercase D), which is a “wrapper” class for type double. A method of Double called doubleValue() then
converts the object to type double.
For type float, there’s an equivalent Float class, which has equivalent valueOf()
and floatValue() methods.
1.11 Java Library Data Structures
The java.util package contains data structures, such as Vector (an extensible array), Stack, Dictionary, and Hashtable. In this tutorial we’ll usually ignore these built-in classes. We’re interested in teaching fundamentals, not the details of a particular implementation. However, occasionally we’ll find some of these structures useful.
You must use the line
import java.util.*;
before you can use objects of these classes.
Although we don’t focus on them, such class libraries, whether those that come with Java or others available from third-party developers, can offer a rich source of versatile, debugged storage classes. This tutorial should equip you with the knowledge to know what sort of data structure you need and the fundamentals of how it works. Then you can decide whether you should write your own classes or use someone else’s.
Hi, nice Overview of Data Structures.Thanks for your help..
ReplyDelete-Aparna
Theosoft