Allen B. Downey - Think Data Structures: Algorithms and Information Retrieval in Java

by Allen B. Downey

Copyright 2017 Allen Downey. All rights reserved.

Printed in the United States of America.

Published by OReilly Media, Inc. , 1005 Gravenstein Highway North, Sebastopol, CA 95472.

OReilly books may be purchased for educational, business, or sales promotional use. Online editions are also available for most titles (http://oreilly.com/safari). For more information, contact our corporate/institutional sales department: 800-998-9938 or corporate@oreilly.com .

• Editors: Nan Barber and Brian Foster
• Production Editor: Kristen Brown
• Copyeditor: Charles Roumeliotis
• Proofreader: Amanda Kersey
• Indexer: Allen B. Downey
• Interior Designer: David Futato
• Cover Designer: Karen Montgomery
• Illustrator: Rebecca Demarest

• July 2017: First Edition

The OReilly logo is a registered trademark of OReilly Media, Inc. Think Data Structures, the cover image, and related trade dress are trademarks of OReilly Media, Inc.

While the publisher and the author have used good faith efforts to ensure that the information and instructions contained in this work are accurate, the publisher and the author disclaim all responsibility for errors or omissions, including without limitation responsibility for damages resulting from the use of or reliance on this work. Use of the information and instructions contained in this work is at your own risk. If any code samples or other technology this work contains or describes is subject to open source licenses or the intellectual property rights of others, it is your responsibility to ensure that your use thereof complies with such licenses and/or rights.

Think Data Structures is available under the Creative Commons Attribution-NonCommercial 3.0 Unported License. The author maintains an online version at http://greenteapress.com/wp/think-data-structures/.

978-1-491-97239-7

[LSI]

Data structures and algorithms are among the most important inventions of the last 50 years, and they are fundamental tools software engineers need to know. But in my opinion, most of the books on these topics are too theoretical, too big, and too bottom up:

Finally, some books present this material out of context and without motivation: its just one damn data structure after another! I try to liven it up by organizing the topics around an application web search that uses data structures extensively, and is an interesting and important topic in its own right.

This application motivates some topics that are not usually covered in an introductory data structures class, including persistent data structures with Redis.

I have made difficult decisions about what to leave out, but I have made some compromises. I include a few topics that most readers will never use, but that they might be expected to know, possibly in a technical interview. For these topics, I present both the conventional wisdom as well as my reasons to be skeptical.

This book also presents basic aspects of software engineering practice, including version control and unit testing. Most chapters include an exercise that allows readers to apply what they have learned. Each exercise provides automated tests that check the solution. And for most exercises, I present my solution at the beginning of the next chapter.