Graphs and Linked Structures

This course covers data built from nodes and references rather than contiguous memory: linked lists, trees, and graphs, along with the traversals that operate on them. As in Arrays and Hashing, the goal for each is what it does, what it costs, and why.

This course assumes the data structures from Arrays and Hashing and some CS background, and is not intended as a substitute for general programming knowledge. It aims to be frugal with your time, acting as a crash course and refresher for node-based structures and their traversals, and a repository you can look back on to remind yourself of the most immediately relevant details and intuitions for using them.

What it covers

• Linked lists: nodes joined by pointers, and the O(1) splice against O(n) lookup trade-off.
• Trees: binary trees and their traversals, binary search trees, heaps, and tries.
• Graphs: adjacency-list representation, and directed, undirected, and weighted edges.
• Traversals and graph algorithms: breadth-first and depth-first search, topological sort, union-find, and shortest paths with Dijkstra.