# Data Structures and Abstractions with Java

**ISBN 13:**## 9780136100911

**ISBN 10:**## 0136100910

**Edition:**3rd**Format:**Hardcover**Copyright:**09/13/2011**Publisher:**Pearson- Newer Edition

Note: Not guaranteed to come with supplemental materials (access cards, study guides, lab manuals, CDs, etc.)

Extend Your Rental at Any Time

Need to keep your rental past your due date? At any time before your due date you can extend or purchase your rental through your account.

Sorry, this item is currently unavailable.

### Summary

Data Structures and Abstractions with Java, 3e,is ideal for one- or two-semester courses in data structures (CS-2) in the departments of Computer Science, Computer Engineering, Business, and Management Information Systems. This is the most student-friendly data structures text available that introduces ADTs in individual, brief chapters - each with pedagogical tools to help students master each concept.¿Using the latest features of Java, this unique object-oriented presentation makes a clear distinction between specification and implementation to simplify learning, while providing maximum classroom flexibility. Author Frank Carrano's Making it Real bloghttp://frank-m-carrano.com/blog/extends his textbooks and lectures to a lively discussion with instructors and students about teaching and learning computer science. Follow Frank on Twitter:http://twitter.com/Frank_M_Carrano Find him on Facebook:https://www.facebook.com/makingitreal

### Author Biography

Read more**Frank M. Carrano**is a professor emeritus of computer science at the University of Rhode Island. He received the Ph.D. degree in computer science from Syracuse University in 1969. His interests include data structures, computer science education, social issues in computing, and numerical computation. Professor Carrano is particularly interested in the design and delivery of undergraduate courses in computer science. He has authored several well-known computer science textbooks for undergraduates.

Visit

**Frank Carrano's Making it Real**blog -- a discussion with instructors and students about teaching and learning computer science.

http://frank-m-carrano.com/blog/

Follow Frank on Twitter: http://twitter.com/Frank_M_Carrano

### Table of Contents

Read more Introduction 1

The Bag 6

A Bag’s Behaviors 6

Specifying a Bag 7

An Interface 13

Using the ADT Bag 15

Using an ADT Is Like Using a Vending Machine 20

Java Class Library: The Interface Set 21

Using a Fixed-Size Array to Implement the ADT Bag 28

An Analogy 28

A Group of Core Methods 29

Implementing the Core Methods 30

Testing the Core Methods 37

Implementing More Methods 40

Methods That Remove Entries 42

Using Array Resizing to Implement the ADT Bag 50

Resizing an Array 50

A New Implementation of a Bag 53

The Pros and Cons of Using an Array to Implement the ADT Bag 55

Linked Data 62

Forming a Chain by Adding to Its Beginning 63

A Linked Implementation of the ADT Bag 65

The Private Class Node 65

An Outline of the Class LinkedBag 66

Defining Some Core Methods 67

Testing the Core Methods 71

The Method getFrequencyOf 72

The Method contains 73

Removing an Item from a Linked Chain 74

The Methods remove and clear 75

A Class Node That Has Set and Get Methods 78

The Pros and Cons of Using a Chain to Implement the ADT Bag 81

Motivation 88

Measuring an Algorithm’s Efficiency 89

Counting Basic Operations 91

Best, Worst, and Average Cases 93

Big Oh Notation 94

The Complexities of Program Constructs 97

Picturing Efficiency 98

The Efficiency of Implementations of the ADT Bag 102

An Array-Based Implementation 102

A Linked Implementation 103

Comparing the Implementations 104

Specifications of the ADT Stack 114

Using a Stack to Process Algebraic Expressions 118

A Problem Solved: Checking for Balanced Delimiters in an

Infix Algebraic Expression 119

A Problem Solved: Transforming an Infix Expression

to a Postfix Expression 123

A Problem Solved: Evaluating Postfix Expressions 128

A Problem Solved: Evaluating Infix Expressions 130

The Program Stack 132

Java Class Library: The Class Stack 133

A Linked Implementation 141

An Array-Based Implementation 145

A Vector-Based Implementation 149

Java Class Library: The Class Vector 150

Using a Vector to Implement the ADT Stack 150

What Is Recursion? 158

Tracing a Recursive Method 162

Recursive Methods That Return a Value 166

Recursively Processing an Array 168

Recursively Processing a Linked Chain 171

The Time Efficiency of Recursive Methods 172

The Time Efficiency of countDown 172

The Time Efficiency of Computing xn 174

