• Choose a category
• All
• Classic-Fiction

Kyle Loudon

Editor

Andy Oram

Copyright © 2009 O'Reilly Media, Inc.

O'Reilly Media

* * *

A Note Regarding Supplemental Files

Supplemental files and examples for this book can be found at http://examples.oreilly.com/9781565924536/. Please use a standard desktop web browser to access these files, as they may not be accessible from all ereader devices.

All code files or examples referenced in the book will be available online. For physical books that ship with an accompanying disc, whenever possible, we’ve posted all CD/DVD content. Note that while we provide as much of the media content as we are able via free download, we are sometimes limited by licensing restrictions. Please direct any questions or concerns to booktech@oreilly.com.

Preface

When I first thought about writing this book, I immediately thought of O'Reilly & Associates to publish it. They were the first publisher I contacted, and the one I most wanted to work with because of their tradition of books covering "just the facts." This approach is not what one normally thinks of in connection with books on data structures and algorithms. When one studies data structures and algorithms, normally there is a fair amount of time spent on proving their correctness rigorously. Consequently, many books on this subject have an academic feel about them, and real details such as implementation and application are left to be resolved elsewhere. This book covers how and why certain data structures and algorithms work, real applications that use them (including many examples), and their implementation. Mathematical rigor appears only to the extent necessary in explanations.

Naturally, I was very happy that O'Reilly & Associates saw value in a book that covered this aspect of the subject. This preface contains some of the reasons I think you will find this book valuable as well. It also covers certain aspects of the code in the book, defines a few conventions, and gratefully acknowledges the people who played a part in the book's creation.

Organization

This book is divided into three parts. The first part consists of introductory material that is useful when working in the rest of the book. The second part presents a number of data structures considered fundamental in the field of computer science. The third part presents an assortment of algorithms for solving common problems. Each of these parts is described in more detail in the following sections, including a summary of the chapters each part contains.

Part I

Part I contains Chapter 1 through Chapter 4. Chapter 1, introduces the concepts of data structures and algorithms and presents reasons for using them. It also presents a few topics in software engineering, which are applied throughout the rest of the book. Chapter 2 discusses a number of topics on pointers. Pointers appear a great deal in this book, so this chapter serves as a refresher on the subject. Chapter 3 covers recursion, a popular technique used with many data structures and algorithms. Chapter 4 presents the analysis of algorithms. The techniques in this chapter are used to analyze algorithms throughout the book.

Part II

Part II contains Chapter 5 through Chapter 11. Chapter 5 presents various forms of linked lists, including singly-linked lists, doubly-linked lists, and circular lists. Chapter 6 presents stacks and queues, data structures for sorting and returning data on a last-in, first-out and first-in, first-out order respectively. Chapter 7 presents sets and the fundamental mathematics describing sets. Chapter 8 presents chained and open-addressed hash tables, including material on how to select a good hash function and how to resolve collisions. Chapter 9 presents binary and AVL trees. Chapter 9 also discusses various methods of tree traversal. Chapter 10 presents heaps and priority queues, data structures that help to quickly determine the largest or smallest element in a set of data. Chapter 11 presents graphs and two fundamental algorithms from which many graph algorithms are