Data Structures: Abstraction and Design Using Java

Data Structures: Abstraction and Design Using Java offers a coherent and well-balanced presentation of data structure implementation and data structure applications with a strong emphasis on problem solving and software design. Step-by-step, the authors introduce each new data structure as an abstract data type (ADT), explain its underlying theory and computational complexity, provide its specification in the form of a Java interface, and demonstrate its implementation as one or more Java classes. Case studies using the data structures covered in the chapter show complete and detailed solutions to real-world problems, while a variety of software design tools are discussed to help students “Think, then code.”

The book supplements its rigorous coverage of basic data structures and algorithms with chapters on sets and maps, balanced binary search trees, graphs, event-oriented programming, testing and debugging, and other key topics. Now available as an enhanced e-book, the fourth edition of Data Structures: Abstraction and Design Using Java enables students to measure their progress after completing each section through interactive questions, quick-check questions, and review questions.

Preface

Chapter 1 Object-Oriented Programming and Class Hierarchies

1.1 Abstract Data Types(ADTs), Interfaces, and the Java API

Interfaces

The implements Clause

Declaring a Variable of an Interface Type

Exercises for Section 1.1

1.2 Introduction to OOP

A Superclass and Subclass Example

Use of this

Initializing Data Fields in a Subclass

The No‐Parameter Constructor

Protected Visibility for Superclass Data Fields

Is‐a versus Has‐a Relationships

Exercises for Section 1.2

1.3 Method Overriding, Method Overloading, and Polymorphism

Method Overriding

Method Overloading

Polymorphism

Methods with Class Parameters

Exercises for Section 1.3

1.4 Abstract Classes

Referencing Actual Objects

Initializing Data Fields in an Abstract Class

Abstract Class Number and the Java Wrapper Classes

Summary of Features of Actual Classes, Abstract Classes,

and Interfaces

Implementing Multiple Interfaces

Extending an Interface

Exercises for Section 1.4

1.5 Class Object and Casting

The Method toString

Operations Determined by Type of Reference Variable

Casting in a Class Hierarchy

Using instanceof to Guard a Casting Operation

The Class Class

Exercises for Section 1.5

1.6 A Java Inheritance Example—The Exception Class Hierarchy

Division by Zero

Array Index Out of Bounds

Null Pointer

The Exception Class Hierarchy

The Class Throwable

Checked and Unchecked Exceptions

Handling Exceptions to Recover from Errors

Using try-catch to Recover from an Error

Throwing an Exception When Recovery Is Not Obvious

Exercises for Section 1.6

1.7 Packages and Visibility

Packages

The No‐Package‐Declared Environment

Package Visibility

Visibility Supports Encapsulation

Exercises for Section 1.7

1.8 A Shape Class Hierarchy

Case Study: Processing Geometric Figures

Exercises for Section 1.8

Java Constructs Introduced in This Chapter

Java API Classes Introduced in This Chapter

User‐Defined Interfaces and Classes in This Chapter

Quick‐Check Exercises

Review Questions

Programming Projects

Answers to Quick-Check Exercises

Chapter 2 Lists and the Collections Framework

2.1 Algorithm Efficiency and Big-O

Big-O Notation

Formal Definition of Big-O

Summary of Notation

Comparing Performance

The Power of O(log n) Algorithms

Algorithms with Exponential and Factorial Growth Rates

Exercises for Section 2.1

2.2 The List Interface and ArrayList Class

The ArrayList Class

Generic Collections

Exercises for Section 2.2

2.3 Applications of ArrayList

A Phone Directory Application

Exercises for Section 2.3

2.4 Implementation of an ArrayList Class

The Constructor for Class KWArrayList<E>

The add(E anEntry) Method

The add(int index, E anEntry) Method

The set and get Methods

The remove Method

The reallocate Method

Performance of the KWArrayList Algorithms

Exercises for Section 2.4

2.5 Single‐Linked Lists

A List Node

Connecting Nodes

A Single-Linked List Class

Inserting a Node in a List

Removing a Node

Completing the KWSingleLinkedList Class

The get and set Methods

The add Methods

Exercises for Section 2.5

2.6 Double‐Linked Lists and Circular Lists

The Node Class

Inserting into a Double‐Linked List

Removing from a Double‐Linked List

A Double‐Linked List Class

Circular Lists

Exercises for Section 2.6

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

The LinkedList Class

The Iterator

The Iterator Interface

The Enhanced for Loop

The ListIterator Interface

Comparison of Iterator and ListIterator

