Data Structures and Abstractions with Java (5th Edition) (What's New in Computer Science)

Description

A relatable and friendly introduction to data structures and their implementation   The 5th Edition of Data Structures and Abstractions with Java introduces readers to data structures (CS-2) in a supportive, reader-friendly way. The book’s organization, sequencing, and pace of topic coverage make teaching and learning easier by: Focusing the reader’s attention on one concept at a time Providing flexibility in the order in which one can cover topics Clearly separating the specification of each abstract data type (ADT) from its implementation Placing relevant coverage of Java into Java Interludes, which you can use as needed.   To increase readability and learning potential, the numbered segments and modular presentation provide a flexible, customizable pathway through the material and focus the reader’s attention on one concept at a time. Numerous examples that mimic real-world situations provide a context for the new material and help to make it easier for audiences to learn and retain abstract concepts. The 5th Edition has a revamped structure and additional pedagogical tools to assist in mastering concepts. Data Structures and Abstractions with Java™, 5th Edition Title Page Copyright Welcome Brief Table of Contents New to This Edition A Note to Students Pedagogical Elements Resources Detailed Content Description Acknowledgments Contents VideoNotes Chapter Prerequisites Introduction Organizing Data Prelude Designing Classes Encapsulation Specifying Methods Java Interfaces Choosing Classes Reusing Classes Exercises Projects Chapter 1 Bags The Bag Specifying a Bag Using the ADT Bag Using an ADT Is Like Using a Vending Machine The ADT Set Java Class Library: The Interface Set Chapter Summary Programming Tip Exercises Projects Java Interlude 1 Generics Generic Data Types Chapter 2 Bag Implementations That Use Arrays Using a Fixed-Size Array to Implement the ADT Bag Using Array Resizing to Implement the ADT Bag The Pros and Cons of Using an Array to Implement the ADT Bag Chapter Summary Programming Tips Exercises Projects Java Interlude 2 Exceptions The Basics Handling an Exception Throwing an Exception Chapter 3 A Bag Implementation That Links Data Linked Data A Linked Implementation of the ADT Bag Removing an Item from a Linked Chain A Class Node That Has Set and Get Methods The Pros and Cons of Using a Chain to Implement the ADT Bag Chapter Summary Programming Tip Exercises Projects Chapter 4 The Efficiency of Algorithms Motivation Measuring an Algorithm’s Efficiency Big Oh Notation Picturing Efficiency The Efficiency of Implementations of the ADT Bag Chapter Summary Exercises Projects Chapter 5 Stacks Specifications of the ADT Stack Using a Stack to Process Algebraic Expressions The Program Stack Java Class Library: The Class Stack Chapter Summary Programming Tip Exercises Projects Chapter 6 Stack Implementations A Linked Implementation An Array-Based Implementation A Vector-Based Implementation Chapter Summary Exercises Projects Java Interlude 3 More About Exceptions Programmer-Defined Exception Classes Inheritance and Exceptions The finally Block Chapter 7 Queues, Deques, and Priority Queues The ADT Queue The ADT Deque The ADT Priority Queue Chapter Summary Programming Tip Exercises Projects Chapter 8 Queue, Deque, and Priority Queue Implementations A Linked Implementation of a Queue An Array-Based Implementation of a Queue Circular Linked Implementations of a Queue Java Class Library: The Class AbstractQueue A Doubly Linked Implementation of a Deque Possible Implementations of a Priority Queue Chapter Summary Programming Tip Exercises Projects Chapter 9 Recursion What Is Recursion? Tracing a Recursive Method Recursive Methods That Return a Value Recursively Processing an Array Recursively Processing a Linked Chain The Time Efficiency of Recursive Methods Tail Recursion Using a Stack Instead of Recursion Chapter Summary Programming Tips Exercises Projects Chapter 10 Lists Specifications for the ADT List Using the ADT List Java Class Library: The Interface List Java Class Library: The Class ArrayList Chapter Summary Exercises Projects Chapter 11 A List Implementation That Uses an Array Using an Array to Implement the ADT List The Efficiency of Using an Array to Implement the ADT List Chapter Summary Exercises Projects Chapter 12 A List Implementation That Links Data Operations on a Chain of Linked Nodes Beginning the Implementation Continuing the Implementation A Refined Implementation The Efficiency of Using a Chain to Implement the ADT List Java Class Library: The Class LinkedList Chapter Summary Exercises Projects Java Interlude 4 Iterators What Is an Iterator? The Interface Iterator The Interface ListIterator Chapter 13 Iterators for the ADT List Ways to Implement an Iterator A Separate Class Iterator An Inner Class Iterator Why Are Iterator Methods in Their Own Class? An Array-Based Implementation of the Interface ListIterator Chapter Summary Programming Tip Exercises Projects Chapter 14 Problem Solving with Recursion A Simple Solution to a Difficult Problem A Poor Solution to a Simple Problem Languages and Grammars Indirect Recursion Backtracking Chapter Summary Exercises Projects Java Interlude 5 More About Generics The Interface Comparable Generic Methods Bounded Type Parameters Wildcards Chapter 15 An Introduction to Sorting Organizing Java Methods That Sort an Array Selection Sort Insertion Sort Shell Sort Comparing the Algorithms Chapter Summary Programming Tip Exercises Projects Chapter 16 Faster Sorting Methods Merge Sort Quick Sort Radix Sort Comparing the Algorithms Chapter Summary Exercises Projects Java Interlude 6 Mutable and Immutable Objects Mutable Objects Immutable Objects Companion Classes Chapter 17 Sorted Lists Specifications for the ADT Sorted List A Linked Implementation An Implementation That Uses the ADT List Chapter Summary Exercises Projects Java Interlude 7 Inheritance and Polymorphism Further Aspects of Inheritance Polymorphism Chapter 18 Inheritance and Lists Using Inheritance to Implement a Sorted List Designing a Base Class An Efficient Implementation of a Sorted List Chapter Summary Programming Tips Exercises Projects Chapter 19 Searching The Problem Searching an Unsorted Array Searching a Sorted Array Searching an Unsorted Chain Searching a Sorted Chain Choosing a Search Method Chapter Summary Programming Tip Exercises Projects Java Interlude 8 Generics Once Again More Than One Generic Type Chapter 20 Dictionaries Specifications for the ADT Dictionary Using the ADT Dictionary Java Class Library: The Interface Map Chapter Summary Programming Tips Exercises Projects Chapter 21 Dictionary Implementations Array-Based Implementations Linked Implementations Chapter Summary Programming Tips Exercises Projects Chapter 22 Introducing Hashing What Is Hashing? Hash Functions Resolving Collisions Chapter Summary Exercises Projects Chapter 23 Hashing as a Dictionary Implementation The Efficiency of Hashing Rehashing Comparing Schemes for Collision Resolution A Dictionary Implementation That Uses Hashing Java Class Library: The Class HashMap Java Class Library: The Class HashSet Chapter Summary Exercises Projects Chapter 24 Trees Tree Concepts Traversals of a Tree Java Interfaces for Trees Examples of Binary Trees Examples of General Trees Chapter Summary Exercises Projects Chapter 25 Tree Implementations The Nodes in a Binary Tree An Implementation of the ADT Binary Tree An Implementation of an Expression Tree General Trees Using a Binary Tree to Represent a General Tree Chapter Summary Programming Tips Exercises Projects Java Interlude 9 Cloning Cloneable Objects Chapter 26 A Binary Search Tree Implementation Getting Started Searching and Retrieving Traversing Adding an Entry Removing an Entry The Efficiency of Operations An Implementation of the ADT Dictionary Chapter Summary Exercises Projects Chapter 27 A Heap Implementation Reprise: The ADT Heap Using an Array to Represent a Heap Adding an Entry Removing the Root Creating a Heap Heap Sort Chapter Summary Exercises Projects Chapter 28 Balanced Search Trees AVL Trees 2-3 Trees 2-4 Trees Red-Black Trees B-Trees Chapter Summary Exercises Projects Chapter 29 Graphs Some Examples and Terminology Traversals Topological Order Paths Java Interfaces for the ADT Graph Chapter Summary Exercises Projects Chapter 30 Graph Implementations An Overview of Two Implementations Vertices and Edges An Implementation of the ADT Graph Chapter Summary Exercises Projects Appendix A Documentation and Programming Style Naming Variables and Classes Indenting Comments Appendix B Java Classes Objects and Classes Using the Methods in a Java Class Defining a Java Class Enumeration as a Class Packages Appendix C Creating Classes from Other Classes Composition Inheritance Type Compatibility and Superclasses Index A B C D E F G H I J K L M N O P Q R S T U V W Supplement 1 Java Basics Introduction Elements of Java Simple Input and Output Using the Keyboard and Screen The if-else Statement The switch Statement Enumerations Scope Loops The Class String The Class StringBuilder Using Scanner to Extract Pieces of a String Arrays Wrapper Classes Supplement 2 File Input and Output Preliminaries Text Files Binary Files Glossary Answers to Study Questions Prelude Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 Chapter 12 Chapter 13 Chapter 14 Java Interlude 5 Chapter 15 Chapter 16 Chapter 17 Chapter 18 Chapter 19 Chapter 20 Chapter 21 Chapter 22 Chapter 24 Chapter 25 Java Interlude 9 Chapter 26 Chapter 27 Chapter 28 Chapter 29 Appendix B Appendix C