A Simple Solution to a Difficult Problem 175

A Poor Solution to a Simple Problem 180

Tail Recursion 182

Indirect Recursion 184

Using a Stack Instead of Recursion 185

Organizing Java Methods That Sort an Array 196

Selection Sort 198

Iterative Selection Sort 199

Recursive Selection Sort 201

The Efficiency of Selection Sort 202

Insertion Sort 203

Iterative Insertion Sort 204

Recursive Insertion Sort 206

The Efficiency of Insertion Sort 208

Insertion Sort of a Chain of Linked Nodes 208

Shell Sort 211

The Java Code 213

The Efficiency of Shell Sort 214

Comparing the Algorithms 214

Merge Sort 222

Merging Arrays 222

Recursive Merge Sort 223

The Efficiency of Merge Sort 225

Iterative Merge Sort 227

Merge Sort in the Java Class Library 227

Quick Sort 228

The Efficiency of Quick Sort 228

Creating the Partition 229

Java Code for Quick Sort 232

Quick Sort in the Java Class Library 234

Radix Sort 235

Pseudocode for Radix Sort 236

The Efficiency of Radix Sort 237

Comparing the Algorithms 237

The ADT Queue 246

A Problem Solved: Simulating a Waiting Line 250

A Problem Solved: Computing the Capital Gain in a Sale of Stock 256

Java Class Library: The Interface Queue 259

The ADT Deque 260

A Problem Solved: Computing the Capital Gain in a Sale of Stock 262

Java Class Library: The Interface Deque 263

Java Class Library: The Class ArrayDeque 264

The ADT Priority Queue 265

A Problem Solved: Tracking Your Assignments 266

Java Class Library: The Class PriorityQueue 268

A Linked Implementation of a Queue 274

An Array-Based Implementation of a Queue 278

A Circular Array 278

A Circular Array with One Unused Location 281

A Vector-Based Implementation of a Queue 286

Circular Linked Implementations of a Queue 288

A Two-Part Circular Linked Chain 289

Java Class Library: The Class AbstractQueue 294

A Doubly Linked Implementation of a Deque 295

Possible Implementations of a Priority Queue 299

Specifications for the ADT List 306

Using the ADT List 312

Java Class Library: The Interface List 316

Java Class Library: The Class ArrayList 316

Using an Array to Implement the ADT List 322

An Analogy 322

The Java Implementation 324

The Efficiency of Using an Array to Implement the ADT List 331

Using a Vector to Implement the ADT List 332

Operations on a Chain of Linked Nodes 340

Adding a Node at Various Positions 340

Removing a Node from Various Positions 344

The Private Method getNodeAt 345

Beginning the Implementation 346

The Data Fields and Constructor 347

Adding to the End of the List 348

Adding at a Given Position Within the List 349

The Methods isEmpty and toArray 350

Testing the Core Methods 353

Continuing the Implementation 354

A Refined Implementation 356

The Tail Reference 357

The Efficiency of Using a Chain to Implement the ADT List 360

Java Class Library: The Class LinkedList 362

What Is an Iterator? 370

The Interface Iterator 371

Using the Interface Iterator 372

A Separate Class Iterator 377

An Inner Class Iterator 381

A Linked Implementation 381

An Array-Based Implementation 385

Why Are Iterator Methods in Their Own Class? 388

The Interface ListIterator 390

Using the Interface ListIterator 393

An Array-Based Implementation of the Interface ListIterator 395

The Inner Class 397

Java Class Library: The Interface Iterable 402

Iterable and for-each loops 403

The Interface List Revisited 403

Specifications for the ADT Sorted List 412

Using the ADT Sorted List 415

A Linked Implementation 416

The Method add 417

The Efficiency of the Linked Implementation 424

An Implementation That Uses the ADT List 424

Efficiency Issues 427

Using Inheritance to Implement a Sorted List 434

Designing a Base Class 436

Creating an Abstract Base Class 441

An Efficient Implementation of a Sorted List 443

The Method add 443

The Problem 448

Searching an Unsorted Array 448

An Iterative Sequential Search of an Unsorted Array 449

A Recursive Sequential Search of an Unsorted Array 450

The Efficiency of a Sequential Search of an Array 452

Searching a Sorted Array 452

A Sequential Search of a Sorted Array 452

A Binary Search of a Sorted Array 453

Java Class Library: The Method binarySearch 458

The Efficiency of a Binary Search of an Array 458

Searching an Unsorted Chain 460

