# Data Structures: Abstraction and Design Using Java, 3rd Edition

# Data Structures: Abstraction and Design Using Java, 3rd Edition

ISBN: 978-1-119-18652-6

Dec 2015

684 pages

$47.50

## Description

TRY (FREE for 14 days), OR RENT this title:**, combines a strong emphasis on problem solving and software design with the study of data structures. The authors discuss applications of each data structure to motivate its study. After providing the specification (interface) and the implementation (a Java class), case studies that use the data structure to solve a significant problem are introduced.**

*www.wileystudentchoice.com*

Data Structures: Abstraction and Design Using Java, 3rd EditionData Structures: Abstraction and Design Using Java, 3rd Edition

## Related Resources

### Instructor

Request an Evaluation Copy for this title

View Instructor Companion Site

Contact your Rep for all inquiries

### Student

Preface iii

**Chapter 1 Object-Oriented Programming and Class Hierarchies 1**

1.1 ADTs, Interfaces, and the Java API 2

Interfaces 2

The implements Clause 5

Declaring a Variable of an Interface Type 6

Exercises for Section 1.1 6

1.2 Introduction to Object‐Oriented Programming (OOP) 7

A Superclass and Subclass Example 8

Use of this. 9

Initializing Data Fields in a Subclass 10

The No‐Parameter Constructor 11

Protected Visibility for Superclass Data Fields 11

*Is‐a* versus *Has‐a* Relationships 12

Exercises for Section 1.2 12

1.3 Method Overriding, Method Overloading, and Polymorphism 13

Method Overriding 13

Method Overloading 15

Polymorphism 17

Methods with Class Parameters 17

Exercises for Section 1.3 18

1.4 Abstract Classes 19

Referencing Actual Objects 21

Initializing Data Fields in an Abstract Class 21

Abstract Class Number and the Java Wrapper Classes 21

Summary of Features of Actual Classes, Abstract Classes, and Interfaces 22

Implementing Multiple Interfaces 23

Extending an Interface 23

Exercises for Section 1.4 23

1.5 Class Object and Casting 24

The Method toString 24

Operations Determined by Type of Reference Variable 25

Casting in a Class Hierarchy 26

Using instanceof to Guard a Casting Operation 27

The Class Class 29

Exercises for Section 1.5 29

1.6 A Java Inheritance Example—The Exception Class Hierarchy 29

Division by Zero 29

Array Index Out of Bounds 30

Null Pointer 31

The Exception Class Hierarchy 31

The Class Throwable 31

Checked and Unchecked Exceptions 32

Handling Exceptions to Recover from Errors 34

Using try‐catch to Recover from an Error 34

Throwing an Exception When Recovery Is Not Obvious 35

Exercises for Section 1.6 36

1.7 Packages and Visibility 36

Packages 36

The No‐Package‐Declared Environment 37

Package Visibility 38

Visibility Supports Encapsulation 38

Exercises for Section 1.7 39

1.8 A Shape Class Hierarchy 39

Case Study: Processing Geometric Figures 40

Exercises for Section 1.8 45

Java Constructs Introduced in This Chapter 46

Java API Classes Introduced in This Chapter 46

User‐Defined Interfaces and Classes in This Chapter 47

Quick‐Check Exercises 47

Review Questions 47

Programming Projects 48

Answers to Quick-Check Exercises 51

**Chapter 2 Lists and the Collections Framework 53**

2.1 Algorithm Efficiency and Big-O 54

Big-O Notation 56

Formal Definition of Big-O 57

Summary of Notation 60

Comparing Performance 60

Algorithms with Exponential and Factorial Growth Rates 62

Exercises for Section 2.1 62

2.2 The List Interface and ArrayList Class 63

The ArrayList Class 64

Generic Collections 66

Exercises for Section 2.2 68

2.3 Applications of ArrayList 68

A Phone Directory Application 69

Exercises for Section 2.3 69

2.4 Implementation of an ArrayList Class 70

The Constructor for Class KWArrayList 71

The add(E anEntry) Method 72

The add(int index, E anEntry) Method 73

The set and get Methods 73

The remove Method 74

The reallocate Method 74

Performance of the KWArrayList Algorithms 74

Exercises for Section 2.4 75

2.5 Single‐Linked Lists 75

A List Node 77

Connecting Nodes 78

