Grokking Data Structures
An illustrated guide for programmers and other curious people
by La Vivien
ISBN: 9781633438040
Look inside
Behind story
In October 2022, I signed a contract with Manning Publisher to write the book Grokking Data Structures. For various reasons, the contract fell through in early 2023. By that time, I had finished four chapters.
This is a fun project that I would like to cross the finish line. I’m going to finish the book and self-publish it. So that people will have fun learning data structures as I had.
The free downloads of Chapters 1-4 are available below. If you like it, please support me by clicking the Donate button. Your $1 contribution is truly invaluable to me. I promise to send you a free copy when I finish the book. Thank you!
Free download
Sign up here to get a download of Chapters 1-4.
The code in the book is in Python.
Get code at GitHub
Table of contents
Chapter 1: Introduction
Chapter 2: Arrays
Chapter 3: Linked Lists
Chapter 4: Stacks and Queues
Chapter 5: Binary trees
Chapter 6: Heaps and Priority Queues
Chapter 7: Hash tables
Chapter 8: Graphs
Chapter 9: Tries
Chapter 10: The fun has just begun
Excerpt
What is a data structure?
Data structures refer to the ways how data are organized and manipulated so that data can be stored and retrieved efficiently. When working with data structures, you focus on how they relate to one another in an organized manner.
When do you need data structures?
Ben is collecting trading cards called 'Eniverse.' Each card has a name and an ID number. Each card has a Category and Hit Power used for a trading card game. Ben organizes his cards in different decks by their categories. He sorts the cards by their Hit Powers.
Ben plays the trading card game with his friends. They compete using cards in different categories. Anyone who has a higher aggregated score is the winner.
Before coming to a game, Ben grabs the cards with high Hit-Powers from each category. On the other hand, his friend Billy never organizes his cards. He brings a pile of random cards to the game. So Ben always wins.
Organizing data is the same as organizing trading cards. For Ben, it is a matter of win or lose. For a software developer, the system simply would not work without organizing data one way or another.
Why study this book?
Data structures are a key concept in computer science and are introduced to students as part of a high school or college computer science curriculum. With many textbooks about data structures available, why would you want to read this book?
A picture book
Data structures are abstract. A beginner cannot 'see' the actions of data structures clearly in their head. When you draw data structures on paper, the concepts are easier to visualize and the solutions will emerge.
Do you remember when you started to learn math in elementary school? Math was intimidating. To help you study, your teacher introduced illustrated math books. They were fun to read and helped you understand quickly.
This book is just like that. It is not a typical textbook with pages and pages of text and code. Instead, this book provides vivid pictures of data structures and helps you learn in a fun way.
This book's audience
This book is for students who have a basic understanding of programming. You probably have taken your first programming course. You know how to enter code into a computer and to compile the code. You know the concepts of variables, flow controls, functions, and classes. This book will take you to the next level of programming.
This book is also for new graduates and junior programmers. When you work on a project, sometimes you debate what data structures to use and how to improve the performance of your code. Other times, you want to refresh your memory and prepare for a coding interview. This book keeps the explanations short so you can find the answers quickly.
Takeaway
In this book, I teach the basic concepts and techniques needed to work with data structures. More importantly, the book helps you to build the mindset to seek elegant approaches.
After you read the book, you will know each data structure's pros and cons. You can write the code to implement your own data structures. You can solve problems efficiently by choosing the right data structures.
Big O Notations
'What gets measured gets done.' Big O notation is a tool to measure the efficiency of the code you write.
Big O notation is a way of expressing the performance or complexity of a software program. A program can be a block of code, a function or a method, an algorithm, or a system. Big O notation describes how the running time or space grows as the size of the input data increases.
Examples of major Big O notations
Here are some of the major Big O notations and their use cases. The list is in order from best to worst, where O(1) is the best and O(n2) is the worst.
• O(1) – a constant complexity. Add an item in an array.
• O(logn) – a logarithmic complexity. Add an item in a balanced binary tree.
• O(n) – a linear complexity. Print all elements in an array.
• O(nlogn) – a nested linear and logarithmic complexity. Add n elements in a priority queue.
• O(n2) – a quadratic complexity. Print all elements in a two-dimensional array.
Time versus space
Big O notations are used to measure both running time and memory space. When you program, you hear people talk about time complexity more often than space complexity. That is because runtime varies from operation to operation within the same data structures.