An Iterative Sequential Search of an Unsorted Chain 460

A Recursive Sequential Search of an Unsorted Chain 461

The Efficiency of a Sequential Search of a Chain 462

Searching a Sorted Chain 462

A Sequential Search of a Sorted Chain 462

A Binary Search of a Sorted Chain 462

Choosing a Search Method 463

Specifications for the ADT Dictionary 472

A Java Interface 476

Iterators 477

Using the ADT Dictionary 478

A Problem Solved: A Directory of Telephone Numbers 479

A Problem Solved: The Frequency of Words 484

A Problem Solved: A Concordance of Words 488

Java Class Library: The Interface Map 490

Array-Based Implementations 498

An Unsorted Array-Based Dictionary 498

A Sorted Array-Based Dictionary 503

Vector-Based Implementations 508

Linked Implementations 512

An Unsorted Linked Dictionary 514

A Sorted Linked Dictionary 514

What Is Hashing? 524

Hash Functions 527

Computing Hash Codes 527

Compressing a Hash Code into an Index for the Hash Table 530

Resolving Collisions 531

Open Addressing with Linear Probing 531

Open Addressing with Quadratic Probing 537

Open Addressing with Double Hashing 537

A Potential Problem with Open Addressing 539

Separate Chaining 539

The Efficiency of Hashing 548

The Load Factor 548

The Cost of Open Addressing 549

The Cost of Separate Chaining 551

Rehashing 552

Comparing Schemes for Collision Resolution 553

A Dictionary Implementation That Uses Hashing 554

Entries in the Hash Table 554

Data Fields and Constructors 555

The Methods getValue, remove, and add 557

Iterators 562

Java Class Library: The Class HashMap 564

Java Class Library: The Class HashSet 564

Tree Concepts 570

Hierarchical Organizations 570

Tree Terminology 572

Traversals of a Tree 576

Traversals of a Binary Tree 576

Traversals of a General Tree 579

Java Interfaces for Trees 579

Interfaces for All Trees 580

An Interface for Binary Trees 580

Examples of Binary Trees 582

Expression Trees 582

Decision Trees 584

Binary Search Trees 588

Heaps 590

Examples of General Trees 593

Parse Trees 593

Game Trees 593

The Nodes in a Binary Tree 604

An Interface for a Node 605

An Implementation of BinaryNode 606

An Implementation of the ADT Binary Tree 607

Creating a Basic Binary Tree 608

The Method privateSetTree 609

Accessor and Mutator Methods 612

Computing the Height and Counting Nodes 613

Traversals 614

An Implementation of an Expression Tree 619

General Trees 621

A Node for a General Tree 621

Using a Binary Tree to Represent a General Tree 622

Getting Started 630

An Interface for the Binary Search Tree 631

Duplicate Entries 633

Beginning the Class Definition 634

Searching and Retrieving 635

Traversing 637

Adding an Entry 637

A Recursive Implementation 638

An Iterative Implementation 642

Removing an Entry 643

Removing an Entry Whose Node Is a Leaf 644

Removing an Entry Whose Node Has One Child 644

Removing an Entry Whose Node Has Two Children 645

Removing an Entry in the Root 648

A Recursive Implementation 649

An Iterative Implementation 652

The Efficiency of Operations 656

The Importance of Balance 657

The Order in Which Nodes Are Added 658

An Implementation of the ADT Dictionary 659

Reprise: The ADT Heap 674

Using an Array to Represent a Heap 674

Adding an Entry 677

Removing the Root 680

Creating a Heap 683

Heap Sort 686

AVL Trees 696

Single Rotations 696

Double Rotations 699

Implementation Details 703

2-3 Trees 707

Searching a 2-3 Tree 708

Adding Entries to a 2-3 Tree 709

Splitting Nodes During Addition 711

2-4 Trees 712

Adding Entries to a 2-4 Tree 713

Comparing AVL, 2-3, and 2-4 Trees 715

Red-Black Trees 716

Properties of a Red-Black Tree 717

Adding Entries to a Red-Black Tree 718

Java Class Library: The Class TreeMap 724

B-Trees 724

Some Examples and Terminology 732

Road Maps 732

Airline Routes 735

Mazes 736

Course Prerequisites 736

Trees 737

Traversals 737

Breadth-First Traversal 738

Depth-First Traversal 740

Topological Order 741

Paths 744

Finding a Path 744

The Shortest Path in an Unweighted Graph 744

The Shortest Path in a Weighted Graph 747