Conversion between a ListIterator and an Index

The Iterable Interface

Exercises for Section 2.7

2.8 Application of the LinkedList Class

Case Study: Maintaining an Ordered List

Testing Class OrderedList

Exercises for Section 2.8

2.9 Implementation of a Double‐Linked List Class

Implementing the KWLinkedList Methods

A Class that Implements the ListIterator Interface

The Constructor

The hasNext and next Methods

The hasPrevious and previous Methods

The add Method

Inner Classes: Static and Nonstatic

Exercises for Section 2.9

2.10 The Collections Framework Design

The Collection Interface

Common Features of Collections

The AbstractCollection, AbstractList, and

AbstractSequentialList Classes

The List and RandomAccess Interfaces (Advanced)

Exercises for Section 2.10

Java API Interfaces and Classes Introduced in This Chapter

User‐Defined Interfaces and Classes in This Chapter

Quick‐Check Exercises

Review Questions

Programming Projects

Answers to Quick-Check Exercises

Chapter 3 Testing and Debugging

3.1 Types of Testing

Preparations for Testing

Testing Tips for Program Systems

Exercises for Section 3.1

3.2 Specifying the Tests

Testing Boundary Conditions

Exercises for Section 3.2

3.3 Stubs and Drivers

Stubs

Preconditions and Postconditions

Drivers

Exercises for Section 3.3

3.4 The JUnit5 Platform

Exercises for Section 3.4

3.5 Test‐Driven Development

Exercises for Section 3.5

3.6 Testing Interactive Programs in JUnit

ByteArrayInputStream

ByteArrayOutputStream

Exercises for Section 3.6

3.7 Debugging a Program

Using a Debugger

The IntelliJ and Eclipse Debuggers

Exercises for Section 3.7

Java API Classes Introduced in This Chapter

User‐Defined Interfaces and Classes in This Chapter

Quick‐Check Exercises

Review Questions

Programming

Answers to Quick-Check Exercises

Chapter 4 Stacks, Queues, and Deques

4.1 Stack Abstract Data Type

Specification of the Stack Abstract Data Type

Exercises for Section 4.1

4.2 Stack Applications

Case Study: Finding Palindromes

Exercises for Section 4.2

4.3 Implementing a Stack

Implementing a Stack with an ArrayList Component

Implementing a Stack as a Linked Data Structure

Comparison of Stack Implementations

Exercises for Section 4.3

4.4 Additional Stack Applications

Case Study: Evaluating Postfix Expressions

Case Study: Converting from Infix to Postfix

Method processOperator

Case Study: Converting Expressions with Parentheses

Tying the Case Studies Together

Exercises for Section 4.4

4.5 Queue Abstract Data Type

A Print Queue

The Unsuitability of a “Print Stack”

A Queue of Customers

Using a Queue for Traversing a Multi‐Branch Data Structure

Specification for a Queue Interface

Class LinkedList Implements the Queue Interface

Exercises for Section 4.5

4.6 Queue Applications

Case Study: Maintaining a Queue

Exercises for Section 4.6

4.7 Implementing the Queue Interface

Using a Double‐Linked List to Implement the Queue Interface

Using a Single‐Linked List to Implement the Queue Interface

Using a Circular Array to Implement the Queue Interface

Exercises for Section 4.7

4.8 The Deque Interface

Classes that Implement Deque

Using a Deque as a Queue

Using a Deque as a Stack

Exercises for Section 4.8

Java API Classes Introduced in This Chapter

User‐Defined Interfaces and Classes in This Chapter

Quick‐Check Exercises

Review Questions

Programming Projects

Answers to Quick-Check Exercises

Chapter 5 Recursion

5.1 Recursive Thinking

Steps to Design a Recursive Algorithm

Proving that a Recursive Method Is Correct

Tracing a Recursive Method

The Run‐Time Stack and Activation Frames

Exercises for Section 5.1

5.2 Recursive Definitions of Mathematical Formulas

Tail Recursion versus Iteration

Efficiency of Recursion

Exercises for Section 5.2

5.3 Recursive Array Search

Design of a Recursive Linear Search Algorithm

Implementation of Linear Search

Design of a Binary Search Algorithm

Efficiency of Binary Search

The Comparable Interface

Implementation of Binary Search

Testing Binary Search

Method Arrays.binarySearch

Exercises for Section 5.3

5.4 Recursive Data Structures

Recursive Definition of a Linked List

Class LinkedListRec

Removing a List Node

