For one- or two-semester courses in data structures (CS-2) in the departments of Computer Science, Computer Engineering, Business, and Management Information Systems. This is the most student-friendly data structures text available that introduces ADTs in individual, brief chapters - each with pedagogical tools to help students master each concept. Using the latest features of Java, this unique object-oriented presentation makes a clear distinction between specification and implementation to simplify learning, while providing maximum classroom flexibility. Visit author Frank Carranos Making it Real blog -- a discussion with instructors and students about teaching and leaning computer science. http://frank-m-carrano.com/blog/
Introduction 1 Chapter 1 Bags 5 The Bag 6 A Bags Behaviors 6 Specifying a Bag 7 An Interface 13 Using the ADT Bag 15 Using an ADT Is Like Using a Vending Machine 20 Java Class Library: The Interface Set 21 Chapter 2 Bag Implementations That Use Arrays 27 Using a Fixed-Size Array to Implement the ADT Bag 28 An Analogy 28 A Group of Core Methods 29 Implementing the Core Methods 30 Testing the Core Methods 37 Implementing More Methods 40 Methods That Remove Entries 42 Using Array Resizing to Implement the ADT Bag 50 Resizing an Array 50 A New Implementation of a Bag 53 The Pros and Cons of Using an Array to Implement the ADT Bag 55 Chapter 3 A Bag Implementation That Links Data 61 Linked Data 62 Forming a Chain by Adding to Its Beginning 63 A Linked Implementation of the ADT Bag 65 The Private Class Node 65 An Outline of the Class LinkedBag 66 Defining Some Core Methods 67 Testing the Core Methods 71 The Method getFrequencyOf 72 The Method contains 73 Removing an Item from a Linked Chain 74 The Methods remove and clear 75 A Class Node That Has Set and Get Methods 78 The Pros and Cons of Using a Chain to Implement the ADT Bag 81 Chapter 4 The Efficiency of Algorithms 87 Motivation 88 Measuring an Algorithms Efficiency 89 Counting Basic Operations 91 Best, Worst, and Average Cases 93 Big Oh Notation 94 The Complexities of Program Constructs 97 Picturing Efficiency 98 The Efficiency of Implementations of the ADT Bag 102 An Array-Based Implementation 102 A Linked Implementation 103 Comparing the Implementations 104 Chapter 5 Stacks 113 Specifications of the ADT Stack 114 Using a Stack to Process Algebraic Expressions 118 A Problem Solved: Checking for Balanced Delimiters in an Infix Algebraic Expression 119 A Problem Solved: Transforming an Infix Expression to a Postfix Expression 123 A Problem Solved: Evaluating Postfix Expressions 128 A Problem Solved: Evaluating Infix Expressions 130 The Program Stack 132 Java Class Library: The Class Stack 133 Chapter 6 Stack Implementations 141 A Linked Implementation 141 An Array-Based Implementation 145 A Vector-Based Implementation 149 Java Class Library: The Class Vector 150 Using a Vector to Implement the ADT Stack 150 Chapter 7 Recursion 157 What Is Recursion? 158 Tracing a Recursive Method 162 Recursive Methods That Return a Value 166 Recursively Processing an Array 168 Recursively Processing a Linked Chain 171 The Time Efficiency of Recursive Methods 172 The Time Efficiency of countDown 172 The Time Efficiency of Computing xn 174 A Simple Solution to a Difficult Problem 175 A Poor Solution to a Simple Problem 180 Tail Recursion 182 Indirect Recursion 184 Using a Stack Instead of Recursion 185 Chapter 8 An Introduction to Sorting 195 Organizing Java Methods That Sort an Array 196 Selection Sort 198 Iterative Selection Sort 199 Recursive Selection Sort 201 The Efficiency of Selection Sort 202 Insertion Sort 203 Iterative Insertion Sort 204 Recursive Insertion Sort 206 The Efficiency of Insertion Sort 208 Insertion Sort of a Chain of Linked Nodes 208 Shell Sort 211 The Java Code 213 The Efficiency of Shell Sort 214 Comparing the Algorithms 214 Chapter 9 Faster Sorting Methods 221 Merge Sort 222 Merging Arrays 222 Recursive Merge Sort 223 The Efficiency of Merge Sort 225 Iterative Merge Sort 227 Merge Sort in the Java Class Library 227 Quick Sort 228 The Efficiency of Quick Sort 228 Creating the Partition 229 Java Code for Quick Sort 232 Quick Sort in the Java Class Library 234 Radix Sort 235 Pseudocode for Radix Sort 236 The Efficiency of Radix Sort 237 Comparing the Algorithms 237 Chapter 10 Queues, Deques, and Priority Queues 245 The ADT Queue 246 A Problem Solved: Simulating a Waiting Line 250 A Problem Solved: Computing the Capital Gain in a Sale of Stock 256 Java Class Library: The Interface Queue 259 The ADT Deque 260 A Problem Solved: Computing the Capital Gain in a Sale of Stock 262 Java Class Library: The Interface Deque 263 Java Class Library: The Class ArrayDeque 264 The ADT Priority Queue 265 A Problem Solved: Tracking Your Assignments 266 Java Class Library: The Class PriorityQueue 268 Chapter 11 Queue, Deque, and Priority Queue Implementations 273 A Linked Implementation of a Queue 274 An Array-Based Implementation of a Queue 278 A Circular Array 278 A Circular Array with One Unused Location 281 A Vector-Based Implementation of a Queue 286 Circular Linked Implementations of a Queue 288 A Two-Part Circular Linked Chain 289 Java Class Library: The Class AbstractQueue 294 A Doubly Linked Implementation of a Deque 295 Possible Implementations of a Priority Queue 299 Chapter 12 Lists 305 Specifications for the ADT List 306 Using the ADT List 312 Java Class Library: The Interface List 316 Java Class Library: The Class ArrayList 316 Chapter 13 List Implementations That Use Arrays 321 Using an Array to Implement the ADT List 322 An Analogy 322 The Java Implementation 324 The Efficiency of Using an Array to Implement the ADT List 331 Using a Vector to Implement the ADT List 332 Chapter 14 A List Implementation That Links Data 339 Operations on a Chain of Linked Nodes 340 Adding a Node at Various Positions 340 Removing a Node from Various Positions 344 The Private Method getNodeAt 345 Beginning the Implementation 346 The Data Fields and Constructor 347 Adding to the End of the List 348 Adding at a Given Position Within the List 349 The Methods isEmpty and toArray 350 Testing the Core Methods 353 Continuing the Implementation 354 A Refined Implementation 356 The Tail Reference 357 The Efficiency of Using a Chain to Implement the ADT List 360 Java Class Library: The Class LinkedList 362 Chapter 15 Iterators 369 What Is an Iterator? 370 The Interface Iterator 371 Using the Interface Iterator 372 A Separate Class Iterator 377 An Inner Class Iterator 381 A Linked Implementation 381 An Array-Based Implementation 385 Why Are Iterator Methods in Their Own Class? 388 The Interface ListIterator 390 Using the Interface ListIterator 393 An Array-Based Implementation of the Interface ListIterator 395 The Inner Class 397 Java Class Library: The Interface Iterable 402 Iterable and for-each loops 403 The Interface List Revisited 403 Chapter 16 Sorted Lists 411 Specifications for the ADT Sorted List 412 Using the ADT Sorted List 415 A Linked Implementation 416 The Method add 417 The Efficiency of the Linked Implementation 424 An Implementation That Uses the ADT List 424 Efficiency Issues 427 Chapter 17 Inheritance and Lists 433 Using Inheritance to Implement a Sorted List 434 Designing a Base Class 436 Creating an Abstract Base Class 441 An Efficient Implementation of a Sorted List 443 The Method add 443 Chapter 18 Searching 447 The Problem 448 Searching an Unsorted Array 448 An Iterative Sequential Search of an Unsorted Array 449 A Recursive Sequential Search of an Unsorted Array 450 The Efficiency of a Sequential Search of an Array 452 Searching a Sorted Array 452 A Sequential Search of a Sorted Array 452 A Binary Search of a Sorted Array 453 Java Class Library: The Method binarySearch 458 The Efficiency of a Binary Search of an Array 458 Searching an Unsorted Chain 460 An Iterative Sequential Search of an Unsorted Chain 460