Data Structures
A representation-first study of arrays, linked lists, stacks, queues, graphs, trees, search trees, heaps, hash tables, and disjoint sets in C.
A data structure is a promise about what a program may do efficiently, backed by a concrete memory representation whose invariants must survive every update. This course studies both halves of that promise. Each chapter begins with an abstract interface, derives one or more representations, traces mutations, implements the structure in C17, and closes with costs, failure modes, design trade-offs, and focused exercises.
The sequence moves from contiguous and linked storage through restricted-access structures, graph representations, hierarchical structures, priority structures, key-based lookup, and partition maintenance. Searching, sorting, graph traversal proofs, shortest paths, and other problem-solving procedures remain in the Algorithms course; this course concentrates on how data is represented and safely maintained.
Outline
Start →- 01ArraysContiguous layout, indexing, updates, dynamic growth, multidimensional and sparse storage, ownership, validation, and failure-safe vector design.
- 02Linked ListsSingly, doubly, circular, and sentinel lists; pointer updates, ownership, metadata, reversal, splicing, validation, and storage trade-offs.
- 03StacksLIFO contracts, fixed and dynamic arrays, linked stacks, call frames, expression processing, undo histories, failure handling, and testing.
- 04QueuesFIFO contracts, linear and circular arrays, linked queues, deques, dynamic growth, capacity policies, batching, iteration, and testing.
- 05GraphsGraph models and terminology; edge lists, matrices, adjacency containers, weighted and dynamic storage, identity, validation, serialization, and introductory BFS/DFS.
- 06TreesRooted and binary tree models, properties, linked and sequential representations, ownership, traversal state, measurements, serialization, cloning, and applications.
- 07Search TreesBST invariants and updates, ordered queries, deletion, rotations, AVL and red-black balancing, map contracts, rank metadata, iteration, and validation.
- 08HeapsBinary and d-ary heap invariants, array layout, sifting, heapify, priority contracts, stable ties, handles, batch construction, and testing.
- 09Hash TablesDictionary and set contracts, hashing and equality, chaining, probing, tombstones, load policies, transactional rehashing, iteration, and adversarial behavior.
- 10Disjoint SetsPartitions, forest invariants, union heuristics, path compression, component metadata, dynamic IDs, validation, rollback, and amortized costs.