Quick Data Structures (David Matuszek) (Z-Library)

Quick Data Structures If you want to upgrade your programming skills, the most impor‑ tant thing you need is a solid understanding of fundamental data structures. The proper choice of data structures distinguishes excellent programmers from merely competent ones. As an experienced programmer, you use data structures—at least arrays—all the time. However, you may not be familiar with hash tables, trees and binary trees, priority queues, directed and undi‑ rected graphs, and other data structures at your disposal. A good choice of data structures will simplify your job, not complicate it. Your code will be not only faster but also easier to understand and debug. There is no downside to using the right data structures for the job. This book • Provides an understanding of the fundamental building blocks of data structures • Describes the construction and use of all common data structures • Explains the simple math required for selecting efficient data structures • Equips you with everything you need to choose data struc‑ tures or devise appropriate new ones

Quick Programming Series Most programming books are either textbooks aimed at begin‑ ners, or tomes intended to provide everything the programmer needs to know. Books in this series fulfil an important niche by offering a bridge for programmers who need a quick entry into a language, and do not need to know everything about it yet. PUBLISHED BOOKS IN THE SERIES Quick Data Structures Quick Java Quick Functional Programming Quick JavaScript Quick Recursion Quick Python 3

Quick Data Structures David Matuszek

Designed cover image: 100covers.com First edition published 2026 by CRC Press 2385 NW Executive Center Drive, Suite 320, Boca Raton FL 33431 and by CRC Press 4 Park Square, Milton Park, Abingdon, Oxon, OX14 4RN CRC Press is an imprint of Taylor & Francis Group, LLC © 2026 David Matuszek Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, access www.copyright.com or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978‑750‑8400. For works that are not available on CCC please contact mpkbookspermissions@tandf.co.uk Trademark notice: Product or corporate names may be trademarks or registered trademarks and are used only for identification and explanation without intent to infringe. ISBN: 978‑1‑041‑03813‑9 (hbk) ISBN: 978‑1‑041‑03810‑8 (pbk) ISBN: 978‑1‑003‑62550‑6 (ebk) DOI: 10.1201/9781003625506 Typeset in Minion by codeMantra

To all my students past, present, and future

vii Contents Preface, xii Author, xiv Where’s the Code?, xvi Chapter 1 ◾ Building Blocks 1 1.1 Pointers and References 2 1.2 Arrays 3 1.3 String Arrays 4 Chapter 2 ◾ Essential Math 5 2.1 The Importance of Efficiency 6 2.2 Analysis of Algorithms 7 2.3 Constant Time 8 2.4 Linear Time 9 2.5 Quadratic Time 10 2.6 Bubble Sort 10 2.7 Characteristic Operations 12 2.8 Insertion Sort 13 2.9 Selection Sort 14 2.10 Exponents and Logarithms 15 2.11 Binary Search 16

viii ◾ Contents 2.12 Quicksort 18 2.13 Analyzing Quicksort 21 2.14 Merge Sort 23 2.15 Even Faster Sorts 25 2.16 Big‑O Notation 26 2.17 Big‑O and Friends 28 2.18 Exponential Time 29 Chapter 3 ◾ Hash Tables and Hash Maps I 31 3.1 Basic Hash Tables 32 3.2 Hash Functions 34 3.3 Hash Table Notes 36 3.4 Hash Maps 37 3.5 Abstract Data Types 38 3.5.1 ADT as a Contract 39 Chapter 4 ◾ Recursion 41 4.1 Recursive Data Structures 41 4.2 Recursive Functions 43 4.3 Four Rules 44 4.3.1 Rule 1: Do Base Cases First 45 4.3.2 Rule 2: Recur Only with Simpler Cases 45 4.3.3 Rule 3: Don’t Use Non‑Local Variables 46 4.3.4 Rule 4: Don’t Look Down 47 4.4 Examples of Recursion 47

Contents ◾ ix Chapter 5 ◾ Stacks, Queues, and Deques 50 5.1 Stacks 50 5.1.1 Example: Balancing Brackets 52 5.1.2 Example: Expression Evaluation 52 5.1.3 Example: Stack Frames 53 5.2 Queues 54 5.3 Deques 56 Chapter 6 ◾ Linked Lists 57 6.1 Singly Linked Lists 57 6.2 Stacks as Singly Linked Lists 60 6.3 Implementation Notes 61 6.4 Lists in Functional Programming 63 6.5 Doubly Linked Lists 64 6.6 Circular Linked Lists 64 6.7 Python “Lists” 65 6.8 Hash Tables and Hash Maps II 66 Chapter 7 ◾ Binary Trees 68 7.1 Binary Tree Traversals 71 7.2 Binary Search Trees 72 7.3 Tree Balancing 73 7.4 Heapsort 75 7.4.1 Phase 1: Heapifying a Binary Tree 76 7.4.2 Phase 2: Removing the Root and Reheaping 77 7.4.3 Phase 3: Mapping a Binary Tree into an Array 78

x ◾ Contents 7.4.4 The Complete Heapsort Algorithm 79 7.4.5 Analysis 80 7.5 Huffman Encoding 81 Chapter 8 ◾ Priority Queues 83 8.1 Priority Queue Implementations 84 Chapter 9 ◾ Heaps 86 9.1 Heap Implementation 87 9.2 Deallocation Problems 89 9.3 Garbage Collection 90 9.3.1 Reference Counting 90 9.3.2 Mark and Sweep 91 Chapter 10 ◾ Trees 92 10.1 Applications of Trees 93 10.1.1 File Systems 94 10.1.2 Family Trees 94 10.1.3 Game Trees 95 10.1.4 Expressions 96 10.2 Tree Searching 97 10.2.1 Depth‑First Searching 98 10.2.2 Breadth‑First Searching 99 10.2.3 Depth‑First Iterative Deepening 100 10.2.4 State‑Space Searches 102 10.2.5 Pruning 105 10.2.6 Alpha–Beta Searching 106 10.3 Tries 109