A Single-Linked List Class 79

Inserting a Node in a List 79

Removing a Node 80

Completing the SingleLinkedList Class 81

The get and set Methods 82

The add Methods 82

Exercises for Section 2.5 83

2.6 Double‐Linked Lists and Circular Lists 84

The Node Class 85

Inserting into a Double‐Linked List 86

Removing from a Double‐Linked List 86

A Double‐Linked List Class 86

Circular Lists 87

Exercises for Section 2.6 88

2.7 The LinkedList Class and the Iterator, ListIterator, and Iterable Interfaces 89

The LinkedList Class 89

The Iterator 89

The Iterator Interface 90

The Enhanced for Loop 92

The ListIterator Interface 92

Comparison of Iterator and ListIterator 94

Conversion between a ListIterator and an Index 95

The Iterable Interface 95

Exercises for Section 2.7 95

2.8 Application of the LinkedList Class 96

Case Study: Maintaining an Ordered List 96

Testing Class OrderedList 101

Exercises for Section 2.8 103

2.9 Implementation of a Double‐Linked List Class 103

Implementing the KWLinkedList Methods 104

A Class that Implements the ListIterator Interface 104

The Constructor 105

The hasNext and next Methods 106

The hasPrevious and previous Methods 107

The add Method 107

Inner Classes: Static and Nonstatic 111

Exercises for Section 2.9 111

2.10 The Collections Framework Design 112

The Collection Interface 112

Common Features of Collections 113

The AbstractCollection, AbstractList, and AbstractSequentialList Classes 113

The List and RandomAccess Interfaces (Advanced) 114

Exercises for Section 2.10 114

Java API Interfaces and Classes Introduced in this Chapter 116

User‐Defined Interfaces and Classes in this Chapter 116

Quick‐Check Exercises 116

Review Questions 117

Programming Projects 117

Answers to Quick-Check Exercises 119

**Chapter 3 Testing and Debugging 121**

3.1 Types of Testing 122

Preparations for Testing 124

Testing Tips for Program Systems 124

Exercises for Section 3.1 125

3.2 Specifying the Tests 125

Testing Boundary Conditions 125

Exercises for Section 3.2 126

3.3 Stubs and Drivers 127

Stubs 127

Preconditions and Postconditions 127

Drivers 128

Exercises for Section 3.3 128

3.4 The JUnit Test Framework 128

Exercises for Section 3.4 132

3.5 Test‐Driven Development 132

Exercises for Section 3.5 136

3.6 Testing Interactive Programs in JUnit 137

ByteArrayInputStream 138

ByteArrayOutputStream 138

Exercises for Section 3.6 139

3.7 Debugging a Program 139

Using a Debugger 140

Exercises for Section 3.7 142

Java API Classes Introduced in This Chapter 144

User‐Defined Interfaces and Classes in This Chapter 144

Quick‐Check Exercises 144

Review Questions 144

Programming 144

Answers to Quick-Check Exercises 146

**Chapter 4 Stacks and Queues 147**

4.1 Stack Abstract Data Type 148

Specification of the Stack Abstract Data Type 148

Exercises for Section 4.1 150

4.2 Stack Applications 151

Case Study: Finding Palindromes 151

Exercises for Section 4.2 155

4.3 Implementing a Stack 155

Implementing a Stack with an ArrayList Component 155

Implementing a Stack as a Linked Data Structure 157

Comparison of Stack Implementations 158

Exercises for Section 4.3 159

4.4 Additional Stack Applications 159

Case Study: Evaluating Postfix Expressions 160

Case Study: Converting From Infix To Postfix 165

Case Study: Converting Expressions with Parentheses 173

Tying the Case Studies Together 176

Exercises for Section 4.4 176

4.5 Queue Abstract Data Type 177

A Print Queue 177

The Unsuitability of a “Print Stack” 178

A Queue of Customers 178

Using a Queue for Traversing a Multi‐Branch Data Structure 178

Specification for a Queue Interface 179

Class LinkedList Implements the Queue Interface 179

Exercises for Section 4.5 180

4.6 Queue Applications 181

Case Study: Maintaining a Queue 181

Exercises for Section 4.6 186

4.7 Implementing the Queue Interface 187

Using a Double‐Linked List to Implement the Queue Interface 187

Using a Single‐Linked List to Implement the Queue Interface 187

