Wiley.com
Print this page Share
Textbook

Data Structures and Algorithms in Java 6/e

Data Structures and Algorithms in Java 6/e (EHEP002900) cover image

Description

The design and analysis of efficient data structures has long been recognized as a key component of the Computer Science curriculum. Goodrich, Tomassia and Goldwasser's approach to this classic topic is based on the object-oriented paradigm as the framework of choice for the design of data structures. For each ADT presented in the text, the authors provide an associated Java interface. Concrete data structures realizing the ADTs are provided as Java classes implementing the interfaces. The Java code implementing fundamental data structures in this book is organized in a single Java package, net.datastructures. This package forms a coherent library of data structures and algorithms in Java specifically designed for educational purposes in a way that is complimentary with the Java Collections Framework.

See More

Table of Contents

1 Java Primer 1

1.1 Getting Started  2

1.1.1 Base Types  4

1.2 Classes and Objects  5

1.2.1 Creating and Using Objects  6

1.2.2 Defining a Class   9

1.3 Strings, Wrappers, Arrays, and Enum Types 17

1.4 Expressions 23

1.4.1 Literals 23

1.4.2 Operators  24

1.4.3 Type Conversions  28

1.5 Control Flow 30

1.5.1 The If and Switch Statements    30

1.5.2 Loops 33

1.5.3 Explicit Control-Flow Statements   37

1.6 Simple Input and Output 38

1.7 An Example Program   41

1.8 Packages and Imports   44

1.9 Software Development  46

1.9.1 Design 46

1.9.2 Pseudocode  48

1.9.3 Coding 49

1.9.4 Documentation and Style 50

1.9.5 Testing and Debugging 53

1.10 Exercises 55

2 Object-Oriented Design 59

2.1 Goals, Principles, and Patterns  60

2.1.1 Object-Oriented Design Goals    60

2.1.2 Object-Oriented Design Principles  61

2.1.3 Design Patterns   63

2.2 Inheritance 64

2.2.1 Extending the CreditCard Class    65

2.2.2 Polymorphism and Dynamic Dispatch 68

2.2.3 Inheritance Hierarchies 69

2.3 Interfaces and Abstract Classes  76

2.3.1 Interfaces in Java  76

2.3.2 Multiple Inheritance for Interfaces  79

2.3.3 Abstract Classes   80

2.4 Exceptions 82

2.4.1 Catching Exceptions 82

2.4.2 Throwing Exceptions 85

2.4.3 Java’s Exception Hierarchy  86

2.5 Casting and Generics   88

2.5.1 Casting 88

2.5.2 Generics 91

2.6 Nested Classes 96

2.7 Exercises 97

3 Fundamental Data Structures 103

3.1 Using Arrays 104

3.1.1 Storing Game Entries in an Array   104

3.1.2 Sorting an Array   110

3.1.3 java.util Methods for Arrays and Random Numbers 112

3.1.4 Simple Cryptography with Character Arrays  115

3.1.5 Two-Dimensional Arrays and Positional Games 118

3.2 Singly Linked Lists  122

3.2.1 Implementing a Singly Linked List Class 126

3.3 Circularly Linked Lists   128

3.3.1 Round-Robin Scheduling 128

3.3.2 Designing and Implementing a Circularly Linked List  129

3.4 Doubly Linked Lists  132

3.4.1 Implementing a Doubly Linked List Class   135

3.5 Equivalence Testing  138

3.5.1 Equivalence Testing with Arrays   139

3.5.2 Equivalence Testing with Linked Lists 140

3.6 Cloning Data Structures 141

3.6.1 Cloning Arrays  142

3.6.2 Cloning Linked Lists 144

3.7 Exercises 145

4 Algorithm Analysis 149

4.1 Experimental Studies   151

4.1.1 Moving Beyond Experimental Analysis 154

4.2 The Seven Functions Used in This Book  156

4.2.1 Comparing Growth Rates 163

4.3 Asymptotic Analysis  164

4.3.1 The “Big-Oh” Notation 164

4.3.2 Comparative Analysis 168

4.3.3 Examples of Algorithm Analysis   170

4.4 Simple Justification Techniques  178

4.4.1 By Example  178

4.4.2 The “Contra” Attack 178

4.4.3 Induction and Loop Invariants    179

4.5 Exercises 182

5 Recursion 189

