JavaTM foundations : introduction to program design and data structures / John Lewis and Joseph Chase

Includes bibliographical references and index.

Preface vii Chapter 1 Introduction 1 1.1 Software Quality 2 Correctness 3 Reliability 3 Robustness 4 Usability 4 Maintainability 5 Reusability 5 Portability 6 Efficiency 6 Quality Issues 6 1.2 Data Structures 7 A Physical Example 7 Containers as Objects 10 Chapter 2 Analysis of Algorithms 15 2.1 Algorithm Efficiency 16 2.2 Growth Functions and Big-Oh Notation 17 2.3 Comparing Growth Functions 19 2.4 Determining Time Complexity 22 Analyzing Loop Execution 22 Nested Loops 22 Method Calls 23 Chapter 3 Introduction to Collections - Stacks 29 3.1 Collections 30 Abstract Data Types 31 The Java Collections API 33 3.2 A Stack Collection 33 3.3 Crucial OO Concepts 35 Inheritance and Polymorphism 36 Generics 37 3.4 Using Stacks: Evaluating Postfix Expressions 38 Javadoc 45 3.5 Exceptions 46 3.6 A Stack ADT 48 3.7 Implementing a Stack: With Arrays 51 Managing Capacity 52 3.8 The ArrayStack Class 53 The Constructors 54 The push Operation 56 The pop Operation 57 The peek Operation 59 Other Operations 59 The EmptyCollectionException Class 59 Other Implementations 60 Chapter 4 Linked Structures - Stacks 67 4.1 R eferences as Links 68 4.2 Managing Linked Lists 70 Accessing Elements 70 Inserting Nodes 71 Deleting Nodes 72 4.3 Elements without Links 73 Doubly Linked Lists 73 4.4 Stacks in the Java API 74 4.5 Using Stacks: Traversing a Maze 75 4.6 Implementing a Stack: With Links 84 The LinkedStack Class 84 The push Operation 88 The pop Operation 90 Other Operations 91 Chapter 5 Queues 97 5.1 A Conceptual Queue 98 5.2 Queues in the Java API 99 5.3 Using Queues: Code Keys 100 5.4 Using Queues: Ticket Counter Simulation 104 5.5 A Queue ADT 109 5.6 A Linked Implementation of a Queue 111 The enqueue Operation 113 The dequeue Operation 115 Other Operations 116 5.7 Implementing Queues: With Arrays 117 The enqueue Operation 121 The dequeue Operation 123 Other Operations 124 5.8 Double-Ended Queues (Deque) 124 Chapter 6 Lists 129 6.1 A List Collection 130 6.2 Lists in the Java Collections API 132 6.3 Using Unordered Lists: Program of Study 133 6.4 Using Indexed Lists: Josephus 144 6.5 A List ADT 146 Adding Elements to a List 147 6.6 Implementing Lists with Arrays 152 The remove Operation 154 The contains Operation 156 The add Operation for an Ordered List 157 Operations Particular to Unordered Lists 159 The addAfter Operation for an Unordered List 159 6.7 Implementing Lists with Links 160 The remove Operation 161 Chapter 7 Iterators 169 7.1 What's an Iterator? 170 Other Iterator Issues 172 7.2 Using Iterators: Program of Study Revisited 172 Printing Certain Courses 176 Removing Courses 177 7.3 Implementing Iterators: With Arrays 179 7.4 Implementing Iterators: With Links 181 Chapter 8 Recursion 187 8.1 Recursive Thinking 188 Infinite Recursion 188 Recursion in Math 189 8.2 Recursive Programming 190 Recursion versus Iteration 193 Direct versus Indirect Recursion 193 8.3 Using Recursion 194 Traversing a Maze 194 The Towers of Hanoi 202 8.4 Analyzing Recursive Algorithms 207 Chapter 9 Searching and Sorting 215 9.1 Searching 216 Static Methods 217 Generic Methods 217 Linear Search

The fourth edition of Java Software Structuresembraces the enhancements of the latest version of Java, where all structures and collections are based on generics. The framework of the text walks the reader through three main areas: conceptualization, explanation, and implementation, allowing for a consistent and coherent introduction to data structures. Readers will learn how to develop high-quality software systems using well-designed collections and algorithms.