Using a Circular Array to Implement the Queue Interface 189

Exercises for Section 4.7 196

4.8 The Deque Interface 196

Classes that Implement Deque 198

Using a Deque as a Queue 198

Using a Deque as a Stack 198

Exercises for Section 4.8 199

Java API Classes Introduced in This Chapter 200

User‐Defined Interfaces and Classes in This Chapter 200

Quick‐Check Exercises 201

Review Questions 202

Programming Projects 203

Answers to Quick-Check Exercises 207

**Chapter 5 Recursion 211**

5.1 Recursive Thinking 212

Steps to Design a Recursive Algorithm 214

Proving that a Recursive Method Is Correct 216

Tracing a Recursive Method 216

The Run‐Time Stack and Activation Frames 217

Exercises for Section 5.1 218

5.2 Recursive Definitions of Mathematical Formulas 219

Tail Recursion versus Iteration 222

Efficiency of Recursion 223

Exercises for Section 5.2 225

5.3 Recursive Array Search 226

Design of a Recursive Linear Search Algorithm 226

Implementation of Linear Search 227

Design of a Binary Search Algorithm 228

Efficiency of Binary Search 229

The Comparable Interface 230

Implementation of Binary Search 230

Testing Binary Search 232

Method Arrays.binarySearch 233

Exercises for Section 5.3 233

5.4 Recursive Data Structures 233

Recursive Definition of a Linked List 234

Class LinkedListRec 234

Removing a List Node 236

Exercises for Section 5.4 237

5.5 Problem Solving with Recursion 238

Case Study: Towers of Hanoi 238

Case Study: Counting Cells in a Blob 243

Exercises for Section 5.5 247

5.6 Backtracking 247

Case Study: Finding a Path through a Maze 248

Exercises for Section 5.6 252

User‐Defined Classes in This Chapter 253

Quick‐Check Exercises 253

Review Questions 253

Programming Projects 254

Answers to Quick-Check Exercises 255

**Chapter 6 Trees 257**

6.1 Tree Terminology and Applications 258

Tree Terminology 258

Binary Trees 259

Some Types of Binary Trees 260

Full, Perfect, and Complete Binary Trees 263

General Trees 263

Exercises for Section 6.1 264

6.2 Tree Traversals 265

Visualizing Tree Traversals 266

Traversals of Binary Search Trees and Expression Trees 266

Exercises for Section 6.2 267

6.3 Implementing a BinaryTree Class 268

The Node Class 268

The BinaryTree Class 269

Exercises for Section 6.3 275

6.4 Java 8 Lambda Expressions and Functional Interfaces 276

Functional Interfaces 277

Passing a Lambda Expression as an Argument 279

A General Preorder Traversal Method 280

Using preOrderTraverse 280

Exercises for Section 6.4 281

6.5 Binary Search Trees 282

Overview of a Binary Search Tree 282

Performance 283

Interface SearchTree 283

The BinarySearchTree Class 283

Insertion into a Binary Search Tree 285

Removal from a Binary Search Tree 288

Testing a Binary Search Tree 293

Case Study: Writing an Index for a Term Paper 294

Exercises for Section 6.5 297

6.6 Heaps and Priority Queues 297

Inserting an Item into a Heap 298

Removing an Item from a Heap 298

Implementing a Heap 299

Priority Queues 302

The PriorityQueue Class 303

Using a Heap as the Basis of a Priority Queue 303

The Other Methods 306

Using a Comparator 306

The compare Method 306

Exercises for Section 6.6 307

6.7 Huffman Trees 308

Case Study: Building a Custom Huffman Tree 310

Exercises for Section 6.6 315

Java API Interfaces and Classes Introduced in This Chapter 316

User‐Defined Interfaces and Classes in This Chapter 317

Quick‐Check Exercises 317

Review Questions 318

Programming Projects 318

Answers to Quick-Check Exercises 320

**Chapter 7 Sets and Maps 323**

7.1 Sets and the Set Interface 324

The Set Abstraction 324

The Set Interface and Methods 325

Comparison of Lists and Sets 327

Exercises for Section 7.1 328

7.2 Maps and the Map Interface 329

The Map Hierarchy 330

The Map Interface 330

Exercises for Section 7.2 332

7.3 Hash Tables 333