Java Interfaces for the ADT Graph 751

An Overview of Two Implementations 762

The Adjacency Matrix 762

The Adjacency List 763

Vertices and Edges 764

Specifying the Class Vertex 765

The Inner Class Edge 767

Implementing the Class Vertex 768

An Implementation of the ADT Graph 772

Basic Operations 772

Graph Algorithms 775

Mutable and Immutable Objects 30-2

Creating a Read-Only Class 30-4

Companion Classes 30-6

Cloneable Objects 30-8

Cloning an Array 30-14

Cloning a Chain 30-16

A Sorted List of Clones 30-19

Introduction A-2

Applications and Applets A-2

Objects and Classes A-3

A First Java Application Program A-3

Java Basics A-5

Identifiers A-5

Reserved Words A-6

Variables A-6

Primitive Types A-7

Constants A-7

Assignment Statements A-8

Assignment Compatibilities A-9

Type Casting A-9

Arithmetic Operators and Expressions A-10

Parentheses and Precedence Rules A-11

Increment and Decrement Operators A-12

Special Assignment Operators A-13

Named Constants A-14

The Class Math A-15

Simple Input and Output Using the Keyboard and Screen A-15

Screen Output A-15

Keyboard Input Using the Class Scanner A-17

The if-else Statement A-19

Boolean Expressions A-20

Nested Statements A-23

Multiway if-else Statements A-24

The Conditional Operator (Optional) A-25

The switch Statement A-26

Enumerations A-28

Scope A-30

Loops A-30

The while Statement A-31

The for Statement A-32

The do-while Statement A-34

Additional Loop Information A-35

The Class String A-36

Characters Within Strings A-36

Concatenation of Strings A-37

String Methods A-38

The Class StringBuilder A-40

Using Scanner to Extract Pieces of a String A-42

Arrays A-44

Array Parameters and Returned Values A-46

Initializing Arrays A-47

Array Index Out of Bounds A-47

Use of = and == with Arrays A-47

Arrays and the For-Each Loop A-48

Multidimensional Arrays A-49

Wrapper Classes A-51

Objects and Classes B-1

Using the Methods in a Java Class B-3

References and Aliases B-4

Defining a Java Class B-5

Method Definitions B-7

Arguments and Parameters B-9

Passing Arguments B-9

A Definition of the Class Name B-13

Constructors B-15

The Method toString B-17

Methods That Call Other Methods B-17

Methods That Return an Instance of Their Class B-19

Static Fields and Methods B-19

Overloading Methods B-21

Enumeration as a Class B-22

Packages B-25

The Java Class Library B-25

Generic Data Types B-26

Composition C-2

Adapters C-4

Inheritance C-5

Invoking Constructors from Within Constructors C-9

Private Fields and Methods of the Superclass C-10

Protected Access C-11

Overriding and Overloading Methods C-11

Multiple Inheritance C-16

Type Compatibility and Superclasses C-16

The Class Object C-18

Abstract Classes and Methods C-19

Polymorphism C-21

Encapsulation D-2

Specifying Methods D-4

Comments D-4

Preconditions and Postconditions D-5

Assertions D-6

Java Interfaces D-7

Writing an Interface D-8

Implementing an Interface D-10

An Interface as a Data Type D-11

Generic Types Within an Interface D-12

Extending an Interface D-14

Interfaces Versus Abstract Classes D-15

Named Constants Within an Interface D-17

Choosing Classes D-18

Identifying Classes D-20

CRC Cards D-20

The Unified Modeling Language D-21

Reusing Classes D-23

The Basics E-2

Handling an Exception E-4

Postpone Handling: The throws Clause E-4

Handle It Now: The try-catch Blocks E-5

Multiple catch Blocks E-6

Throwing an Exception E-8

Programmer-Defined Exception Classes E-9

Inheritance and Exceptions E-14

The finally Block E-15

Preliminaries F-2

Why Files? F-2

Streams F-2

The Kinds of Files F-3

File Names F-3

Text Files F-3

Creating a Text File F-3

Reading a Text File F-8

Changing Existing Data in a Text File F-12

Defining a Method to Open a Stream F-13

Binary Files F-13

Creating a Binary File of Primitive Data F-14

Reading a Binary File of Primitive Data F-18

Strings in a Binary File F-20

Object Serialization F-23

Naming Variables and Classes G-1

Indenting G-2

Comments G-2

Single-Line Comments G-3

Comment Blocks G-3

