Grokking data structures

Grokking Data structures cover
Grokking Data Structures
An illustrated guide for programmers and other curious people
by La Vivien

ISBN: 9781633438040



Look inside

Grokking Data chapter1 Grokking Data structures chapter2 Grokking Data structures chapter3 Grokking Data structures chapter4

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 apart 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.

    organize cards

    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.

    dogs play cards

    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.

    math is fun

    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.

    Junior programmers

    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.

    Big o notations

    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.

    time measurment

    On the contrary, the space complexity doesn't change much once you store data in data structures, except you use a lot of auxiliary spaces in your code. Using unnecessary extra spaces or use memory improperly can hurt space efficiency. Through analyzing the space complexity, you will find room for improvement.

    space measurment


    Comments are closed