Hash Codes and Index Calculation 333

Methods for Generating Hash Codes 334

Open Addressing 335

Table Wraparound and Search Termination 335

Traversing a Hash Table 337

Deleting an Item Using Open Addressing 337

Reducing Collisions by Expanding the Table Size 338

Reducing Collisions Using Quadratic Probing 338

Problems with Quadratic Probing 339

Chaining 340

Performance of Hash Tables 340

Exercises for Section 7.3 342

7.4 Implementing the Hash Table 344

Interface KWHashMap 344

Class Entry 344

Class HashtableOpen 345

Class HashtableChain 350

Testing the Hash Table Implementations 353

Exercises for Section 7.4 354

7.5 Implementation Considerations for Maps and Sets 354

Methods hashCode and equals 354

Implementing HashSetOpen 355

Writing HashSetOpen as an Adapter Class 355

Implementing the Java Map and Set Interfaces 356

Interface Map.Entry and Class AbstractMap.SimpleEntry 356

Creating a Set View of a Map 357

Method entrySet and Classes EntrySet and SetIterator 357

Classes TreeMap and TreeSet 358

Exercises for Section 7.5 359

7.6 Additional Applications of Maps 359

Case Study: Implementing a Cell Phone Contact List 359

Case Study: Completing the Huffman Coding Problem 361

Encoding the Huffman Tree 365

Exercises for Section 7.6 366

7.7 Navigable Sets and Maps 366

Application of a NavigableMap 368

Exercises for Section 7.7 370

Java API Interfaces and Classes Introduced in This Chapter 372

User‐Defined Interfaces and Classes in This Chapter 372

Quick‐Check Exercises 372

Review Questions 372

Programming Projects 373

Answers to Quick-Check Exercises 374

**Chapter 8 Sorting 375**

8.1 Using Java Sorting Methods 376

Exercises for Section 8.1 380

8.2 Selection Sort 380

Analysis of Selection Sort 381

Code for Selection Sort 381

Exercises for Section 8.2 383

8.3 Insertion Sort 383

Analysis of Insertion Sort 384

Code for Insertion Sort 385

Exercises for Section 8.3 386

8.4 Comparison of Quadratic Sorts 386

Comparisons versus Exchanges 387

Exercises for Section 8.4 388

8.5 Shell Sort: A Better Insertion Sort 388

Analysis of Shell Sort 389

Code for Shell Sort 390

Exercises for Section 8.5 391

8.6 Merge Sort 391

Analysis of Merge 392

Code for Merge 392

Algorithm for Merge Sort 394

Trace of Merge Sort Algorithm 394

Analysis of Merge Sort 394

Code for Merge Sort 395

Exercises for Section 8.6 396

8.7 Timsort 397

Merging Adjacent Sequences 400

Implementation 400

8.8 Heapsort 405

First Version of a Heapsort Algorithm 405

Revising the Heapsort Algorithm 405

Algorithm to Build a Heap 407

Analysis of Revised Heapsort Algorithm 407

Code for Heapsort 407

Exercises for Section 8.8 409

8.9 Quicksort 409

Algorithm for Quicksort 410

Analysis of Quicksort 411

Code for Quicksort 411

Algorithm for Partitioning 412

Code for partition 413

A Revised partition Algorithm 415

Code for Revised partition Method 416

Exercises for Section 8.9 417

8.10 Testing the Sort Algorithms 417

Exercises for Section 8.10 419

8.11 The Dutch National Flag Problem (Optional Topic) 419

Case Study: The Problem of the Dutch National Flag 419

Exercises for Section 8.11 422

Java Classes Introduced in This Chapter 423

User‐Defined Interfaces and Classes in This Chapter 423

Quick‐Check Exercises 424

Review Questions 424

Programming Projects 424

Answers to Quick-Check Exercises 425

**Chapter 9 Self-Balancing Search Trees 427**

9.1 Tree Balance and Rotation 428

Why Balance Is Important 428

Rotation 428

Algorithm for Rotation 429

Implementing Rotation 430

Exercises for Section 9.1 432

9.2 AVL Trees 432

Balancing a Left–Left Tree 432

Balancing a Left–Right Tree 433

Four Kinds of Critically Unbalanced Trees 434

Implementing an AVL Tree 436

Inserting into an AVL Tree 438

Removal from an AVL Tree 443