When to Write Comments G-3

Java Documentation Comments G-3

Running javadoc G-5

Glossary Online

Index I-1

**Chapter 1**Bags 5The Bag 6

A Bag’s Behaviors 6

Specifying a Bag 7

An Interface 13

Using the ADT Bag 15

Using an ADT Is Like Using a Vending Machine 20

Java Class Library: The Interface Set 21

**Chapter 2**Bag Implementations That Use Arrays 27Using a Fixed-Size Array to Implement the ADT Bag 28

An Analogy 28

A Group of Core Methods 29

Implementing the Core Methods 30

Testing the Core Methods 37

Implementing More Methods 40

Methods That Remove Entries 42

Using Array Resizing to Implement the ADT Bag 50

Resizing an Array 50

A New Implementation of a Bag 53

The Pros and Cons of Using an Array to Implement the ADT Bag 55

**Chapter 3**A Bag Implementation That Links Data 61Linked Data 62

Forming a Chain by Adding to Its Beginning 63

A Linked Implementation of the ADT Bag 65

The Private Class Node 65

An Outline of the Class LinkedBag 66

Defining Some Core Methods 67

Testing the Core Methods 71

The Method getFrequencyOf 72

The Method contains 73

Removing an Item from a Linked Chain 74

The Methods remove and clear 75

A Class Node That Has Set and Get Methods 78

The Pros and Cons of Using a Chain to Implement the ADT Bag 81

**Chapter 4**The Efficiency of Algorithms 87Motivation 88

Measuring an Algorithm’s Efficiency 89

Counting Basic Operations 91

Best, Worst, and Average Cases 93

Big Oh Notation 94

The Complexities of Program Constructs 97

Picturing Efficiency 98

The Efficiency of Implementations of the ADT Bag 102

An Array-Based Implementation 102

A Linked Implementation 103

Comparing the Implementations 104

**Chapter 5**Stacks 113Specifications of the ADT Stack 114

Using a Stack to Process Algebraic Expressions 118

A Problem Solved: Checking for Balanced Delimiters in an

Infix Algebraic Expression 119

A Problem Solved: Transforming an Infix Expression

to a Postfix Expression 123

A Problem Solved: Evaluating Postfix Expressions 128

A Problem Solved: Evaluating Infix Expressions 130

The Program Stack 132

Java Class Library: The Class Stack 133

**Chapter 6**Stack Implementations 141A Linked Implementation 141

An Array-Based Implementation 145

A Vector-Based Implementation 149

Java Class Library: The Class Vector 150

Using a Vector to Implement the ADT Stack 150

**Chapter 7**Recursion 157What Is Recursion? 158

Tracing a Recursive Method 162

Recursive Methods That Return a Value 166

Recursively Processing an Array 168

Recursively Processing a Linked Chain 171

The Time Efficiency of Recursive Methods 172

The Time Efficiency of countDown 172

The Time Efficiency of Computing xn 174

A Simple Solution to a Difficult Problem 175

A Poor Solution to a Simple Problem 180

Tail Recursion 182

Indirect Recursion 184

Using a Stack Instead of Recursion 185

**Chapter 8**An Introduction to Sorting 195Organizing Java Methods That Sort an Array 196

Selection Sort 198

Iterative Selection Sort 199

Recursive Selection Sort 201

The Efficiency of Selection Sort 202

Insertion Sort 203

Iterative Insertion Sort 204

Recursive Insertion Sort 206

The Efficiency of Insertion Sort 208

Insertion Sort of a Chain of Linked Nodes 208

Shell Sort 211

The Java Code 213

The Efficiency of Shell Sort 214

Comparing the Algorithms 214

**Chapter 9**Faster Sorting Methods 221Merge Sort 222

Merging Arrays 222

Recursive Merge Sort 223

The Efficiency of Merge Sort 225

Iterative Merge Sort 227

Merge Sort in the Java Class Library 227

Quick Sort 228

The Efficiency of Quick Sort 228

Creating the Partition 229

Java Code for Quick Sort 232

Quick Sort in the Java Class Library 234

Radix Sort 235

Pseudocode for Radix Sort 236

The Efficiency of Radix Sort 237

Comparing the Algorithms 237

**Chapter 10**Queues, Deques, and Priority Queues 245The ADT Queue 246

A Problem Solved: Simulating a Waiting Line 250

A Problem Solved: Computing the Capital Gain in a Sale of Stock 256

Java Class Library: The Interface Queue 259

