Data Structures
Choosing a data structure by the cost of its operations, and implementing arrays, linked lists, stacks, queues, hash tables, trees, heaps, tries and graphs in Python, Java and TypeScript.
Measuring Cost
The vocabulary and the counting every data structure is compared with: Big O and complexity analysis.
Big O notation: how to describe the way a data structure operation's cost grows with its input, and why constants and smaller terms drop out.
Beginner to Intermediate8 cards · 5 qnot started
Analysing complexity: reading the time and space a function needs from its loops, its recursion and the built-in calls hidden inside them.
Beginner to Intermediate8 cards · 5 qnot started
Sequences and Lookup
Data structures that hold items in a line or find them by key: arrays, linked lists, stacks, queues and hash tables.
Arrays and strings: why reading by index is instant, why inserting in the middle is not, and how a dynamic array grows without slowing every append.
Beginner to Intermediate9 cards · 4 qnot started
Linked lists: nodes joined by references, so inserting and deleting is a rewire instead of a shift, at the price of reading by position.
Beginner to Intermediate9 cards · 4 qnot started
Stacks and queues: the two data structures defined by the order items leave in, last in first out or first in first out, and how to build each cheaply.
Beginner to Intermediate9 cards · 4 qnot started
Hash tables: the data structure that turns a key into an array index to find values in expected constant time, and what collisions, growth and bad keys do to it.
Beginner to Intermediate10 cards · 6 qnot started
Recursion and Trees
Recursion, and the trees it walks: binary trees, binary search trees, heaps and tries.
Recursion: writing a function that calls itself on a smaller input, tracing it through the call stack, and replacing it with a loop when it runs too deep.
Beginner to Intermediate8 cards · 5 qnot started
Binary Trees: naming the parts of a tree, traversing it in four orders, counting height in edges, and writing functions that combine two subtrees' answers.
Beginner to Intermediate8 cards · 4 qnot started
Binary Search Trees: keeping keys in order so that search, insert and delete each follow one path, and why insertion order decides the cost.
Beginner to Advanced9 cards · 6 qnot started
Heaps: a complete binary tree stored in an array that always gives the smallest or largest item first, the data structure behind every priority queue.
Beginner to Intermediate9 cards · 5 qnot started
Tries: a tree with one node per letter, which answers whether any stored word starts with a prefix in time that ignores how many words there are.
Beginner to Intermediate7 cards · 3 qnot started
Graphs
Storing vertices and edges, and tracking which vertices are connected.
Graph representations: storing vertices and edges as an adjacency list or an adjacency matrix, and choosing between them by how many edges there are.
Beginner to Intermediate8 cards · 4 qnot started
Union-find in data structures: tracking which items share a group with a parent array, merging groups, and counting components and detecting cycles in a graph.
Intermediate to Advanced7 cards · 3 qnot started
Choosing and Combining
Picking the data structure a problem needs, and joining two when no single one is enough.
Choosing a data structure: listing a program's operations and their frequency, picking the structure that makes them cheap, and the built-ins Python, Java and TypeScript provide.
Intermediate to Advanced7 cards · 4 qnot started
Combining data structures: an LRU cache from a hash map and a doubly linked list, a set with O(1) random picks from an array and a map, and keeping both parts in step.
Intermediate6 cards · 3 qnot started