Performance of the AVL Tree 444

Exercises for Section 9.2 444

9.3 Red–Black Trees 445

Insertion into a Red–Black Tree 445

Removal from a Red–Black Tree 455

Performance of a Red–Black Tree 455

The TreeMap and TreeSet Classes 455

Exercises for Section 9.3 456

9.4 2–3 Trees 456

Searching a 2–3 Tree 457

Inserting an Item into a 2–3 Tree 457

Analysis of 2–3 Trees and Comparison with Balanced Binary Trees 461

Removal from a 2–3 Tree 461

Exercises for Section 9.4 462

9.5 B‐Trees and 2–3–4 Trees 463

B‐Trees 463

Implementing the B‐Tree 464

Code for the insert Method 466

The insertIntoNode Method 467

The splitNode Method 468

Removal from a B‐Tree 470

B+ Trees 471

2–3–4 Trees 471

Relating 2–3–4 Trees to Red–Black Trees 473

Exercises for Section 9.5 474

9.6 Skip‐Lists 475

Skip‐List Structure 475

Searching a Skip‐List 476

Performance of a Skip‐List Search 477

Inserting into a Skip‐List 477

Increasing the Height of a Skip‐List 477

Implementing a Skip‐List 477

Searching a Skip‐List 478

Insertion 479

Determining the Size of the Inserted Node 480

Completing the Insertion Process 480

Performance of a Skip‐List 480

Exercises for Section 9.6 480

Java Classes Introduced in This Chapter 482

User‐Defined Interfaces and Classes in This Chapter 482

Quick‐Check Exercises 482

Review Questions 483

Programming Projects 484

Answers to Quick-Check Exercises 486

**Chapter 10 Graphs 489**

10.1 Graph Terminology 490

Visual Representation of Graphs 490

Directed and Undirected Graphs 491

Paths and Cycles 491

Relationship between Graphs and Trees 493

Graph Applications 493

Exercises for Section 10.1 494

10.2 The Graph ADT and Edge Class 494

Representing Vertices and Edges 495

Exercises for Section 10.2 496

10.3 Implementing the Graph ADT 496

Adjacency List 497

Adjacency Matrix 497

Overview of the Hierarchy 499

Class AbstractGraph 499

The ListGraph Class 501

The MatrixGraph Class 503

Comparing Implementations 504

The MapGraph Class 505

Exercises for Section 10.3 505

10.4 Traversals of Graphs 506

Breadth‐First Search 506

Algorithm for Breadth‐First Search 508

Depth‐First Search 511

Exercises for Section 10.4 517

10.5 Applications of Graph Traversals 517

Case Study: Shortest Path through a Maze 517

Case Study: Topological Sort of a Graph 521

Exercises for Section 10.5 524

10.6 Algorithms Using Weighted Graphs 524

Finding the Shortest Path from a Vertex to All Other Vertices 524

Minimum Spanning Trees 528

Exercises for Section 10.6 531

User‐Defined Classes and Interfaces in This Chapter 533

Quick‐Check Exercises 533

Review Questions 534

Programming Projects 534

Answers to Quick-Check Exercises 536

**Appendix A Introduction to Java 541**

A.1 The Java Environment and Classes 542

The Java Virtual Machine 543

The Java Compiler 543

Classes and Objects 543

The Java API 543

The import Statement 544

Method main 544

Execution of a Java Program 545

Exercises for Section A.1 545

A.2 Primitive Data Types and Reference Variables 545

Primitive Data Types 545

Primitive‐Type Variables 547

Primitive‐Type Constants 547

Operators 547

Postfix and Prefix Increment 549

Type Compatibility and Conversion 549

Referencing Objects 550

Creating Objects 550

Exercises for Section A.2 551

A.3 Java Control Statements 551

Sequence and Compound Statements 551

Selection and Repetition Control 551

Nested if Statements 553

The switch Statement 555

Exercises for Section A.3 555

A.4 Methods and Class Math 555

The Instance Methods println and print 556

Call‐by‐Value Arguments 557

The Class Math 557

Escape Sequences 558

Exercises for Section A.4 559

A.5 The String, StringBuilder, StringBuffer, and StringJoiner Classes 559

The String Class 559

Strings Are Immutable 562

The Garbage Collector 562

Comparing Objects 562

The String.format Method 564

