Problem Solving with Data Structures, First Edition is not a traditional data structures textbook that teaches concepts in an abstract, and often dry, context that focuses on data structures using numbers. Instead, this book takes a more creative approach that uses media and simulations (specifically, trees and linked lists of images and music), to make concepts more concrete, more relatable, and therefore much more motivating for students. This book is appropriate for both majors and non-majors. It provides an introduction to object-oriented programming in Java, arrays, linked lists, trees, stacks, queues, lists, maps, and heaps. It also covers an existing simulation package (Greenfoot) and how to create continuous and discrete event simulations.
Contents iii I Introduction to Java: Object-Oriented Programming for Modeling a World 1 Objects for Modeling a World 1.1 Making Representations of a World 1.2 Why Java? 2 Introduction to Java 2.1 Whats Java about? 2.2 Basic (Syntax) Rules of Java 2.3 Using Java to Model the World 2.4 Manipulating Pictures in Java 2.5 Exploring Sound in Java 2.6 Exploring Music in Java 3 Methods in Java: Manipulating Pictures 3.1 Reviewing Java Basics 3.2 Java is about Classes and Methods 3.3 Methods that return something: Compositing images 3.4 Creating classes that do something 4 Objects as Agents: Manipulating Turtles 4.1 Turtles: An Early Computational Object 4.2 Drawing with Turtles 4.3 Creating animations with turtles and frames 4.4 Making a Slow Moving Turtle with sleep and exceptions 5 Arrays: A Static Data Structure for Sounds 5.1 Manipulating Sampled Sounds 5.2 Inserting and Deleting in an Array 5.3 How Slow Does It Get? II Introducing Linked Lists 6 Structuring Music using Linked Lists 6.1 JMusic and Imports 6.2 Making a Simple Song Object 6.3 Making a Song Something to Explore as a Linked List 7 Structuring Images using Linked Lists 7.1 Simple arrays of pictures 7.2 Listing the Pictures, Left-to-Right 7.3 Listing the Pictures, Layering 7.4 Reversing a List 7.5 Animation 7.6 Lists with Two Kinds of Elements III Trees: Hierarchical Structures for Media 8 Trees of Images 8.1 Representing scenes with trees 8.2 Our First Scene Graph: Attack of the Killer Wolvies 8.3 The Classes in the SceneGraph 8.4 Building a scene graph 8.5 Implementing the Scene Graph 8.6 Exercises 9 Lists and Trees for Structuring Sounds 9.1 Composing with Sampled Sounds and Linked Lists: Recursive Traversals 9.2 Using Trees to Structure Sampled Sounds . 10 Generalizing Lists and Trees 10.1 Refactoring a General Linked List Node Class 10.2 Making a New Kind of List 10.3 The Uses and Characteristics of Arrays, Lists, and Trees 10.4 Binary Search Trees: Trees that are fast to search 11 Abstract Data Types: Separating the Meaning from the Implementation 11.1 Introducing Stacks 11.2 Introducing Queues 11.3 Using an ArrayList 11.4 Using a map ADT 12 Circular Linked Lists and Graphs: Lists and Trees That Loop 12.1 Making Sprite Animation with Circular Linked Lists 12.2 Generalizing a Circular Linked List 12.3 Graphs: Trees with Loops 13 User Interface Structures 13.1 A Toolkit for Building User Interfaces 13.2 Rendering of User Interfaces 13.3Creating an Interactive User Interface 13.4 Running from the Command Line IV Simulations: Problem Solving with Data Structures 14 Using an Existing Simulation Package 14.1 Introducing Simulations 14.2 Overview of Greenfoot 14.3 Greenfoot Basics 14.4 Creating new classes 14.5 Breakout 15 Introducing UML and Continuous Simulations 15.1 Our First Model and Simulation: Wolves and Deer 15.2 Modeling in Objects 15.3 Implementing the Simulation Class 15.4 Implementing a Wolf 15.5 Implementing Deer 15.6 Implementing AgentNode 15.7 Extending the Simulation 16 Abstracting Simulations: Creating a Simulation Package 16.1 Creating a Generalized Simulation Package 16.2 Re-Making the Wolves and Deer with our Simulation Package 16.3 Making a Disease Propagation Simulation 16.4 Walking through the Simulation Package 16.5 Finally! Making Wildebeests and Villagers 17 Discrete Event Simulation 17.1 Describing a Marketplace 17.2 Differences between Continuous and Discrete Event Simulations 17.3 Different Kinds of Random 17.4 Ordering Events by Time 17.5 Implementing a Discrete Event Simulation 17.6 The Final Word: The Thin Line between Structure and Behavior Index