Contents ◾ xi Chapter 11 ◾ Graphs 112 11.1 Graph Applications 114 11.2 Adjacency Matrix Representations 115 11.3 Representation by Sets 116 11.4 Searching a Graph 117 11.5 Sparse Arrays 119 11.6 Dijkstra’s Algorithm 121 11.7 Spanning Trees 122 11.8 Mazes 124 11.9 Heuristic Searching 126 11.9.1 Solving the Fifteen Puzzle 127 11.9.2 The A* Algorithm 128 11.9.3 IDA* 129 Chapter 12 ◾ Hypergraphs 131 12.1 Plexes 132 Chapter 13 ◾ Algorithm Types 135 13.1 Simple Recursive Algorithms 135 13.2 Backtracking Algorithms 135 13.2.1 Virtual Trees 137 13.3 Divide and Conquer Algorithms 138 13.4 Greedy Algorithms 139 13.5 Dynamic Programming Algorithms 139 13.6 Brute Force Algorithms 143 13.7 Randomized Algorithms 144 Afterword, 145 Index, 147

xii Preface Many years ago, a friend came to me with a problem. Back then, you typed your program on punched cards and put them in a tray along with other programs to be run. Some hours later, you would get the printed results. My friend’s problem was that his program was taking more than 20 minutes to run on the Control Data 6600, which (in those days) was the world’s fastest computer. According to the Computation Center rules, any program that took more than 20 minutes would be stopped and not run again until the weekend when the com‑ puter was less busy. My friend asked me if I could speed up his program. The program was doing a lot of table look‑ups, using an ordi‑ nary array. I replaced the array with a hash table–a change which reduced the running time to under 20 seconds. My friend didn’t fully trust my work because, as he later told me, he spent the entire weekend hand‑checking the results. Times have changed, and today’s computers are orders of mag‑ nitude faster than the “supercomputers” of yesteryear. That same program would, today, run in a few milliseconds.

Preface ◾ xiii Today’s computers are so fast and have so much memory that, for most programs, it doesn’t make sense to worry about efficiency. However, there are important exceptions: video games, popular websites, deep learning, weather modeling, and more. Besides, why struggle with a poor choice of data structures when there might be one perfectly suited to your needs?

xiv Author I’m David Matuszek, known to most of my students as “Dr. Dave.” I wrote my first program on punched cards in 1963 and immedi‑ ately got hooked. I taught my first computer classes in 1970 as a graduate student in computer science at the University of Texas in Austin. I eventually earned a PhD there, and I’ve been teaching ever since. Admittedly, I spent over a dozen years in industry, but even then I taught as an adjunct for Villanova University. I finally left the industry and joined the Villanova faculty full time for a few years before moving to the University of Pennsylvania, where I directed a master’s program (MCIT, Master’s in Computer and Information Technology) for students transitioning into com‑ puter science from other disciplines. Throughout my career, my main interests have been in artificial intelligence (AI) and programming languages. I’ve used a lot of programming languages. I retired in 2017, but I can’t stop teaching, so I’m writing a series of “quick start” books on programming and programming lan‑ guages. I’ve also written three science fiction novels—Ice Jockey,

Author ◾ xv All True Value, and A Prophet in Paradise—and I expect to write more. Check them out! And, hey, if you’re a former student, drop me a note. I’d love to hear from you! david.matuszek@gmail.com

xvi Where’s the Code? This isn’t a recipe book. If you want the code for, say, a merge sort, you can do a web search and find code for a merge sort in any of the couple dozen most common languages. Instead, the goal of this book is to explain (for example) how a merge sort works, and when and why you might want to use one. Once you understand that, you can write your own or grab one of the many published versions. Code isn’t always the best way to explain an algorithm or data structure—but sometimes it is. In such cases, the code should be as readable as possible. It’s generally agreed that Python is the most readable language, but every language has glitches. Python’s for loop is for i in range(0, n): # do something and it isn’t necessarily obvious to a non‑Python programmer that this means: for i from 0 up to but not including n { # do something }

Where’s the Code? ◾ xvii Similarly, Python has dictionaries, “lists,” and sets, which we will try to avoid. Consequently, the code in this book is “Python‑like” but, in the interest of making code as readable as possible for everyone, not necessarily “real” Python. There is one feature we retain from Python. Good programming style demands that code be indented properly, and in Python, this is a requirement, not just a style rule. In this book, indentation is used to indicate code controlled by an if or while statement, mak‑ ing braces unnecessary.

1DOI: 10.1201/9781003625506‑1 C h a p t e r 1 Building Blocks A data structure is a way of organizing information so that it can be retrieved and updated quickly and easily. Any data structure can be created from just three basic compo‑ nents: arrays, nodes, and pointers. A node is a (generally small) collection of named fields that hold data values. Nodes may be of varied types and sizes, may be arbi‑ trarily complex, and often contain links to other nodes. For exam‑ ple, a node used to represent a customer may have a field named customerId to hold a unique integer, a field named email to hold a link to an email address represented as a string, and a field named orderHistory that holds a link to another node type whose values represent an order history. In object‑oriented languages, a node is almost always represented by an object, but any method of associating the various pieces of information can be made to work. A pointer (also called a reference or a link) provides access to a data value that is located elsewhere in memory. Originally, a