Prerequisites

This book is intended for college students in computer science and related fields, as well as professional software engineers, people training in software engineering, and people preparing for technical interviews.

Before you start this book, you should know Java pretty well; in particular, you should know how to define a new class that extends an existing class or implements an interface. If your Java is rusty, here are two books you might start with:

• Downey and Mayfield, Think Java (O’Reilly Media, 2016), which is intended for people who have never programmed before.
• Sierra and Bates, Head First Java (O’Reilly Media, 2005), which is appropriate for people who already know another programming language.

You should also be familiar with type parameters and generic types. For example, you should know how create an object with a type parameter, like ArrayList<Integer>. If not, you can read about type parameters at thinkdast.com/types.

You should be familiar with the Java Collections Framework (JCF), which you can read about at thinkdast.com/collections. In particular, you should know about the List interface and the classes ArrayList and LinkedList.

Ideally you should be familiar with Apache Ant, which is an automated build tool for Java. You can read more about Ant at thinkdast.com/anttut.

And you should be familiar with JUnit, which is a unit testing framework for Java. You can read more about it at thinkdast.com/junit.

Working with the code

The code for this book is in a Git repository at thinkdast.com/repo.

Git is a “version control system” that allows you to keep track of the files that make up a project. A collection of files under Git’s control is called a “repository”.

GitHub is a hosting service that provides storage for Git repositories and a convenient web interface. It provides several ways to work with the code:

• You can create a copy of the repository on GitHub by pressing the Fork button. If you don’t already have a GitHub account, you’ll need to create one. After forking, you’ll have your own repository on GitHub that you can use to keep track of code you write. Then you can “clone” the repository, which downloads a copy of the files to your computer.
• Alternatively, you could clone the repository without forking. If you choose this option, you don’t need a GitHub account, but you won’t be able to save your changes on GitHub.
• If you don’t want to use Git at all, you can download the code in a ZIP archive using the Download button on the GitHub page, or this link: thinkdast.com/zip.

After you clone the repository or unzip the ZIP file, you should have a directory called ThinkDataStructures with a subdirectory called code.

The examples in this book were developed and tested using Java SE Development Kit 7. If you are using an older version, some examples will not work. If you are using a more recent version, they should all work.

Contributors and Attributions

This book is an adapted version of a curriculum I wrote for the Flatiron School in New York City, which offers a variety of online classes related to programming and web development. They offer a class based on this material, which provides an online development environment, help from instructors and other students, and a certificate of completion. You can find more information at http://flatironschool.com.

• At the Flatiron School, Joe Burgess, Ann John, and Charles Pletcher provided guidance, suggestions, and corrections from the initial specification all the way through implementation and testing. Thank you all!
• I am very grateful to my technical reviewers, Barry Whitman, Patrick White, and Chris Mayfield, who made many helpful suggestions and caught many errors. Of course, any remaining errors are my fault, not theirs!
• Thanks to the instructors and students in Data Structures and Algorithms at Olin College, who read this book and provided useful feedback.

If you have comments or ideas about the text, please send them to: [e-mail].