The ADT Deque 260

A Problem Solved: Computing the Capital Gain in a Sale of Stock 262

Java Class Library: The Interface Deque 263

Java Class Library: The Class ArrayDeque 264

The ADT Priority Queue 265

A Problem Solved: Tracking Your Assignments 266

Java Class Library: The Class PriorityQueue 268

**Chapter 11**Queue, Deque, and Priority Queue Implementations 273A Linked Implementation of a Queue 274

An Array-Based Implementation of a Queue 278

A Circular Array 278

A Circular Array with One Unused Location 281

A Vector-Based Implementation of a Queue 286

Circular Linked Implementations of a Queue 288

A Two-Part Circular Linked Chain 289

Java Class Library: The Class AbstractQueue 294

A Doubly Linked Implementation of a Deque 295

Possible Implementations of a Priority Queue 299

**Lists 305**

Chapter 12Chapter 12

Specifications for the ADT List 306

Using the ADT List 312

Java Class Library: The Interface List 316

Java Class Library: The Class ArrayList 316

**Chapter 13**List Implementations That Use Arrays 321Using an Array to Implement the ADT List 322

An Analogy 322

The Java Implementation 324

The Efficiency of Using an Array to Implement the ADT List 331

Using a Vector to Implement the ADT List 332

**Chapter 14**A List Implementation That Links Data 339Operations on a Chain of Linked Nodes 340

Adding a Node at Various Positions 340

Removing a Node from Various Positions 344

The Private Method getNodeAt 345

Beginning the Implementation 346

The Data Fields and Constructor 347

Adding to the End of the List 348

Adding at a Given Position Within the List 349

The Methods isEmpty and toArray 350

Testing the Core Methods 353

Continuing the Implementation 354

A Refined Implementation 356

The Tail Reference 357

The Efficiency of Using a Chain to Implement the ADT List 360

Java Class Library: The Class LinkedList 362

**Chapter 15**Iterators 369What Is an Iterator? 370

The Interface Iterator 371

Using the Interface Iterator 372

A Separate Class Iterator 377

An Inner Class Iterator 381

A Linked Implementation 381

An Array-Based Implementation 385

Why Are Iterator Methods in Their Own Class? 388

The Interface ListIterator 390

Using the Interface ListIterator 393

An Array-Based Implementation of the Interface ListIterator 395

The Inner Class 397

Java Class Library: The Interface Iterable 402

Iterable and for-each loops 403

The Interface List Revisited 403

**Chapter 16**Sorted Lists 411Specifications for the ADT Sorted List 412

Using the ADT Sorted List 415

A Linked Implementation 416

The Method add 417

The Efficiency of the Linked Implementation 424

An Implementation That Uses the ADT List 424

Efficiency Issues 427

**Chapter 17**Inheritance and Lists 433Using Inheritance to Implement a Sorted List 434

Designing a Base Class 436

Creating an Abstract Base Class 441

An Efficient Implementation of a Sorted List 443

The Method add 443

**Chapter 18**Searching 447The Problem 448

Searching an Unsorted Array 448

An Iterative Sequential Search of an Unsorted Array 449

A Recursive Sequential Search of an Unsorted Array 450

The Efficiency of a Sequential Search of an Array 452

Searching a Sorted Array 452

A Sequential Search of a Sorted Array 452

A Binary Search of a Sorted Array 453

Java Class Library: The Method binarySearch 458

The Efficiency of a Binary Search of an Array 458

Searching an Unsorted Chain 460

An Iterative Sequential Search of an Unsorted Chain 460

A Recursive Sequential Search of an Unsorted Chain 461

The Efficiency of a Sequential Search of a Chain 462

Searching a Sorted Chain 462

A Sequential Search of a Sorted Chain 462

A Binary Search of a Sorted Chain 462

Choosing a Search Method 463

**Chapter 19**Dictionaries 471Specifications for the ADT Dictionary 472

A Java Interface 476

Iterators 477

Using the ADT Dictionary 478

A Problem Solved: A Directory of Telephone Numbers 479

A Problem Solved: The Frequency of Words 484

A Problem Solved: A Concordance of Words 488

Java Class Library: The Interface Map 490

**Chapter 20**Dictionary Implementations 497Array-Based Implementations 498

An Unsorted Array-Based Dictionary 498

A Sorted Array-Based Dictionary 503

Vector-Based Implementations 508

Linked Implementations 512

An Unsorted Linked Dictionary 514

A Sorted Linked Dictionary 514