Exercises for Section 5.4

5.5 Problem Solving with Recursion

Case Study: Towers of Hanoi

Case Study: Counting Cells in a Blob

Exercises for Section 5.5

5.6 Backtracking

Case Study: Finding a Path through a Maze

Exercises for Section 5.6

User‐Defined Classes in This Chapter

Quick‐Check Exercises

Review Questions

Programming Projects

Answers to Quick-Check Exercises

Chapter 6 Trees 257

6.1 Tree Terminology and Applications

Tree Terminology

Binary Trees

Some Types of Binary Trees

General Trees

Exercises for Section 6.1

6.2 Tree Traversals

Visualizing Tree Traversals

Traversals of Binary Search Trees and Expression Trees

Exercises for Section 6.2

6.3 Implementing a BinaryTree Class

The Node<E> Class

The BinaryTree<E> Class

Exercises for Section 6.3

6.4 Lambda Expressions and Functional Interfaces

Functional Interfaces

A General Preorder Traversal Method

Using preOrderTraverse

Exercises for Section 6.4

6.5 Binary Search Trees

Overview of a Binary Search Tree

Performance

Interface SearchTree

The BinarySearchTree Class

Insertion into a Binary Search Tree

Removal from a Binary Search Tree

Testing a Binary Search Tree

Case Study: Writing an Index for a Term Paper

Exercises for Section 6.5

6.6 Heaps and Priority Queues

Inserting an Item into a Heap

Removing an Item from a Heap

Implementing a Heap

Priority Queues

The PriorityQueue Class

The Other Methods

The compare Method

Exercises for Section 6.6

6.7 Huffman Trees

Case Study: Building a Custom Huffman Tree

Exercises for Section 6.6

Java API Interfaces and Classes Introduced in This Chapter

User‐Defined Interfaces and Classes in This Chapter

Quick‐Check Exercises

Review Questions

Programming Projects

Answers to Quick-Check Exercises

Chapter 7 Sets and Maps

7.1 Sets and the Set Interface

The Set Abstraction

The Set Interface and Methods

Using Method of to Initialize a Collection

Comparison of Lists and Sets

Exercises for Section 7.1

7.2 Maps and the Map Interface

The Map Hierarchy

The Map Interface

Creating a Map

Exercises for Section 7.2

7.3 Hash Tables

Hash Codes and Index Calculation

Methods for Generating Hash Codes

Open Addressing

Table Wraparound and Search Termination

Traversing a Hash Table

Deleting an Item Using Open Addressing

Reducing Collisions by Expanding the Table Size

Reducing Collisions Using Quadratic Probing

Problems with Quadratic Probing

Chaining

Performance of Hash Tables

Exercises for Section 7.3

7.4 Implementing the Hash Table

Interface KWHashMap

Class Entry

Class HashtableOpen

Class HashtableChain

Testing the Hash Table Implementations

Exercises for Section 7.4

7.5 Implementation Considerations for Maps and Sets

Methods hashCode and equals

Implementing HashSetOpen

Writing HashSetOpen as an Adapter Class

Implementing the Java Map and Set Interfaces

Interface Map.Entry and Class AbstractMap.SimpleEntry

Creating a Set View of a Map

Method entrySet and Classes EntrySet and SetIterator

Classes TreeMap and TreeSet

Exercises for Section 7.5

7.6 Additional Applications of Maps

Case Study: Implementing a Cell Phone Contact List

Case Study: Completing the Huffman Coding Problem

Encoding the Huffman Tree

Exercises for Section 7.6

7.7 Navigable Sets and Maps

Application of a NavigableMap

Exercises for Section 7.7

Java API Interfaces and Classes Introduced in This Chapter

User‐Defined Interfaces and Classes in This Chapter

Quick‐Check Exercises

Review Questions

Programming Projects

Answers to Quick-Check Exercises

Chapter 8 Sorting

8.1 Using Java Sorting Methods

Exercises for Section 8.1

8.2 Selection Sort

Analysis of Selection Sort

Code for Selection Sort

Exercises for Section 8.2

8.3 Insertion Sort

Analysis of Insertion Sort

Code for Insertion Sort

Exercises for Section 8.3

8.4 Comparison of Quadratic Sorts

Comparisons versus Exchanges

Exercises for Section 8.4

8.5 Shell Sort: A Better Insertion Sort

Analysis of Shell Sort

Code for Shell Sort

Exercises for Section 8.5

8.6 Merge Sort

Analysis of Merge

Code for Merge

