Tabs for Contents, notes, highlights

Contents
Notes
Highlights

Detailed Table of Contents

Hide Contents, Notes, and Highlights

Search TermsShow Hide

« Back to eTextbook

Copyright, ii
Preface, v
Introduction, 1
1. Java Classes, 5
Objects and Classes, 6
Using the Methods in a Java Class, 8
Defining a Java Class, 10
Enumeration as a Class, 26
Chapter Summary, 30
Programming Tips, 32
Exercises, 32
Projects, 34
2. Creating Classes from Other Classes, 39
Composition, 40
Type Compatibility and Base Classes, 58
Polymorphism, 63
Chapter Summary, 68
Programming Tips, 69
Exercises, 69
Projects, 73
3. Designing Classes, 77
Encapsulation, 78
Specifying Methods, 80
Java Interfaces, 84
Choosing Classes, 95
Reusing Classes, 100
Chapter Summary, 101
Programming Tips, 101
Exercises, 102
Projects, 103
4. Lists, 107
Specifications for the ADT List, 108
Using the ADT List, 116
Using a List Is Like Using a Vending Machine, 120
Java Class Library: The Interface List, 122
Chapter Summary, 122
Programming Tips, 123
Exercises, 123
Projects, 125
5. List Implementations That Use Arrays, 127
Using a Fixed-Size Array to Implement the ADT List, 128
Using Array Expansion to Implement the ADT List, 138
Java Class Library: The Classes ArrayList and Vector, 142
The Pros and Cons of Using an Array to Implement the ADT List, 146
Chapter Summary, 147
Programming Tips, 147
Exercises, 147
Projects, 149
6. A List Implementation That Links Data, 151
Linked Data, 152
A Linked Implementation of the ADT List, 160
Testing the Incomplete Implementation, 173
Chapter Summary, 175
Programming Tips, 175
Exercises, 175
Projects, 177
7. Completing the Linked Implementation of a List, 179
Removing an Item from a Linked Chain, 180
Completing the Linked Implementation of the ADT List, 183
A Class Node That Has Set and Get Methods, 188
Tail References, 191
The Pros and Cons of Using a Chain to Implement the ADT List, 196
Java Class Library: The Class LinkedList, 196
Chapter Summary, 197
Exercises, 197
Projects, 198
8. Iterators, 201
What Is an Iterator?, 202
The Interface Iterator, 203
A Separate Class Iterator, 210
Why Are Iterator Methods in Their Own Class?, 221
The Interface ListIterator, 222
An Array-Based Implementation of the Interface ListIterator, 228
Java Class Library: The Interface Iterable, 235
Chapter Summary, 237
Programming Tips, 237
Exercises, 238
Projects, 240
9. The Efficiency of Algorithms, 243
Motivation, 244
Measuring an Algorithm’s Efficiency, 246
Formalities, 252
Picturing Efficiency, 255
The Efficiency of Implementations of the ADT List, 258
Chapter Summary, 264
Programming Tip, 264
Exercises, 264
Projects, 267
10. Recursion, 269
What Is Recursion?, 270
Tracing a Recursive Method, 275
Recursive Methods That Return a Value, 277
Recursively Processing an Array, 280
Recursively Processing a Linked Chain, 282
A Simple Solution to a Difficult Problem, 287
A Poor Solution to a Simple Problem, 292
Tail Recursion, 294
Mutual Recursion, 296
Chapter Summary, 297
Programming Tips, 298
Exercises, 298
11. An Introduction to Sorting, 305
Organizing Java Methods That Sort an Array, 306
Selection Sort, 308
Insertion Sort, 313
Shell Sort, 322
Comparing the Algorithms, 325
Chapter Summary, 325
Programming Tip, 326
Exercises, 326
Projects, 329
12. Faster Sorting Methods, 331
Merge Sort, 332
Quick Sort, 338
Radix Sort, 346
Comparing the Algorithms, 349
Chapter Summary, 349
Exercises, 350
Projects, 352
13. Sorted Lists, 355
Specifications for the ADT Sorted List, 356
A Linked Implementation, 360
An Implementation That Uses the ADT List, 368
Chapter Summary, 373
Exercises, 374
Projects, 375
14. Inheritance and Lists, 377
Using Inheritance to Implement a Sorted List, 378
Designing a Base Class, 380
Chapter Summary, 389
Programming Tips, 389
Exercises, 389
Projects, 390
15. Mutable, Immutable, and Cloneable Objects, 391
Mutable and Immutable Objects, 392
Cloneable Objects, 398
Chapter Summary, 413
Programming Tips, 414
Exercises, 414
16. Searching, 417
The Problem, 418
Searching an Unsorted Array, 419
Searching a Sorted Array, 422
Searching an Unsorted Chain, 429
Searching a Sorted Chain, 432
Choosing a Search Method, 433
Chapter Summary, 434
Programming Tip, 434
Exercises, 434
Projects, 436
17. Dictionaries, 439
Specifications for the ADT Dictionary, 440
Using the ADT Dictionary, 446
Java Class Library: The Interface Map, 458
Exercises, 460
Projects, 461
18. Dictionary Implementations, 463
Array-Based Implementations, 464
Vector-Based Implementations, 474
Programming Tip, 484
Exercises, 484
Projects, 485
19. Introducing Hashing, 487
What Is Hashing?, 488
Hash Functions, 491
Resolving Collisions, 495
Chapter Summary, 507
Exercises, 508
Projects, 509
20. Hashing as a Dictionary Implementation, 511
The Efficiency of Hashing, 512
Rehashing, 516
Comparing Schemes for Collision Resolution, 517
A Dictionary Implementation That Uses Hashing, 518
Chapter Summary, 529
Exercises, 529
Projects, 530
21. Stacks, 533
Specifications of the ADT Stack, 534
Using a Stack to Process Algebraic Expressions, 538
Using a Stack Instead of Recursion, 557
Programming Tip, 560
Exercises, 560
Projects, 562
22. Stack Implementations, 565
A Linked Implementation, 566
An Array-Based Implementation, 569
A Vector-Based Implementation, 573
Exercises, 576
Projects, 577
23. Queues, Deques, and Priority Queues, 579
Specifications of the ADT Queue, 580
Using a Queue to Simulate a Waiting Line, 584
Using a Queue to Compute the Capital Gain in a Sale of Stock, 590
Java Class Library: The Interface Queue, 593
Specifications of the ADT Deque, 594
Using a Deque to Compute the Capital Gain in a Sale of Stock, 596
Using a Priority Queue to Track Your Assignments, 598
Chapter Summary, 601
Programming Tip, 601
Exercises, 601
Projects, 603
24. Queue, Deque, and Priority Queue Implementations, 605
A Linked Implementation of a Queue, 606
An Array-Based Implementation of a Queue, 610
A Vector-Based Implementation of a Queue, 619
Circular Linked Implementations of a Queue, 620
Java Class Library: The Class AbstractQueue, 628
A Doubly Linked Implementation of a Deque, 628
Possible Implementations of a Priority Queue, 632
Java Class Library: The Class PriorityQueue, 633
Chapter Summary, 634
Programming Tip, 635
Exercises, 635
Projects, 636
25. Trees, 639
Tree Concepts, 640
Traversals of a Tree, 647
Java Interfaces for Trees, 650
Chapter Summary, 666
Exercises, 667
Projects, 669
26. Tree Implementations, 671
The Nodes in a Binary Tree, 672
An Implementation of an Expression Tree, 687
General Trees, 689
Chapter Summary, 691
Programming Tips, 692
Exercises, 692
Projects, 694
27. A Binary Search Tree Implementation, 697
Getting Started, 698
Traversing, 705
Adding an Entry, 705
Removing an Entry, 712
The Efficiency of Operations, 725
An Implementation of the ADT Dictionary, 728
Exercises, 732
Projects, 734
28. A Heap Implementation, 737
Reprise: The ADT Heap, 738
Using an Array to Represent a Heap, 738
Adding an Entry, 741
Heap Sort, 750
Chapter Summary, 753
Exercises, 754
Projects, 755
29. Balanced Search Trees, 757
AVL Trees, 758
2-4 Trees, 775
Red-Black Trees, 779
B-Trees, 787
Chapter Summary, 788
Exercises, 788
Projects, 790
30. Graphs, 791
Some Examples and Terminology, 792
Traversals, 797
Topological Order, 801
Paths, 803
Chapter Summary, 815
Exercises, 816
Projects, 819
31. Graph Implementations, 821
An Overview of Two Implementations, 822
Vertices and Edges, 824
An Implementation of the ADT Graph, 832
Exercises, 839
Projects, 841
A. Java Essentials, 843
Introduction, 844
Java Basics, 847
Simple Input and Output Using the Keyboard and Screen, 858
The if-else Statement, 863
The switch Statement, 870
Enumerations, 872
Scope, 874
Loops, 874
The Class String, 880
The Class StringBuilder, 885
Using Scanner to Extract Pieces of a String, 887
Arrays, 890
Wrapper Classes, 897
Programming Tips, 901
B. Exception Handling, 903
Basic Exception Handling, 903
Exception Classes in the Java Class Library, 906
Defining Your Own Exception Classes, 907
Multiple catch Blocks, 909
Methods That Throw but Do Not Catch Exceptions, 911
Exceptions That Do Not Need to Be Caught, 912
Programming Tips, 913
C. File Input and Output, 915
Overview, 916
Writing to a Text File Using PrintWriter, 918
I/O with Binary Files, 926
The Class File, 932
Object Serialization, 933
Programming Tips, 936
D. Documentation and Programming Style, 937
Naming Variables and Classes, 938
Indenting, 938
Comments, 939
E. Answers to Self-Test Questions, 943
Chapter 1, 943
Chapter 2, 944
Chapter 3, 945
Chapter 4, 947
Chapter 5, 948
Chapter 6, 949
Chapter 7, 950
Chapter 8, 951
Chapter 9, 952
Chapter 10, 953
Chapter 11, 955
Chapter 12, 956
Chapter 13, 958
Chapter 14, 959
Chapter 15, 959
Chapter 16, 960
Chapter 17, 961
Chapter 18, 963
Chapter 19, 964
Chapter 20, 964
Chapter 21, 965
Chapter 22, 966
Chapter 23, 967
Chapter 24, 967
Chapter 25, 968
Chapter 26, 970
Chapter 27, 971
Chapter 28, 974
Chapter 29, 977
Chapter 30, 980
Chapter 31, 981
Inside Back Cover, InsideBackCover
Reserved Words, InsideBackCover
Primitive Data Types, InsideBackCover
Operator Precedence, InsideBackCover
Unicode Character Codes, InsideBackCover
Index, I-1-1

Search Results

« Back to eTextbook


PAGE	Description

175	...