Preface iii
Special Features xxiv
1 Introduction 1
1.1 Computer Programs 2
1.2 The Anatomy of a Computer 3
1.3 The Java Programming Language 5
1.4 Becoming Familiar with Your Programming Environment 7
1.5 Analyzing Your First Program 11
1.6 Errors 13
1.7 PROBLEM SOLVING Algorithm Design 15
The Algorithm Concept 15
An Algorithm for Solving an Investment Problem 16
Pseudocode 17
From Algorithms to Programs 18
2 Using Objects 23
2.1 Objects and Classes 24
Using Objects 24
Classes 25
2.2 Variables 26
Variable Declarations 26
Types 28
Names 29
Comments 30
Assignment 30
2.3 Calling Methods 33
The Public Interface of a Class 33
Method Arguments 34
Return Values 35
Method Declarations 36
2.4 Constructing Objects 38
2.5 Accessor and Mutator Methods 40
2.6 The API Documentation 41
Browsing the API Documentation 41
Packages 43
2.7 Implementing a Test Program 44
2.8 Object References 46
2.9 Graphical Applications 49
Frame Windows 50
Drawing on a Component 51
Displaying a Component in a Frame 53
2.10 Ellipses, Lines, Text, and Color 54
Ellipses and Circles 54
Lines 55
Drawing Text 56
Colors 56
3 Implementing Classes 61
3.1 Instance Variables and Encapsulation 62
Instance Variables 62
The Methods of the Counter Class 64
Encapsulation 64
3.2 Specifying the Public Interface of a Class 66
Specifying Methods 66
Specifying Constructors 67
Using the Public Interface 69
Commenting the Public Interface 69
3.3 Providing the Class Implementation 72
Providing Instance Variables 72
Providing Constructors 73
Providing Methods 75
3.4 Unit Testing 81
3.5 PROBLEM SOLVING Tracing Objects 84
3.6 Local Variables 86
3.7 The this Reference 88
3.8 Shape Classes 90
4 Fundamental Data Types 99
4.1 Numbers 100
Number Types 100
Constants 102
4.2 Arithmetic 107
Arithmetic Operators 107
Increment and Decrement 107
Integer Division and Remainder 108
Powers and Roots 109
Converting Floating-Point Numbers to Integers 110
4.3 Input and Output 114
Reading Input 114
Formatted Output 115
4.4 PROBLEM SOLVING First Do it By Hand 121
4.5 Strings 122
The String Type 122
Concatenation 123
String Input 124
Escape Sequences 124
Strings and Characters 124
Substrings 125
5 Decisions 131
5.1 The if Statement 132
5.2 Comparing Values 137
Relational Operators 138
Comparing Floating-Point Numbers 139
Comparing Strings 140
Comparing Objects 141
Testing for null 141
5.3 Multiple Alternatives 146
5.4 Nested Branches 149
5.5 PROBLEM SOLVING Flowcharts 156
5.6 PROBLEM SOLVING Selecting Test Cases 159
5.7 Boolean Variables and Operators 161
Operators 165
5.8 APPLICATION Input Validation 166
6 Loops 171
6.1 The while Loop 172
6.2 PROBLEM SOLVING Hand-Tracing 179
6.3 The for Loop 183
Header 189
6.4 The do Loop 190
6.5 APPLICATION Processing Sentinel Values 192
6.6 PROBLEM SOLVING Storyboards 197
6.7 Common Loop Algorithms 199
Sum and Average Value 199
Counting Matches 200
Finding the First Match 200
Prompting Until a Match is Found 201
Maximum and Minimum 201
Comparing Adjacent Values 202
6.8 Nested Loops 206
6.9 APPLICATION Random Numbers and Simulations 209
Generating Random Numbers 210
The Monte Carlo Method 211
6.10 Using a Debugger 213
7 Arrays and Array Lists 221
7.1 Arrays 222
Declaring and Using Arrays 222
Array References 225
Using Arrays with Methods 226
Partially Filled Arrays 226
Arguments 229
7.2 The Enhanced for Loop 230
7.3 Common Array Algorithms 232
Filling 232
Sum and Average Value 232
Maximum and Minimum 232
Element Separators 232
Linear Search 233
Removing an Element 234
Inserting an Element 234
Swapping Elements 236
Copying Arrays 237
Reading Input 238
7.4 PROBLEM SOLVING Adapting Algorithms 240
7.5 PROBLEM SOLVING Discovering Algorithms by Manipulating Physical Objects 245
7.6 Two-Dimensional Arrays 248
Declaring Two-Dimensional Arrays 248
Accessing Elements 249
Locating Neighboring Elements 250
Accessing Rows and Columns 251
Two-Dimensional Array Parameters 252
7.7 Array Lists 255
Declaring and Using Array Lists 255
Using the Enhanced for Loop with Array Lists 258
Copying Array Lists 259
Wrappers and Auto-boxing 259
Using Array Algorithms with Array Lists 260
Storing Input Values in an Array List 261
Removing Matches 261
Choosing Between Array Lists and Arrays 262
7.8 Regression Testing 264
8 Designing Classes 271
8.1 Discovering Classes 272
8.2 Designing Good Methods 273
Providing a Cohesive Public Interface 273
Minimizing Dependencies 274
Separating Accessors and Mutators 275
Minimizing Side Effects 276
8.3 PROBLEM SOLVING Patterns for Object Data 282
Keeping a Total 282
Counting Events 283
Collecting Values 283
Managing Properties of an Object 284
Modeling Objects with Distinct States 284
Describing the Position of an Object 285
8.4 Static Variables and Methods 286
8.5 PROBLEM SOLVING Solve a Simpler Problem First 291
8.6 Packages 295
Organizing Related Classes into Packages 295
Importing Packages 296
Package Names 297
Packages and Source Files 297
8.7 Unit Test Frameworks 300
9 Inheritance 305
9.1 Inheritance Hierarchies 306
9.2 Implementing Subclasses 310
9.3 Overriding Methods 314
9.4 Polymorphism 319
9.5 Object: The Cosmic Superclass 330
Overriding the toString Method 330
The equals Method 332
The instanceof Operator 333
10 Interfaces 339
10.1 Using Interfaces for Algorithm Reuse 340
Discovering an Interface Type 340
Declaring an Interface Type 341
Implementing an Interface Type 343
Comparing Interfaces and Inheritance 345
10.2 Working with Interface Variables 348
Converting from Classes to Interfaces 348
Invoking Methods on Interface Variables 349
Casting from Interfaces to Classes 349
10.3 The Comparable Interface 350
Interface 352
10.4 Using Interfaces for Callbacks 355
10.5 Inner Classes 360
10.6 Mock Objects 361
10.7 Event Handling 363
Listening to Events 363
Using Inner Classes for Listeners 365
10.8 Building Applications with Buttons 368
10.9 Processing Timer Events 371
10.10 Mouse Events 374
11 Input/Output and Exception Handling 383
11.1 Reading and Writing Text Files 384
11.2 Text Input and Output 389
Reading Words 389
Reading Characters 390
Classifying Characters 390
Reading Lines 390
Scanning a String 392
Converting Strings to Numbers 392
Avoiding Errors When Reading Numbers 392
Mixing Number, Word, and Line Input 393
Formatting Output 394
11.3 Command Line Arguments 396
11.4 Exception Handling 403
Throwing Exceptions 403
Catching Exceptions 405
Checked Exceptions 407
Closing Resources 409
Designing Your Own Exception Types 410
11.5 APPLICATION Handling Input Errors 412
12 Object-Oriented Design 419
12.1 Classes and Their Responsibilities 420
Discovering Classes 420
The CRC Card Method 421
12.2 Relationships Between Classes 423
Dependency 423
Aggregation 424
Inheritance 425
12.3 APPLICATION Printing an Invoice 428
Requirements 429
CRC Cards 429
UML Diagrams 432
Method Documentation 432
Implementation 434
13 Recursion 443
13.1 Triangle Numbers 444
13.2 Recursive Helper Methods 452
13.3 The Efficiency of Recursion 453
13.4 Permutations 459
13.5 Mutual Recursion 463
13.6 Backtracking 469
14 Sorting and Searching 477
14.1 Selection Sort 478
14.2 Profiling the Selection Sort Algorithm 481
14.3 Analyzing the Performance of the Selection Sort Algorithm 484
14.4 Merge Sort 488
14.5 Analyzing the Merge Sort Algorithm 491
14.6 Searching 495
Linear Search 495
Binary Search 497
14.7 PROBLEM SOLVING Estimating the Running Time of an Algorithm 500
Linear Time 500
Quadratic Time 501
The Triangle Pattern 502
Logarithmic Time 503
14.8 Sorting and Searching in the Java Library 504
Sorting 504
Binary Search 505
Comparing Objects 505
15 The Java Collections Framework 511
15.1 An Overview of the Collections Framework 512
15.2 Linked Lists 514
The Structure of Linked Lists 515
The LinkedList Class of the Java Collections Framework 516
List Iterators 516
15.3 Sets 520
Choosing a Set Implementation 520
Working with Sets 522
15.4 Maps 525
15.5 Stacks, Queues, and Priority Queues 531
Stacks 531
Queues 532
Priority Queues 533
15.6 Stack and Queue Applications 534
Balancing Parentheses 534
Evaluating Reverse Polish Expressions 535
Evaluating Algebraic Expressions 537
Backtracking 540
Customers 543
16 Basic Data Structures 545
16.1 Implementing Linked Lists 546
The Node Class 546
Adding and Removing the First Element 547
The Iterator Class 548
Advancing an Iterator 549
Removing an Element 550
Adding an Element 552
Setting an Element to a Different Value 553
Efficiency of Linked List Operations 553
16.2 Implementing Array Lists 560
Getting and Setting Elements 560
Removing or Adding Elements 562
Growing the Internal Array 563
16.3 Implementing Stacks and Queues 564
Stacks as Linked Lists 565
Stacks as Arrays 566
Queues as Linked Lists 567
Queues as Circular Arrays 568
16.4 Implementing a Hash Table 570
Hash Codes 570
Hash Tables 570
Finding an Element 572
Adding and Removing Elements 572
Iterating over a Hash Table 573
17 Tree Structures 581
17.1 Basic Tree Concepts 582
17.2 Binary Trees 585
Binary Tree Examples 586
Balanced Trees 588
A Binary Tree Implementation 589
17.3 Binary Search Trees 590
The Binary Search Property 591
Insertion 592
Removal 594
Efficiency of the Operations 595
17.4 Tree Traversal 599
Inorder Traversal 599
Preorder and Postorder Traversals 601
The Visitor Pattern 602
Depth-First and Breadth-First Search 603
Tree Iterators 604
17.5 Red-Black Trees 605
Basic Properties of Red-Black Trees 605
Insertion 607
Removal 608
17.6 Heaps 612
17.7 The Heapsort Algorithm 622
18 Generic Classes 629
18.1 Generic Classes and Type Parameters 630
18.2 Implementing Generic Types 631
18.3 Generic Methods 634
18.4 Constraining Type Parameters 636
18.5 Type Erasure 639
19 Stream Processing 645
19.1 The Stream Concept 646
19.2 Producing Streams 648
19.3 Collecting Results 649
19.4 Transforming Streams 652
19.5 Lambda Expressions 654
19.6 The Optional Type 659
19.7 Other Terminal Operations 661
19.8 Primitive-Type Streams 663
Creating Primitive-Type Streams 663
Mapping a Primitive-Type Stream 663
Processing Primitive-Type Streams 664
19.9 Grouping Results 665
19.10 Common Algorithms Revisited 667
Filling 667
Sum, Average, Maximum, and Minimum 668
Counting Matches 668
Element Separators 668
Linear Search 669
Comparing Adjacent Values 669
20 Graphical User Interfaces 675
20.1 Layout Management 676
Using Layout Managers 676
Achieving Complex Layouts 677
Using Inheritance to Customize Frames 678
20.2 Processing Text Input 680
Text Fields 680
Text Areas 682
20.3 Choices 685
Radio Buttons 685
Check Boxes 687
Combo Boxes 687
20.4 Menus 695
20.5 Exploring the Swing Documentation 702
21 Advanced Input/Output* (Etext Only)
21.1 Readers, Writers, and Input/Output Streams
21.2 Binary Input and Output
21.3 Random Access
21.4 Object Input and Output Streams
21.5 File and Directory Operations Paths
Creating and Deleting Files and Directories
Useful File Operations
Visiting Directories
22 Multithreading* (Etext Only)
22.1 Running Threads
22.2 Terminating Threads
22.3 Race Conditions
22.4 Synchronizing Object Access
22.5 Avoiding Deadlocks
22.6 APPLICATION Algorithm Animation
23 Internet Networking* (Etext Only)
23.1 The Internet Protocol
23.2 Application Level Protocols
23.3 A Client Program
23.4 A Server Program
23.5 URL Connections
24 Relational Databases* (Etext Only)
24.1 Organizing Database Information
Database Tables
Linking Tables
Implementing Multi-Valued Relationships
24.2 Queries
Simple Queries
Selecting Columns
Selecting Subsets
Calculations
Joins
Updating and Deleting Data
24.3 Installing a Database
24.4 Database Programming in Java
Connecting to the Database
Executing SQL Statements
Analyzing Query Results
Result Set Metadata
24.5 APPLICATION Entering an Invoice
25 XML* (Etext Only)
25.1 XML Tags and Documents
Advantages of XML
Differences Between XML and HTML
The Structure of an XML Document
25.2 Parsing XML Documents
25.3 Creating XML Documents
25.4 Validating XML Documents
Document Type Definitions
Specifying a DTD in an XML Document
Parsing and Validation
Appendix A The Basic Latin and Latin-1 Subsets of Unicode A-1
Appendix B JAVA Operator Summary A-5
Appendix C JAVA Reserved Word Summary A-7
Appendix D The Java Library A-9
Appendix E JAVA Language Coding Guidelines A-38
Appendix F Tool Summary (Etext Only)
Appendix G Number Systems (Etext Only)
Appendix H UML Summary (Etext Only)
Appendix I JAVA Syntax Summary (Etext Only)
Appendix J Html Summary (Etext Only)
Glossary G-1
Index I-1
Credits C-1
Quick Reference C-3