**Chapter 21**Introducing Hashing 523What Is Hashing? 524

Hash Functions 527

Computing Hash Codes 527

Compressing a Hash Code into an Index for the Hash Table 530

Resolving Collisions 531

Open Addressing with Linear Probing 531

Open Addressing with Quadratic Probing 537

Open Addressing with Double Hashing 537

A Potential Problem with Open Addressing 539

Separate Chaining 539

**Chapter 22**Hashing as a Dictionary Implementation 547The Efficiency of Hashing 548

The Load Factor 548

The Cost of Open Addressing 549

The Cost of Separate Chaining 551

Rehashing 552

Comparing Schemes for Collision Resolution 553

A Dictionary Implementation That Uses Hashing 554

Entries in the Hash Table 554

Data Fields and Constructors 555

The Methods getValue, remove, and add 557

Iterators 562

Java Class Library: The Class HashMap 564

Java Class Library: The Class HashSet 564

**Chapter 23**Trees 569Tree Concepts 570

Hierarchical Organizations 570

Tree Terminology 572

Traversals of a Tree 576

Traversals of a Binary Tree 576

Traversals of a General Tree 579

Java Interfaces for Trees 579

Interfaces for All Trees 580

An Interface for Binary Trees 580

Examples of Binary Trees 582

Expression Trees 582

Decision Trees 584

Binary Search Trees 588

Heaps 590

Examples of General Trees 593

Parse Trees 593

Game Trees 593

**Chapter 24**Tree Implementations 603The Nodes in a Binary Tree 604

An Interface for a Node 605

An Implementation of BinaryNode 606

An Implementation of the ADT Binary Tree 607

Creating a Basic Binary Tree 608

The Method privateSetTree 609

Accessor and Mutator Methods 612

Computing the Height and Counting Nodes 613

Traversals 614

An Implementation of an Expression Tree 619

General Trees 621

A Node for a General Tree 621

Using a Binary Tree to Represent a General Tree 622

**Chapter 25**A Binary Search Tree Implementation 629Getting Started 630

An Interface for the Binary Search Tree 631

Duplicate Entries 633

Beginning the Class Definition 634

Searching and Retrieving 635

Traversing 637

Adding an Entry 637

A Recursive Implementation 638

An Iterative Implementation 642

Removing an Entry 643

Removing an Entry Whose Node Is a Leaf 644

Removing an Entry Whose Node Has One Child 644

Removing an Entry Whose Node Has Two Children 645

Removing an Entry in the Root 648

A Recursive Implementation 649

An Iterative Implementation 652

The Efficiency of Operations 656

The Importance of Balance 657

The Order in Which Nodes Are Added 658

An Implementation of the ADT Dictionary 659

**Chapter 26**A Heap Implementation 673Reprise: The ADT Heap 674

Using an Array to Represent a Heap 674

Adding an Entry 677

Removing the Root 680

Creating a Heap 683

Heap Sort 686

**Chapter 27**Balanced Search Trees 695AVL Trees 696

Single Rotations 696

Double Rotations 699

Implementation Details 703

2-3 Trees 707

Searching a 2-3 Tree 708

Adding Entries to a 2-3 Tree 709

Splitting Nodes During Addition 711

2-4 Trees 712

Adding Entries to a 2-4 Tree 713

Comparing AVL, 2-3, and 2-4 Trees 715

Red-Black Trees 716

Properties of a Red-Black Tree 717

Adding Entries to a Red-Black Tree 718

Java Class Library: The Class TreeMap 724

B-Trees 724

**Chapter 28**Graphs 731Some Examples and Terminology 732

Road Maps 732

Airline Routes 735

Mazes 736

Course Prerequisites 736

Trees 737

Traversals 737

Breadth-First Traversal 738

Depth-First Traversal 740

Topological Order 741

Paths 744

Finding a Path 744

The Shortest Path in an Unweighted Graph 744

The Shortest Path in a Weighted Graph 747

Java Interfaces for the ADT Graph 751

**Chapter 29**Graph Implementations 761An Overview of Two Implementations 762

The Adjacency Matrix 762

The Adjacency List 763

Vertices and Edges 764

Specifying the Class Vertex 765

The Inner Class Edge 767

Implementing the Class Vertex 768

An Implementation of the ADT Graph 772

Basic Operations 772

Graph Algorithms 775

**Chapter 30**Mutable, Immutable, and Cloneable Objects OnlineMutable and Immutable Objects 30-2

