Big Java

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