Introduction to Java Programming and Data Structures, Comprehensive Version

Front Cover......Page 1
Title Page......Page 3
Copyright Page......Page 4
Preface......Page 5
Contents......Page 14
Chapter 1 Introduction to Computers, Programs, and Java?......Page 25
1.2 What Is a Computer?......Page 26
1.3 Programming Languages......Page 31
1.4 Operating Systems......Page 33
1.5 Java, the World Wide Web, and Beyond......Page 34
1.6 The Java Language Specification, API, JDK, JRE, and IDE......Page 35
1.7 A Simple Java Program......Page 36
1.8 Creating, Compiling, and Executing a Java Program......Page 39
1.9 Programming Style and Documentation......Page 42
1.10 Programming Errors......Page 44
1.11 Developing Java Programs Using NetBeans......Page 47
1.12 Developing Java Programs Using Eclipse......Page 49
Chapter 2 Elementary Programming......Page 57
2.2 Writing a Simple Program......Page 58
2.3 Reading Input from the Console......Page 61
2.5 Variables......Page 64
2.6 Assignment Statements and Assignment Expressions......Page 66
2.7 Named Constants......Page 67
2.8 Naming Conventions......Page 68
2.9 Numeric Data Types and Operations......Page 69
2.10 Numeric Literals......Page 72
2.11 Evaluating Expressions and Operator Precedence......Page 74
2.12 Case Study: Displaying the Current Time......Page 76
2.13 Augmented Assignment Operators......Page 78
2.14 Increment and Decrement Operators......Page 79
2.15 Numeric Type Conversions......Page 81
2.16 Software Development Process......Page 83
2.17 Case Study: Counting Monetary Units......Page 87
2.18 Common Errors and Pitfalls......Page 89
Chapter 3 Selections......Page 99
3.2 boolean Data Type......Page 100
3.3 if Statements......Page 102
3.4 Two-Way if-else Statements......Page 104
3.5 Nested if and Multi-Way if-else Statements......Page 105
3.6 Common Errors and Pitfalls......Page 107
3.7 Generating Random Numbers......Page 111
3.8 Case Study: Computing Body Mass Index......Page 113
3.9 Case Study: Computing Taxes......Page 114
3.10 Logical Operators......Page 117
3.11 Case Study: Determining Leap Year......Page 121
3.12 Case Study: Lottery......Page 122
3.13 switch Statements......Page 124
3.14 Conditional Operators......Page 127
3.15 Operator Precedence and Associativity......Page 128
3.16 Debugging......Page 130
Chapter 4 Mathematical Functions, Characters, and Strings......Page 143
4.2 Common Mathematical Functions......Page 144
4.3 Character Data Type and Operations......Page 149
4.4 The String Type......Page 154
4.5 Case Studies......Page 163
4.6 Formatting Console Output......Page 169
Chapter 5 Loops......Page 183
5.2 The while Loop......Page 184
5.3 Case Study: Guessing Numbers......Page 187
5.4 Loop Design Strategies......Page 190
5.5 Controlling a Loop with User Confirmation or a Sentinel Value......Page 192
5.6 The do-while Loop......Page 194
5.7 The for Loop......Page 197
5.8 Which Loop to Use?......Page 200
5.9 Nested Loops......Page 202
5.10 Minimizing Numeric Errors......Page 204
5.11 Case Studies......Page 206
5.12 Keywords break and continue......Page 210
5.13 Case Study: Checking Palindromes......Page 213
5.14 Case Study: Displaying Prime Numbers......Page 215
Chapter 6 Methods......Page 229
6.2 Defining a Method......Page 230
6.3 Calling a Method......Page 232
6.4 void vs. Value-Returning Methods......Page 235
6.5 Passing Parameters by Values......Page 238
6.6 Modularizing Code......Page 241
6.7 Case Study: Converting Hexadecimals to Decimals......Page 243
6.8 Overloading Methods......Page 245
6.9 The Scope of Variables......Page 248
6.10 Case Study: Generating Random Characters......Page 249
6.11 Method Abstraction and Stepwise Refinement......Page 251
Chapter 7 Single-Dimensional Arrays......Page 271
7.2 Array Basics......Page 272
7.3 Case Study: Analyzing Numbers......Page 279
7.4 Case Study: Deck of Cards......Page 280
7.5 Copying Arrays......Page 282
7.6 Passing Arrays to Methods......Page 283
7.7 Returning an Array from a Method......Page 286
7.8 Case Study: Counting the Occurrences of Each Letter......Page 287
7.9 Variable-Length Argument Lists......Page 290
7.10 Searching Arrays......Page 291
7.11 Sorting Arrays......Page 295
7.12 The Arrays Class......Page 296
7.13 Command-Line Arguments......Page 298
Chapter 8 Multidimensional Arrays......Page 313
8.2 Two-Dimensional Array Basics......Page 314
8.3 Processing Two-Dimensional Arrays......Page 317
8.4 Passing Two-Dimensional Arrays to Methods......Page 319
8.5 Case Study: Grading a Multiple-Choice Test......Page 320
8.6 Case Study: Finding the Closest Pair......Page 322
8.7 Case Study: Sudoku......Page 324
8.8 Multidimensional Arrays......Page 327
Chapter 9 Objects and Classes......Page 347
9.2 Defining Classes for Objects......Page 348
9.3 Example: Defining Classes and Creating Objects......Page 350
9.4 Constructing Objects Using Constructors......Page 355
9.5 Accessing Objects via Reference Variables......Page 356
9.6 Using Classes from the Java Library......Page 360
9.7 Static Variables, Constants, and Methods......Page 363
9.8 Visibility Modifiers......Page 368
9.9 Data Field Encapsulation......Page 370
9.10 Passing Objects to Methods......Page 373
9.11 Array of Objects......Page 377
9.12 Immutable Objects and Classes......Page 379
9.13 The Scope of Variables......Page 381
9.14 The this Reference......Page 382
Chapter 10 Object-Oriented Thinking......Page 391
10.2 Class Abstraction and Encapsulation......Page 392
10.3 Thinking in Objects......Page 396
10.4 Class Relationships......Page 399
10.5 Case Study: Designing the Course Class......Page 402
10.6 Case Study: Designing a Class for Stacks......Page 404
10.7 Processing Primitive Data Type Values as Objects......Page 406
10.8 Automatic Conversion between Primitive Types and Wrapper Class Types......Page 409
10.9 The BigInteger and BigDecimal Classes......Page 410
10.10 The String Class......Page 412
10.11 The StringBuilder and StringBuffer Classes......Page 418
Chapter 11 Inheritance and Polymorphism......Page 435
11.2 Superclasses and Subclasses......Page 436
11.3 Using the super Keyword......Page 442
11.4 Overriding Methods......Page 445
11.5 Overriding vs. Overloading......Page 446
11.6 The Object Class and Its toString() Method......Page 448
11.8 Dynamic Binding......Page 449
11.9 Casting Objects and the instanceof Operator......Page 453
11.10 The Object?s equals Method......Page 457
11.11 The ArrayList Class......Page 458
11.12 Useful Methods for Lists......Page 464
11.13 Case Study: A Custom Stack Class......Page 465
11.14 The protected Data and Methods......Page 466
11.15 Preventing Extending and Overriding......Page 469
Chapter 12 Exception Handling and Text I/O......Page 477
12.2 Exception-Handling Overview......Page 478
12.3 Exception Types......Page 483
12.4 More on Exception Handling......Page 486
12.5 The finally Clause......Page 494
12.6 When to Use Exceptions......Page 495
12.7 Rethrowing Exceptions......Page 496
12.8 Chained Exceptions......Page 497
12.9 Defining Custom Exception Classes......Page 498
12.10 The File Class......Page 501
12.11 File Input and Output......Page 504
12.12 Reading Data from the Web......Page 510
12.13 Case Study: Web Crawler......Page 512
Chapter 13 Abstract Classes and Interfaces......Page 523
13.2 Abstract Classes......Page 524
13.3 Case Study: the Abstract Number Class......Page 529
13.4 Case Study: Calendar and GregorianCalendar......Page 531
13.5 Interfaces......Page 534
13.6 The Comparable Interface......Page 537
13.7 The Cloneable Interface......Page 542
13.8 Interfaces vs. Abstract Classes......Page 547
13.9 Case Study: The Rational Class......Page 550
13.10 Class-Design Guidelines......Page 555
Chapter 14 JavaFX Basics......Page 565
14.3 The Basic Structure of a JavaFX Program......Page 566
14.4 Panes, Groups, UI Controls, and Shapes......Page 569
14.5 Property Binding......Page 572
14.6 Common Properties and Methods for Nodes......Page 575
14.7 The Color Class......Page 577
14.8 The Font Class......Page 578
14.9 The Image and ImageView Classes......Page 580
14.10 Layout Panes and Groups......Page 582
14.11 Shapes......Page 591
14.12 Case Study: The ClockPane Class......Page 604
Chapter 15 Event-Driven Programming and Animations......Page 617
15.1 Introduction......Page 618
15.2 Events and Event Sources......Page 620
15.3 Registering Handlers and Handling Events......Page 621
15.4 Inner Classes......Page 625
15.5 Anonymous Inner Class Handlers......Page 626
15.6 Simplifying Event Handling Using Lambda Expressions......Page 629
15.7 Case Study: Loan Calculator......Page 633
15.8 Mouse Events......Page 635
15.9 Key Events......Page 637
15.10 Listeners for Observable Objects......Page 640
15.11 Animation......Page 642
15.12 Case Study: Bouncing Ball......Page 650
15.13 Case Study: US Map......Page 654
Chapter 16 JavaFX UI Controls and Multimedia......Page 667
16.2 Labeled and Label......Page 668
16.3 Button......Page 670
16.4 CheckBox......Page 672
16.5 RadioButton......Page 675
16.6 TextField......Page 678
16.7 TextArea......Page 679
16.8 ComboBox......Page 683
16.9 ListView......Page 686
16.10 ScrollBar......Page 689
16.11 Slider......Page 692
16.12 Case Study: Developing a Tic-Tac-Toe Game......Page 695
16.13 Video and Audio......Page 700
16.14 Case Study: National Flags and Anthems......Page 703
Chapter 17 Binary I/O......Page 715
17.2 How Is Text I/O Handled in Java?......Page 716
17.3 Text I/O vs. Binary I/O......Page 717
17.4 Binary I/O Classes......Page 718
17.5 Case Study: Copying Files......Page 728
17.6 Object I/O......Page 730
17.7 Random-Access Files......Page 735
Chapter 18 Recursion......Page 743
18.2 Case Study: Computing Factorials......Page 744
18.3 Case Study: Computing Fibonacci Numbers......Page 747
18.4 Problem Solving Using Recursion......Page 750
18.5 Recursive Helper Methods......Page 752
18.6 Case Study: Finding the Directory Size......Page 755
18.7 Case Study: Tower of Hanoi......Page 757
18.8 Case Study: Fractals......Page 760
18.10 Tail Recursion......Page 764
Chapter 19 Generics......Page 775
19.2 Motivations and Benefits......Page 776
19.3 Defining Generic Classes and Interfaces......Page 778
19.4 Generic Methods......Page 780
19.5 Case Study: Sorting an Array of Objects......Page 782
19.6 Raw Types and Backward Compatibility......Page 784
19.7 Wildcard Generic Types......Page 785
19.8 Erasure and Restrictions on Generics......Page 788
19.9 Case Study: Generic Matrix Class......Page 790
Chapter 20 Lists, Stacks, Queues, and Priority Queues......Page 799
20.2 Collections......Page 800
20.3 Iterators......Page 804
20.4 Using the forEach Method......Page 805
20.5 Lists......Page 806
20.6 The Comparator Interface......Page 811
20.7 Static Methods for Lists and Collections......Page 815
20.8 Case Study: Bouncing Balls......Page 818
20.9 Vector and Stack Classes......Page 822
20.10 Queues and Priority Queues......Page 823
20.11 Case Study: Evaluating Expressions......Page 827
Chapter 21 Sets and Maps......Page 839
21.2 Sets......Page 840
21.3 Comparing the Performance of Sets and Lists......Page 848
21.4 Case Study: Counting Keywords......Page 851
21.5 Maps......Page 852
21.6 Case Study: Occurrences of Words......Page 857
21.7 Singleton and Unmodifiable Collections and Maps......Page 859
Chapter 22 Developing Efficient Algorithms......Page 863
22.2 Measuring Algorithm Efficiency Using Big O Notation......Page 864
22.3 Examples: Determining Big O......Page 866
22.4 Analyzing Algorithm Time Complexity......Page 870
22.5 Finding Fibonacci Numbers Using Dynamic Programming......Page 873
22.6 Finding Greatest Common Divisors Using Euclid?s Algorithm......Page 875
22.7 Efficient Algorithms for Finding Prime Numbers......Page 879
22.8 Finding the Closest Pair of Points Using Divide-and-Conquer......Page 885
22.9 Solving the Eight Queens Problem Using Backtracking......Page 888
22.10 Computational Geometry: Finding a Convex Hull......Page 891
Chapter 23 Sorting......Page 905
23.2 Insertion Sort......Page 906
23.3 Bubble Sort......Page 908
23.4 Merge Sort......Page 911
23.5 Quick Sort......Page 914
23.6 Heap Sort......Page 918
23.7 Bucket and Radix Sorts......Page 925
23.8 External Sort......Page 927
Chapter 24 Implementing Lists, Stacks, Queues, and Priority Queues......Page 941
24.2 Common Operations for Lists......Page 942
24.3 Array Lists......Page 946
24.4 Linked Lists......Page 953
24.5 Stacks and Queues......Page 967
24.6 Priority Queues......Page 971
Chapter 25 Binary Search Trees......Page 977
25.2 Binary Search Trees......Page 978
25.3 Deleting Elements from a BST......Page 991
25.4 Tree Visualization and MVC......Page 997
25.5 Iterators......Page 1000
25.6 Case Study: Data Compression......Page 1002
Chapter 26 AVL Trees......Page 1013
26.2 Rebalancing Trees......Page 1014
26.3 Designing Classes for AVL Trees......Page 1017
26.4 Overriding the insert Method......Page 1018
26.5 Implementing Rotations......Page 1019
26.7 The AVLTree Class......Page 1020
26.8 Testing the AVLTree Class......Page 1026
26.9 AVL Tree Time Complexity Analysis......Page 1029
Chapter 27 Hashing......Page 1033
27.2 What Is Hashing?......Page 1034
27.3 Hash Functions and Hash Codes......Page 1035
27.4 Handling Collisions Using Open Addressing......Page 1037
27.6 Load Factor and Rehashing......Page 1041
27.7 Implementing a Map Using Hashing......Page 1043
27.8 Implementing Set Using Hashing......Page 1052
Chapter 28 Graphs and Applications......Page 1063
28.1 Introduction......Page 1064
28.2 Basic Graph Terminologies......Page 1065
28.3 Representing Graphs......Page 1066
28.4 Modeling Graphs......Page 1072
28.5 Graph Visualization......Page 1082
28.6 Graph Traversals......Page 1085
28.7 Depth-First Search (DFS)......Page 1086
28.8 Case Study: The Connected Circles Problem......Page 1090
28.9 Breadth-First Search (BFS)......Page 1092
28.10 Case Study: The Nine Tails Problem......Page 1095
Chapter 29 Weighted Graphs and Applications......Page 1109
29.1 Introduction......Page 1110
29.2 Representing Weighted Graphs......Page 1111
29.3 The WeightedGraph Class......Page 1113
29.4 Minimum Spanning Trees......Page 1121
29.5 Finding Shortest Paths......Page 1127
29.6 Case Study: The Weighted Nine Tails Problem......Page 1136
Chapter 30 Aggregate Operations for Collection Streams......Page 1147
30.2 Stream Pipelines......Page 1148
30.3 IntStream, LongStream, and DoubleStream......Page 1154
30.4 Parallel Streams......Page 1157
30.5 Stream Reduction Using the reduce Method......Page 1159
30.6 Stream Reduction Using the collect Method......Page 1162
30.7 Grouping Elements Using the groupingby Collector......Page 1165
30.8 Case Studies......Page 1168
Chapter 31 Advanced JavaFX and FXML......Page 1179
Chapter 32 Multithreading and Parallel Programming......Page 1228
Chapter 33 Networking......Page 1270
Chapter 34 Java Database Programming......Page 1303
Chapter 35 Advanced Java Database Programming......Page 1342
Chapter 36 Internationalization......Page 1368
Chapter 37 Servlets......Page 1401
Chapter 38 Javaserver Pages......Page 1447
Chapter 39 Javaserver Faces......Page 1481
Chapter 40 Remote Method Invocation......Page 1533
Chapter 41 Web Services......Page 1558
Chapter 42 2-4 Trees and B-Trees......Page 1581
Chapter 43 Red-Black Trees......Page 1609
Chapter 44 Testing Using Junit......Page 1639
Appendixes......Page 1655
Appendix A Java Keywords......Page 1657
Appendix B The ASCII Character Set......Page 1658
Appendix C Operator Precedence Chart......Page 1660
Appendix D Java Modifiers......Page 1662
Appendix E Special Floating-Point Values......Page 1664
Appendix F Number System......Page 1665
Appendix G Bitwise Operations......Page 1669
Appendix H Regular Expressions......Page 1670
Appendix I Enumerated Types......Page 1675
Quick Reference......Page 1681
Index......Page 1683
Back Cover......Page 1711