Data structures
Undergraduate · CS / Programming
Syllabus focus
Topics typically covered
Standard syllabus
Analysis and linear structures
- Asymptotic notation: O, Ω, Θ; best/average/worst case
- Dynamic arrays and amortized analysis (intro)
- Linked lists: singly, doubly, and circular variants
- Stacks and queues; applications (parsing, BFS)
- Recursion and recursive data definitions
Trees, hashing, and heaps
- Binary trees; traversals (in-order, pre-order, post-order)
- Binary search trees; search, insert, delete
- Balanced trees overview (AVL, red-black at survey level)
- Hash tables: chaining, open addressing, load factor
- Heaps and priority queues; heap sort (intro)
STEM / applied
Implementation and applications
- Implementing ADTs in C++, Java, or Python with memory/performance tradeoffs
- Graph adjacency lists vs matrices for sparse/dense graphs
- Union–find (disjoint set) for connectivity problems
- Caching and LRU-style eviction (conceptual)
- Benchmarking structures on real datasets
Systems connections
- Memory layout: pointers, references, and object overhead
- Serialization of structures for storage and networking
- Concurrent data structures overview (locks, concurrent maps)
- Choosing structures for pipeline and ETL workloads
- Debugging memory leaks and invalid references
Notes
Typically follows intro programming. Exact coverage of balanced trees and graph representations varies by institution.