5.1 Illustrative Examples   191

5.1.1 The Factorial Function 191

5.1.2 Drawing an English Ruler 193

5.1.3 Binary Search  196

5.1.4 File Systems  198

5.2 Analyzing Recursive Algorithms  202

5.3 Further Examples of Recursion 206

5.3.1 Linear Recursion   206

5.3.2 Binary Recursion  211

5.3.3 Multiple Recursion 212

5.4 Designing Recursive Algorithms  214

5.5 Recursion Run Amok   215

5.5.1 Maximum Recursive Depth in Java  218

5.6 Eliminating Tail Recursion 219

5.7 Exercises 221

6 Stacks, Queues, and Deques 225

6.1 Stacks   226

6.1.1 The Stack Abstract Data Type    227

6.1.2 A Simple Array-Based Stack Implementation 230

6.1.3 Implementing a Stack with a Singly Linked List 233

6.1.4 Reversing an Array Using a Stack  234

6.1.5 Matching Parentheses and HTML Tags 235

6.2 Queues  238

6.2.1 The Queue Abstract Data Type   239

6.2.2 Array-Based Queue Implementation  241

6.2.3 Implementing a Queue with a Singly Linked List 245

6.2.4 A Circular Queue  246

6.3 Double-Ended Queues   248

6.3.1 The Deque Abstract Data Type   248

6.3.2 Implementing a Deque 250

6.3.3 Deques in the Java Collections Framework   251

6.4 Exercises 252

7 List and Iterator ADTs 257

7.1 The List ADT 258

7.2 Array Lists 260

7.2.1 Dynamic Arrays   263

7.2.2 Implementing a Dynamic Array    264

7.2.3 Amortized Analysis of Dynamic Arrays 265

7.2.4 Java’s StringBuilder class 269

7.3 Positional Lists 270

7.3.1 Positions 272

7.3.2 The Positional List Abstract Data Type 272

7.3.3 Doubly Linked List Implementation  276

7.4 Iterators  282

7.4.1 The Iterable Interface and Java’s For-Each Loop 283

7.4.2 Implementing Iterators 284

7.5 The Java Collections Framework  288

7.5.1 List Iterators in Java 289

7.5.2 Comparison to Our Positional List ADT 290

7.5.3 List-Based Algorithms in the Java Collections Framework   291

7.6 Sorting a Positional List 293

7.7 Case Study: Maintaining Access Frequencies   294

7.7.1 Using a Sorted List 294

7.7.2 Using a List with the Move-to-Front Heuristic 297

7.8 Exercises 300

8 Trees 307

8.1 General Trees308

8.1.1 Tree Definitions and Properties    309

8.1.2 The Tree Abstract Data Type    312

8.1.3 Computing Depth and Height  314

8.2 Binary Trees 317

8.2.1 The Binary Tree Abstract Data Type  319

8.2.2 Properties of Binary Trees  321

8.3 Implementing Trees  323

8.3.1 Linked Structure for Binary Trees   323

8.3.2 Array-Based Representation of a Binary Tree 331

8.3.3 Linked Structure for General Trees  333

8.4 Tree Traversal Algorithms 334

8.4.1 Preorder and Postorder Traversals of General Trees 334

8.4.2 Breadth-First Tree Traversal  336

8.4.3 Inorder Traversal of a Binary Tree  337

8.4.4 Implementing Tree Traversals in Java 339

8.4.5 Applications of Tree Traversals    343

8.4.6 Euler Tours  348

8.5 Exercises 350

9 Priority Queues 359

9.1 The Priority Queue Abstract Data Type  360

9.1.1 Priorities 360

9.1.2 The Priority Queue ADT 361

9.2 Implementing a Priority Queue  362

9.2.1 The Entry Composite 362

9.2.2 Comparing Keys with Total Orders  363

9.2.3 The AbstractPriorityQueue Base Class 364

9.2.4 Implementing a Priority Queue with an Unsorted List  366

9.2.5 Implementing a Priority Queue with a Sorted List 368

9.3 Heaps   370

9.3.1 The Heap Data Structure 370

9.3.2 Implementing a Priority Queue with a Heap  372

9.3.3 Analysis of a Heap-Based Priority Queue 379

9.3.4 Bottom-Up Heap Construction ⋆  380

9.3.5 Using the java.util.PriorityQueue Class 384