The Formatter Class 565

The String.split Method 565

Introduction to Regular Expressions 565

Matching One of a Group of Characters 566

Qualifiers 566

Defined Character Groups 567

Unicode Character Class Support 567

The StringBuilder and StringBuffer Classes 567

Java 8 StringJoiner Class 569

Exercises for Section A.5 570

A.6 Wrapper Classes for Primitive Types 571

Exercises for Section A.6 572

A.7 Defining Your Own Classes 573

Private Data Fields, Public Methods 576

Constructors 577

The No‐Parameter Constructor 577

Modifier and Accessor Methods 578

Use of this. in a Method 578

The Method toString 578

The Method equals 579

Declaring Local Variables in Class Person 580

An Application that Uses Class Person 580

Objects as Arguments 581

Classes as Components of Other Classes 582

Java Documentation Style for Classes and Methods 582

Exercises for Section A.7 585

A.8 Arrays 585

Data Field length 587

Method Arrays.copyOf 588

Method System.arrayCopy 588

Array Data Fields 589

Array Results and Arguments 590

Arrays of Arrays 590

Exercises for Section A.8 593

A.9 Enumeration Types 594

Using Enumeration Types 595

Assigning Values to Enumeration Types 596

Exercises for Section A.9 596

A.10 I/O Using Streams, Class Scanner, and Class JOptionPane 596

The Scanner 597

Using a Scanner to Read from a File 599

Exceptions 599

Tokenized Input 599

Extracting Tokens Using Scanner.findInLine 600

Using a BufferedReader to Read from an Input Stream 600

Output Streams 600

Passing Arguments to Method main 600

Closing Streams 601

Try with Resources 601

A Complete File‐Processing Application 601

Class InputStream and Character Codes (Optional) 603

The Default Character Coding (Optional) 603

UTF‐8 (Optional) 604

Specifying a Character Encoding (Optional) 605

Input/Output Using Class JOptionPane 605

Converting Numeric Strings to Numbers 606

GUI Menus Using Method showOptionDialog 607

Exercises for Section A.10 607

A.11 Catching Exceptions 608

Catching and Handling Exceptions 608

Exercises for Section A.11 614

A.12 Throwing Exceptions 614

The throws Clause 615

The throw Statement 616

Exercises for Section A.12 619

Java Constructs Introduced in This Appendix 621

Java API Classes Introduced in This Appendix 622

User‐Defined Interfaces and Classes in This Appendix 622

Quick‐Check Exercises 622

Review Questions 622

Programming Projects 623

Answer to Quick‐Check Exercises 624

**Appendix B Overview of UML 625**

B.1 The Class Diagram 626

Representing Classes and Interfaces 626

Generalization 629

Inner or Nested Classes 629

Association 629

Aggregation and Composition 630

Generic Classes 631

B.2 Sequence Diagrams 631

Time Axis 632

Objects 633

Life Lines 633

Activation Bars 633

Messages 633

Use of Notes 633

Glossary 635

Index 643

- New Introduce new features of Java 8 where appropriate. The authors use the Java 8 StringJoiner in place of the StringBuilder for creating delimited strings. The text also features Java 8 functional interfaces and Lambda expressions.
- New Additional emphasis on testing and debugging in Chapter 3. Chapter 3 features different aspects of testing (e.g. top-down, bottom-up, white-box, black-box), as well as a section on developing a JUnit test harness and a section on Test-Driven Development.
- New Ease the transition to Java for Python programmers. When introducing Java data structures (for example, arrays, lists, sets, and maps), the authors compare them to equivalent Python data structures.

- Combines a strong emphasis on problem solving and software design with the study of data structures. The authors discuss applications of each data structure to motivate its study. After providing the specification (interface) and the implementation (one or more Java classes) we then cover case studies that use the data structure to solve significant problems.
- Focuses on implementing effective programs using the Java Collections Framework and the classes in the framework. The code for these classes follows closely that which is provided in the framework and is not a conversion of code in other programming languages.
- Many problems have extensive discussions of testing and include classes and driver methods for testing solutions to case studies.
- Extensive pedagogy to assist inexperienced programmers in learning the material including boxes on Programming Pitfalls, Design concepts, and Programming Practice; Syntax boxes for quick reference; and self-check and end-of-section exercises for immediate feedback and practice