Creating a Read-Only Class 30-4

Companion Classes 30-6

Cloneable Objects 30-8

Cloning an Array 30-14

Cloning a Chain 30-16

A Sorted List of Clones 30-19

**Appendices****A.**Java Essentials A-1Introduction A-2

Applications and Applets A-2

Objects and Classes A-3

A First Java Application Program A-3

Java Basics A-5

Identifiers A-5

Reserved Words A-6

Variables A-6

Primitive Types A-7

Constants A-7

Assignment Statements A-8

Assignment Compatibilities A-9

Type Casting A-9

Arithmetic Operators and Expressions A-10

Parentheses and Precedence Rules A-11

Increment and Decrement Operators A-12

Special Assignment Operators A-13

Named Constants A-14

The Class Math A-15

Simple Input and Output Using the Keyboard and Screen A-15

Screen Output A-15

Keyboard Input Using the Class Scanner A-17

The if-else Statement A-19

Boolean Expressions A-20

Nested Statements A-23

Multiway if-else Statements A-24

The Conditional Operator (Optional) A-25

The switch Statement A-26

Enumerations A-28

Scope A-30

Loops A-30

The while Statement A-31

The for Statement A-32

The do-while Statement A-34

Additional Loop Information A-35

The Class String A-36

Characters Within Strings A-36

Concatenation of Strings A-37

String Methods A-38

The Class StringBuilder A-40

Using Scanner to Extract Pieces of a String A-42

Arrays A-44

Array Parameters and Returned Values A-46

Initializing Arrays A-47

Array Index Out of Bounds A-47

Use of = and == with Arrays A-47

Arrays and the For-Each Loop A-48

Multidimensional Arrays A-49

Wrapper Classes A-51

**B.**Java Classes B-1Objects and Classes B-1

Using the Methods in a Java Class B-3

References and Aliases B-4

Defining a Java Class B-5

Method Definitions B-7

Arguments and Parameters B-9

Passing Arguments B-9

A Definition of the Class Name B-13

Constructors B-15

The Method toString B-17

Methods That Call Other Methods B-17

Methods That Return an Instance of Their Class B-19

Static Fields and Methods B-19

Overloading Methods B-21

Enumeration as a Class B-22

Packages B-25

The Java Class Library B-25

Generic Data Types B-26

**C.**Creating Classes from Other Classes C-1Composition C-2

Adapters C-4

Inheritance C-5

Invoking Constructors from Within Constructors C-9

Private Fields and Methods of the Superclass C-10

Protected Access C-11

Overriding and Overloading Methods C-11

Multiple Inheritance C-16

Type Compatibility and Superclasses C-16

The Class Object C-18

Abstract Classes and Methods C-19

Polymorphism C-21

**D.**Designing Classes D-1Encapsulation D-2

Specifying Methods D-4

Comments D-4

Preconditions and Postconditions D-5

Assertions D-6

Java Interfaces D-7

Writing an Interface D-8

Implementing an Interface D-10

An Interface as a Data Type D-11

Generic Types Within an Interface D-12

Extending an Interface D-14

Interfaces Versus Abstract Classes D-15

Named Constants Within an Interface D-17

Choosing Classes D-18

Identifying Classes D-20

CRC Cards D-20

The Unified Modeling Language D-21

Reusing Classes D-23

**E.**Handling Exceptions E-1The Basics E-2

Handling an Exception E-4

Postpone Handling: The throws Clause E-4

Handle It Now: The try-catch Blocks E-5

Multiple catch Blocks E-6

Throwing an Exception E-8

Programmer-Defined Exception Classes E-9

Inheritance and Exceptions E-14

The finally Block E-15

**F.**File Input and Output F-1Preliminaries F-2

Why Files? F-2

Streams F-2

The Kinds of Files F-3

File Names F-3

Text Files F-3

Creating a Text File F-3

Reading a Text File F-8

Changing Existing Data in a Text File F-12

Defining a Method to Open a Stream F-13

Binary Files F-13

Creating a Binary File of Primitive Data F-14

Reading a Binary File of Primitive Data F-18

Strings in a Binary File F-20

Object Serialization F-23

**G.**Documentation and Programming Style G-1Naming Variables and Classes G-1

Indenting G-2

Comments G-2

Single-Line Comments G-3

Comment Blocks G-3

When to Write Comments G-3

Java Documentation Comments G-3

Running javadoc G-5

Glossary Online

Index I-1

### Write a Review

Currently unavailable