9.4 Sorting with a Priority Queue 385

9.4.1 Selection-Sort and Insertion-Sort   386

9.4.2 Heap-Sort  388

9.5 Adaptable Priority Queues 390

9.5.1 Location-Aware Entries 391

9.5.2 Implementing an Adaptable Priority Queue  392

9.6 Exercises 395

10 Maps, Hash Tables, and Skip Lists 401

10.1 Maps   402

10.1.1 The Map ADT   403

10.1.2 Application: Counting Word Frequencies 405

10.1.3 An AbstractMap Base Class  406

10.1.4 A Simple Unsorted Map Implementation 408

10.2 Hash Tables 410

10.2.1 Hash Functions   411

10.2.2 Collision-Handling Schemes  417

10.2.3 Load Factors, Rehashing, and Efficiency 420

10.2.4 Java Hash Table Implementation   422

10.3 Sorted Maps 428

10.3.1 Sorted Search Tables 429

10.3.2 Two Applications of Sorted Maps  433

10.4 Skip Lists 436

10.4.1 Search and Update Operations in a Skip List 438

10.4.2 Probabilistic Analysis of Skip Lists ⋆  442

10.5 Sets, Multisets, and Multimaps  445

10.5.1 The Set ADT  445

10.5.2 The Multiset ADT 447

10.5.3 The Multimap ADT 448

10.6 Exercises 451

11 Search Trees 459

11.1 Binary Search Trees  460

11.1.1 Searching Within a Binary Search Tree 461

11.1.2 Insertions and Deletions 463

11.1.3 Java Implementation 466

11.1.4 Performance of a Binary Search Tree  470

11.2 Balanced Search Trees  472

11.2.1 Java Framework for Balancing Search Trees  475

11.3 AVL Trees 479

11.3.1 Update Operations 481

11.3.2 Java Implementation 486

11.4 Splay Trees 488

11.4.1 Splaying 488

11.4.2 When to Splay  492

11.4.3 Java Implementation 494

11.4.4 Amortized Analysis of Splaying ⋆  495

11.5 (2,4) Trees 500

11.5.1 Multiway Search Trees 500

11.5.2 (2,4)-Tree Operations 503

11.6 Red-Black Trees  510

11.6.1 Red-Black Tree Operations  512

11.6.2 Java Implementation 522

11.7 Exercises 525

12 Sorting and Selection 531

12.1 Merge-Sort 532

12.1.1 Divide-and-Conquer 532

12.1.2 Array-Based Implementation of Merge-Sort  537

12.1.3 The Running Time of Merge-Sort  538

12.1.4 Merge-Sort and Recurrence Equations ⋆ 540

12.1.5 Alternative Implementations of Merge-Sort  541

12.2 Quick-Sort 544

12.2.1 Randomized Quick-Sort 551

12.2.2 Additional Optimizations for Quick-Sort 553

12.3 Studying Sorting through an Algorithmic Lens  556

12.3.1 Lower Bound for Sorting 556

12.3.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort 558

12.4 Comparing Sorting Algorithms 561

12.5 Selection 563

12.5.1 Prune-and-Search  563

12.5.2 Randomized Quick-Select 564

12.5.3 Analyzing Randomized Quick-Select  565

12.6 Exercises 566

13 Text Processing 573

13.1 Abundance of Digitized Text 574

13.1.1 Notations for Character Strings    575

13.2 Pattern-Matching Algorithms 576

13.2.1 Brute Force  576

13.2.2 The Boyer-Moore Algorithm  578

13.2.3 The Knuth-Morris-Pratt Algorithm  582

13.3 Tries 586

13.3.1 Standard Tries  586

13.3.2 Compressed Tries  590

13.3.3 Suffix Tries  592

13.3.4 Search Engine Indexing 594

13.4 Text Compression and the Greedy Method 595

13.4.1 The Huffman Coding Algorithm   596

13.4.2 The Greedy Method 597

13.5 Dynamic Programming  598

13.5.1 Matrix Chain-Product 598

13.5.2 DNA and Text Sequence Alignment  601

13.6 Exercises 605

14 Graph Algorithms 611

14.1 Graphs   612

14.1.1 The Graph ADT   618

14.2 Data Structures for Graphs 619

14.2.1 Edge List Structure 620

14.2.2 Adjacency List Structure 622

14.2.3 Adjacency Map Structure 624

