Data Structures tutorial

Learn how to store and organize data with arrays, stacks, queues, trees and graphs.

Course contents

Introduction to Data Structures — What a data structure is, why programs need one, how data structures are grouped, what an ADT is, and the basic operations every structure supports.

Linked Lists — Why linked lists exist, how they differ from arrays, how nodes and references work, the singly, doubly and circular kinds, and the six list operations.
Stacks — What a stack is, the LIFO rule, push, pop and peek, how to build a stack with an array or a linked list, and how the call stack runs functions.
Queues — What a queue is, the FIFO rule, enqueue, dequeue and peek, circular queues, deques, priority queues, and the common ways to build a queue.
Hash Tables — How hashing works, hash functions and buckets, hash maps and hash sets, collision handling with chaining and probing, load factor and rehashing.

Tree Fundamentals — What a tree is, why we need trees, tree terminology, height and depth, degree, binary and n-ary trees, tree classifications, and linked and array representation.
Tree Traversals — What tree traversal is, depth-first and breadth-first search, and the preorder, inorder, postorder and level order visiting orders.
Binary Search Trees — The BST property and structure, node relationships, search, insert and delete, and finding the minimum, maximum, successor and predecessor nodes.
Balanced Trees — Why trees need balancing, tree rotations, AVL trees, red-black trees, B-trees, B+ trees and splay trees.
Tree Structures — Special-purpose trees: expression trees for evaluation and parsing, single and double threaded trees, winner and loser tournament trees, and decision trees.
Tries — What a trie is, its structure, prefix trees, radix trees, compressed tries and ternary search trees.

Heaps — What a heap is, the heap property, complete binary trees, binary, min and max heaps, insert, extract, peek and build, and binomial and Fibonacci heaps.

Graph Fundamentals — What a graph is, vertices, edges, self loops, parallel edges and degree, graph properties, undirected, weighted and unweighted graphs, paths, cycles and components.
Graph Representations — Four ways to store a graph: adjacency list, adjacency matrix, edge list and incidence matrix, and how sparse and dense graphs decide which one to use.
Directed Graphs — Directed graphs and one-way edges, sources, sinks and reachability, in-degree and out-degree, DAGs with topological order, and finding cycles.
Disjoint Sets — Disjoint sets (union-find): sets as trees, the parent array, find and union, path compression and union by rank, with a step-by-step simulation.
Graph Structures — Special kinds of graphs: multigraphs, pseudographs, bipartite graphs, complete graphs, planar graphs and network graphs, with a test for each one.

Segment Trees — Segment trees for fast range sums: structure and storage, range queries, point updates, min trees, and lazy propagation for range updates.
Fenwick Trees — Fenwick trees (binary indexed trees): lowbit, which positions each cell covers, prefix sum queries, point updates, and two ways to build one.
Advanced Data Structures — A tour of special structures: sparse tables, interval trees, skip lists, Bloom filters, ropes, k-d trees and quad trees, each with a runnable example.