Early in my career I was handed one textbook: Evangel Quiwa's Data Structures. It is the only book on the subject I ever took seriously. I studied it chapter by chapter and kept written notes, one session of his to one set of mine. The book, and later these notes, got me through technical interviews in the United States and in the Netherlands.
One idea holds these notes together: a program gets long when the steps have to hunt for the data. It stays short when the data already sits where the steps expect it. So there are two jobs: decide how the data sits in memory, then write the steps that use it.
Fifteen sessions follow that idea through stacks, queues, trees, heaps, graphs, shortest paths, linked lists, searching, binary search trees, and hash tables. Each session starts from a drawing, walks it with real numbers, and ends with a check you can do on paper. Every step is written in Python, with 35 diagrams and 22 programs you can run.
What you'll learn
- Tell a data type, an abstract data type, and a data structure apart
- Read and run Easy, the teaching notation, and write the same step in Python
- Count a procedure with the bounds that matter, and read O and Theta without mixing them
- Build a stack, a queue, and a deque, and use them for brackets, postfix, and a topological sort
- Walk a binary tree four ways, and without a stack three more: threads, link inversion, and exclusive-or links
- Keep a heap, a forest, and a set of equivalence classes, and say what each operation costs
- Walk a graph depth-first and breadth-first, and use the walks for cycles, components, and articulation points
- Find a cheapest spanning tree and a shortest path, and know when each algorithm applies
- Store a sequence four ways, then use the chain for a polynomial, a long integer, a memory pool, and a qualifying list
- Search a static table, a binary search tree, and a hash table, and say what each collision policy costs