14.2.4 Adjacency Matrix Structure  625

14.2.5 Java Implementation 626

14.3 Graph Traversals  630

14.3.1 Depth-First Search 631

14.3.2 DFS Implementation and Extensions  636

14.3.3 Breadth-First Search 640

14.4 Transitive Closure  643

14.5 Directed Acyclic Graphs 647

14.5.1 Topological Ordering 647

14.6 Shortest Paths 651

14.6.1 Weighted Graphs  651

14.6.2 Dijkstra’s Algorithm 653

14.7 Minimum Spanning Trees 662

14.7.1 Prim-Jarn´ýk Algorithm 664

14.7.2 Kruskal’s Algorithm 667

14.7.3 Disjoint Partitions and Union-Find Structures 672

14.8 Exercises 677

15 Memory Management and B-Trees 687

15.1 Memory Management   688

15.1.1 Stacks in the Java Virtual Machine  688

15.1.2 Allocating Space in the Memory Heap 691

15.1.3 Garbage Collection 693

15.2 Memory Hierarchies and Caching  695

15.2.1 Memory Systems  695

15.2.2 Caching Strategies 696

15.3 External Searching and B-Trees  701

15.3.1 (a,b) Trees  702

15.3.2 B-Trees 704

15.4 External-Memory Sorting 705

15.4.1 Multiway Merging  706

15.5 Exercises 707

Bibliography 710

Index 714

See More

New To This Edition

  • The authors redesigned the entire code base to increase clarity of presentation and consistency in style and convention, including reliance on type inference, as introduced in Java 7, to reduce clutter when instantiating generic types.
  • A new chapter, dedicated to the topic of recursion, provides comprehensive coverage of material that was previously divided within multiple chapters, while newly introducing the use of recursion when processing file systems.
  • The authors have added 38 new figures, and redesigned 144 existing figures.
  • New co-author Michael Goldwasser, Professor and Director of Computer Science at St. Louis University, has been added to the author team.
See More

The Wiley Advantage

  • Known for its clarity of presentation, DSA Java presents even the most difficult mathematical concepts in terms students can understand. 
  • A robust set of end-of-chapter problems are arranged by purpose – reinforcement problems assess understanding; creativity problems require students to apply concepts to writing “classes” (portions of a program); projects require students to write entire programs.
  • Java code examples are used extensively, with source code provided on the student companion site . Students learn to build data structures using a simple API which is consistent with the Java Collections Framework.  The authors describe the Java Collections Framework and point out how the API in use may differ from the Java Collections Framework.
  • An effective in-text art program illustrate data structures and algorithms in a clear, visual manner.  Visual proofs help students develop a better understanding of mathematical topics.
  • Coverage of Internet-related topics including hashing and text processing.
  • Discussion of object-oriented design and the Java programming language, including the Collections Framework and Design Patterns help students grasp both data structures and object-oriented design issues.  The book presents several object-oriented design patterns and important Java language constructs, like iterators and generic types, as well as all the traditional data structures topics.
See More
Instructors Resources
Wiley Instructor Companion Site
Instructor’s Solutions Manual
Contains detailed solutions to all questions, exercises, and problems in the textbook.
PowerPoint Presentations
Our PowerPoint™ presentations contain a combination of key concepts allowing you to illustrate important topics with images, figures, and problems from the textbook.
Source Code
Correlation Guide
A correlation of the fifth edition exercises to the sixth edition.
Digital evaluation copy available for this title
Request Copy
Contact your Wiley Representative
Find Your Rep
See More
See Less
Students Resources
Wiley Student Companion Site
PowerPoint Presentations
Our PowerPoint™ presentations contain a combination of key concepts allowing you to illustrate important topics with images, figures, and problems from the textbook.
Study Guide
Hints, Presentations, and Code Fragments
Source Code
Study Guide
Hints for all exercises.
Useful Mathematical Facts
An appendix to the book, available online only
See More
See Less
Purchase Options
Wiley E-Text   
Data Structures and Algorithms in Java, 6th Edition
ISBN : 978-1-118-80314-1
738 pages
January 2014, ©2014
$64.00   BUY

Paperback   
Data Structures and Algorithms in Java, 6th Edition
ISBN : 978-1-118-77133-4
738 pages
January 2014, ©2014
$167.95   BUY

Related Titles

Back to Top