Preface vii
Chapter 1 Introduction 1
1.1 The Java Programming Language 2
A Java Program 3
Comments 5
Identifiers and Reserved Words 7
White Space 9
1.2 Program Development 11
Programming Language Levels 11
Editors, Compilers, and Interpreters 13
Development Environments 15
Syntax and Semantics 16
Errors 17
1.3 Problem Solving 18
1.4 Software Development Activities 20
1.5 Object-Oriented Programming 21
Object-Oriented Software Principles 22
Chapter 2 Data and Expressions 33
2.1 Character Strings 34
The print and println Methods 34
String Concatenation 36
Escape Sequences 40
2.2 Variables and Assignment 41
Variables 41
The Assignment Statement 44
Constants 46
2.3 Primitive Data Types 47
Integers and Floating Points 47
Characters 48
Booleans 50
2.4 Expressions 51
Arithmetic Operators 51
Operator Precedence 52
Increment and Decrement Operators 56
Assignment Operators 57
2.5 Data Conversion 58
Conversion Techniques 60
2.6 Reading Input Data 61
The Scanner Class 61
Chapter 3 Using Classes and Objects 75
3.1 Creating Objects 76
Aliases 78
3.2 The String Class 80
3.3 Packages 83
The import Declaration 84
3.4 The Random Class 86
3.5 The Math Class 89
3.6 Formatting Output 92
The NumberFormat Class 92
The DecimalFormat Class 94
The printf Method 96
3.7 Enumerated Types 97
3.8 Wrapper Classes 100
Autoboxing 102
Chapter 4 Conditionals and Loops 111
4.1 Boolean Expressions 112
Equality and Relational Operators 113
Logical Operators 114
4.2 The if Statement 116
The if-else Statement 119
Using Block Statements 121
The Conditional Operator 124
Nested if Statements 125
4.3 Comparing Data 127
Comparing Floats 127
Comparing Characters 127
Comparing Objects 128
4.4 The switch Statement 130
4.5 The while Statement 134
Infinite Loops 140
Nested Loops 141
Other Loop Controls 144
4.6 Iterators 145
Reading Text Files 146
4.7 The do Statement 148
4.8 The for Statement 151
Iterators and for Loops 156
Comparing Loops 157
Chapter 5 Writing Classes 169
5.1 Classes and Objects Revisited 170
Identifying Classes and Objects 171
Assigning Responsibilities 173
5.2 Anatomy of a Class 173
Instance Data 178
UML Class Diagrams 179
5.3 Encapsulation 181
Visibility Modifiers 182
Accessors and Mutators 183
5.4 Anatomy of a Method 188
The return Statement 194
Parameters 196
Local Data 197
Constructors Revisited 198
5.5 Static Class Members 199
Static Variables 199
Static Methods 200
5.6 Class Relationships 203
Dependency 203
Dependencies among Objects of the Same Class 204
Aggregation 206
The this Reference 211
5.7 Method Design 212
Method Decomposition 213
Method Parameters Revisited 218
5.8 Method Overloading 223
5.9 Testing 224
Reviews 225
Defect Testing 226
Unit Testing 227
Integration Testing 228
System Testing 228
Test-Driven Development 228
5.10 Debugging 229
Simple Debugging with print Statements 230
Debugging Concepts 230
Chapter 6 Graphical User Interfaces 245
6.1 GUI Elements 246
Frames and Panels 247
Buttons and Action Events 251
Determining Event Sources 253
6.2 More Components 256
Text Fields 257
Check Boxes 260
Radio Buttons 263
Sliders 267
Combo Boxes 272
Timers 277
6.3 Layout Managers 282
Flow Layout 285
Border Layout 288
Grid Layout 291
Box Layout 293
Containment Hierarchies 296
6.4 Mouse and Key Events 297
Mouse Events 297
Key Events 305
Extending Adapter Classes 310
6.5 Dialog Boxes 311
File Choosers 314
Color Choosers 316
6.6 Some Important Details 317
Borders 317
Tool Tips and Mnemonics 321
6.7 GUI Design 328
Chapter 7 Arrays 339
7.1 Array Elements 340
Overview of Arrays 341
7.2 Declaring and Using Arrays 341
Bounds Checking 344
Alternative Array Syntax 349
Initializer Lists 350
Arrays as Parameters 351
7.3 Arrays of Objects 351
7.4 Command-Line Arguments 361
7.5 Variable-Length Parameter Lists 363
7.6 Two-Dimensional Arrays 367
Multidimensional Arrays 370
Chapter 8 Inheritance 379
8.1 C reating Subclasses 380
The protected Modifier 385
The super Reference 386
Multiple Inheritance 390
8.2 Overriding Methods 391
Shadowing Variables 394
8.3 C lass Hierarchies 394
The Object Class 395
Abstract Classes 397
8.4 Visibility 399
8.5 Designing for Inheritance 401
Restricting Inheritance 402
Chapter 9 Polymorphism 411
9.1 Dynamic Binding 412
9.2 Polymorphism via Inheritance 413
9.3 Interfaces 425
Interface Hierarchies 430
The Comparable Interface 431
The Iterator Interface 431
9.4 Polymorphism via Interfaces 432
Event Processing 434
Chapter 10 Exceptions 441
10.1 Exception Handling 442
10.2 Uncaught Exceptions 443
10.3 The try-catch Statement 444
The finally Clause 447
10.4 Exception Propagation 448
10.5 The Exception Class Hierarchy 451
Checked and Unchecked Exceptions 455
10.6 I/O Exceptions 455
Chapter 11 Analysis of Algorithms 465
11.1 Algorithm Efficiency 466
11.2 Growth Functions and Big-Oh Notation 467
11.3 Comparing Growth Functions 469
11.4 Determining Time Complexity 471
Analyzing Loop Execution 471
Nested Loops 472
Method Calls 473
Chapter 12 Introduction to Collections-Stacks 479
12.1 Collections 480
Abstract Data Types 481
The Java Collections API 483
12.2 A Stack Collection 483
12.3 C rucial OO Concepts 485
Inheritance and Polymorphism 486
Generics 487
12.4 Using Stacks: Evaluating Postfix Expressions 488
Javadoc 496
12.5 Exceptions 497
12.6 A Stack ADT 498
12.7 Implementing a Stack: With Arrays 501
Managing Capacity 502
12.8 The ArrayStack Class 503
The Constructors 504
The push Operation 506
The pop Operation 508
The peek Operation 509
Other Operations 509
The EmptyCollectionException Class 510
Other Implementations 511
Chapter 13 Linked Structures-Stacks 519
13.1 References as Links 520
13.2 Managing Linked Lists 522
Accessing Elements 522
Inserting Nodes 523
Deleting Nodes 524
13.3 Elements without Links 525
Doubly Linked Lists 525
13.4 Stacks in the Java API 526
13.5 Using Stacks: Traversing a Maze 527
13.6 Implementing a Stack: With Links 536
The LinkedStack Class 536
The push Operation 540
The pop Operation 542
Other Operations 543
Chapter 14 Queues 549
14.1 A Conceptual Queue 550
14.2 Queues in the Java API 551
14.3 Using Queues: Code Keys 552
14.4 Using Queues: Ticket Counter Simulation 556
14.5 A Queue ADT 561
14.6 A Linked Implementation of a Queue 562
The enqueue Operation 564
The dequeue Operation 566
Other Operations 567
14.7 Implementing Queues: With Arrays 568
The enqueue Operation 572
The dequeue Operation 574
Other Operations 575
14.8 Double-Ended Queues (Deque) 575
Chapter 15 Lists 581
15.1 A List Collection 582
15.2 Lists in the Java Collections API 584
15.3 Using Unordered Lists: Program of Study 585
15.4 Using Indexed Lists: Josephus 595
15.5 A List ADT 597
Adding Elements to a List 598
15.6 Implementing Lists with Arrays 603
The remove Operation 605
The contains Operation 607
The add Operation for an Ordered List 608
Operations Particular to Unordered Lists 609
The addAfter Operation for an
Unordered List 609
15.7 Implementing Lists with Links 610
The remove Operation 611
Chapter 16 Iterators 619
16.1 What's an Iterator? 620
Other Iterator Issues 622
16.2 Using Iterators: Program of Study Revisited 622
Printing Certain Courses 626
Removing Courses 627
16.3 Implementing Iterators: With Arrays 629
16.4 Implementing Iterators: With Links 631
Chapter 17 Recursion 637
17.1 Recursive Thinking 638
Infinite Recursion 638
Recursion in Math 639
17.2 Recursive Programming 640
Recursion versus Iteration 643
Direct versus Indirect Recursion 643
17.3 Using Recursion 644
Traversing a Maze 644
The Towers of Hanoi 652
17.4 Analyzing Recursive Algorithms 657
Chapter 18 Searching and Sorting 665
18.1 Searching 666
Static Methods 667
Generic Methods 667
Linear Search 668
Binary Search 670
Comparing Search Algorithms 672
18.2 Sorting 673
Selection Sort 676
Insertion Sort 678
Bubble Sort 680
Quick Sort 682
Merge Sort 686
18.3 Radix Sort 689
Chapter 19 Trees 699
19.1 Trees 700
Tree Classifications 701
19.2 Strategies for Implementing Trees 703
Computational Strategy for Array
Implementation of Trees 703
Simulated Link Strategy for Array
Implementation of Trees 703
Analysis of Trees
19.3 Tree Traversals 706
Preorder Traversal 706
Inorder Traversal 707
Postorder Traversal 707
Level-Order Traversal 708
19.4 A Binary Tree ADT 709
19.5 Using Binary Trees: Expression Trees 713
19.6 A Backpain Analyzer 725
19.7 Implementing Binary Trees with Links 729
The find Method 734
The iteratorInOrder Method 736
Chapter 20 Binary Search Trees 743
20.1 A Binary Search Tree 744
20.2 Implementing Binary Search Trees: With Links 746
The addElement Operation 747
The removeElement Operation 750
The removeAllOccurrences Operation 753
The removeMin Operation 754
Implementing Binary Search Trees: With Arrays 756
20.3 Using Binary Search Trees: Implementing
Ordered Lists 756
Analysis of the BinarySearchTreeList
Implementation 759
20.4 Balanced Binary Search Trees 760
Right Rotation 761
Left Rotation 762
Rightleft Rotation 763
Leftright Rotation 763
20.5 Implementing Binary Search Trees: AVL Trees 764
Right Rotation in an AVL Tree 765
Left Rotation in an AVL Tree 765
Rightleft Rotation in an AVL Tree 765
Leftright Rotation in an AVL Tree 767
20.6 Implementing Binary Search Trees: Red/Black Trees 767
Insertion into a Red/Black Tree 768
Element Removal from a Red/Black Tree 771
Chapter 21 Heaps and Priority Queues 781
21.1 A Heap 782
The addElement Operation 784
The removeMin Operation 785
The findMin Operation 786
21.2 Using Heaps: Priority Queues 786
The addElement Operation 790
The removeMin Operation 794
The findMin Operation 797
21.4 Implementing Heaps: With Arrays 797
The addElement Operation 799
The removeMin Operation 800
The findMin Operation 802
21.5 Using Heaps: Heap Sort 802
Chapter 22 Sets and Maps 809
22.1 Set and Map Collections 810
22.2 Sets and Maps in the Java API 810
22.3 Using Sets: Domain Blocker 813
22.4 Using Maps: Product Sales 816
22.5 Using Maps: User Management 820
22.6 Implementing Sets and Maps Using Trees 825
22.7 Implementing Sets and Maps Using Hashing 825
Chapter 23 Multi-way Search Trees 833
23.1 Combining Tree Concepts 834
23.2 2-3 Trees 834
Inserting Elements into a 2-3 Tree 835
Removing Elements from a 2-3 Tree 837
23.3 2-4 Trees 840
23.4 B-Trees 842
B*-Trees 843
B+-Trees 843
Analysis of B-Trees 844
23.5 Implementation Strategies for B-Trees 844
Chapter 24 Graphs 1
24.1 Undirected Graphs 2
24.2 Directed Graphs 3
24.3 Networks 5
24.4 Common Graph Algorithms 6
Traversals 6
Testing for Connectivity 10
Minimum Spanning Trees 12
Determining the Shortest Path 15
24.5 Strategies for Implementing Graphs 15
Adjacency Lists 16
Adjacency Matrices 16
24.6 Implementing Undirected Graphs with an
Adjacency Matrix 17
The addEdge Method 22
The addVertex Method 22
The expandCapacity Method 23
Other Methods 24
Chapter 25 Databases 781
25.1 Introduction to Databases 782
25.2 Establishing a Connection to a Database 784
Obtaining a Database Driver 784
25.3 Creating and Altering Database Tables 787
Create Table 787
Alter Table 788
Drop Column 789
25.4 Querying the Database 789
Show Columns 790
25.5 Inserting, Viewing, and Updating Data 792
Insert 793
SELECT . . . FROM 793
Update 798
25.6 Deleting Data and Database Tables 799
Deleting Data 799
Deleting Database Tables 800
Appendix A Glossary 905
Appendix B Number Systems 939
Place Value 940
Bases Higher Than 10 941
Conversions 942
Shortcut Conversions 945
Appendix C The Unicode Character Set 951
Appendix D Java Operators 955
Java Bitwise Operators 957
Appendix E Java Modifiers 961
Java Visibility Modifiers 962
A Visibility Example 962
Other Java Modifiers 963
Appendix F Java Graphics 965
Coordinate Systems 966
Representing Color 966
Drawing Shapes 967
Polygons and Polylines 976
The Polygon Class 980
Appendix G Java Applets 985
Embedding Applets in HTML 988
More Applet Methods 988
GUIs in Applets 993
Appendix H Regular Expressions 1003
Appendix I Hashing 1005
I.1 A Hashing 1006
I.2 Hashing Functions 1007
The Division Method 1008
The Folding Method 1008
The Mid-Square Method 1009
The Radix Transformation Method 1009
The Digit Analysis Method 1009
The Length-Dependent Method 1010
Hashing Functions in the Java Language 1010
I.3 Resolving Collisions 1010
Chaining 1011
Open Addressing 1012
I.4 Deleting Elements from a Hash Table 1015
Deleting from a Chained Implementation 1015
Deleting from an Open Addressing
Implementation 1016
I.5 Hash Tables in the Java Collections API 1017
The Hashtable Class 1017
The HashSet Class 1019
The HashMap Class 1019
The IdentityHashMap Class 1020
I.6 The WeakHashMap Class 1021
LinkedHashSet and LinkedHashMap 1022
Appendix J Java Syntax 1029
Index 1043