Algorithm for Merge Sort

Trace of Merge Sort Algorithm

Analysis of Merge Sort

Code for Merge Sort

Exercises for Section 8.6

8.7 Timsort

Merging Adjacent Sequences

Implementation

8.8 Heapsort

First Version of a Heapsort Algorithm

Revising the Heapsort Algorithm

Algorithm to Build a Heap

Analysis of Revised Heapsort Algorithm

Code for Heapsort

Exercises for Section 8.8

8.9 Quicksort

Algorithm for Quicksort

Analysis of Quicksort

Code for Quicksort

Algorithm for Partitioning

Code for partition

A Revised partition Algorithm

Code for Revised partition Method

Exercises for Section 8.9

8.10 Testing the Sort Algorithms

Exercises for Section 8.10

8.11 The Dutch National Flag Problem (Optional Topic)

Case Study: The Problem of the Dutch National Flag

Exercises for Section 8.11

Java Classes Introduced in This Chapter

User‐Defined Interfaces and Classes in This Chapter

Quick‐Check Exercises

Review Questions

Programming Projects

Answers to Quick-Check Exercises

Chapter 9 Self-Balancing Search Trees

9.1 Tree Balance and Rotation 428

Why Balance Is Important

Rotation

Algorithm for Rotation

Implementing Rotation

Exercises for Section 9.1

9.2 AVL Trees

Balancing a Left–Left Tree

Balancing a Left–Right Tree

Four Kinds of Critically Unbalanced Trees

Implementing an AVL Tree

Inserting into an AVL Tree

Removal from an AVL Tree

Performance of the AVL Tree

Exercises for Section 9.2

9.3 Red–Black Trees

Insertion into a Red–Black Tree

Removal from a Red–Black Tree

Performance of a Red–Black Tree

The TreeMap and TreeSet Classes

Exercises for Section 9.3

9.4 2–3 Trees

Searching a 2–3 Tree

Inserting an Item into a 2–3 Tree

Analysis of 2–3 Trees and Comparison with

Balanced Binary Trees

Removal from a 2–3 Tree

Exercises for Section 9.4

9.5 B‐Trees and 2–3–4 Trees

B‐Trees

Implementing the B‐Tree

Code for the insert Method

The insertIntoNode Method

The splitNode Method

Removal from a B‐Tree

B+ Trees

2–3–4 Trees

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

Exercises for Section 9.5

Java Classes Introduced in This Chapter

User‐Defined Interfaces and Classes in This Chapter

Quick‐Check Exercises

Review Questions

Programming Projects

Answers to Quick-Check Exercises

Chapter 10 Graphs

10.1 Graph Terminology

Visual Representation of Graphs

Directed and Undirected Graphs

Paths and Cycles

Relationship between Graphs and Trees

Graph Applications

Exercises for Section 10.1

10.2 The Graph ADT and Edge Class

Representing Vertices and Edges

Exercises for Section 10.2

10.3 Implementing the Graph ADT

Adjacency List

Adjacency Matrix

Overview of the Hierarchy

Declaring the Graph Interface

The ListGraph Class

The MatrixGraph Class

Comparing Implementations

The MapGraph Class

Exercises for Section 10.3

10.4 Traversals of Graphs

Breadth‐First Search

Depth‐First Search

Exercises for Section 10.4

10.5 Applications of Graph Traversals

Case Study: Shortest Path through a Maze

Case Study: Topological Sort of a Graph

Exercises for Section 10.5

10.6 Algorithms Using Weighted Graphs

Finding the Shortest Path from a Vertex to All Other Vertices

Minimum Spanning Trees

Exercises for Section 10.6

10.7 A Heuristic Algorithm A* to Find the Best Path

A* (A-Star) an Improvement of Dijkstra’s Algorithm

Exercises for Section 10.7

User‐Defined Classes and Interfaces in This Chapter

Quick‐Check Exercises

Review Questions

Programming Projects

Answers to Quick-Check Exercises

Appendix A Introduction to Java

A.1 The Java Environment and Classes

The Java Virtual Machine

The Java Compiler

Classes and Objects

The Java API

The import Statement

Method main

Execution of a Java Program

Use of jshell

Exercises for Section A.1

A.2 Primitive Data Types and Reference Variables

Primitive Data Types

Primitive‐Type Variables

Primitive‐Type Constants

Operators

Postfix and Prefix Increment

Type Compatibility and Conversion

Referencing Objects

Creating Objects

Exercises for Section A.2

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.