wunder beta📘 How do data structures trade time for space?
Arrays, maps, and trees—how choosing a structure is choosing a cost, not a vibe.
What you’ll learn
- Why Data Structures Matter: Abstraction and CostExplain what a data structure is, how abstract data types separate interface from implementation, and how to reason about cost using asymptotic (Big-O) analysis.A data structure is a concrete way of organizing data in memory so that specific operations are efficient, while an abstract data type (ADT) specifies the operations without committing to an implementation. Because the same ADT can be backed by different structures with very different costs, we compare them using asymptotic analysis, which describes how running time grows with input size n. Big-O notation gives an upper bound on that growth, letting us choose the right structure before writing a single line of code.
- Arrays and Linked Lists: Contiguous vs. Linked MemoryCompare array-based and linked storage, deriving the costs of access, insertion, and deletion from how each lays data out in memory.Arrays store elements in a contiguous block of memory, which gives constant-time random access by index but makes inserting or deleting in the middle expensive because elements must shift. Linked lists store each element in a node that points to the next, allowing constant-time insertion and deletion once you hold the relevant node, but forcing linear-time traversal to reach a position. Dynamic arrays add automatic resizing with O(1) amortized appends. Understanding these layout-driven trade-offs underlies almost every higher-level structure.
- Stacks and Queues: Disciplined AccessDescribe the stack (LIFO) and queue (FIFO) ADTs, their core operations, common implementations, and the problems each is designed to solve.Stacks and queues are restricted-access ADTs: a stack serves elements last-in-first-out (LIFO) through push and pop, while a queue serves them first-in-first-out (FIFO) through enqueue and dequeue. Both offer all core operations in O(1) time and can be implemented on top of arrays or linked lists. Their disciplined access patterns make them ideal for managing function calls, undo histories, breadth-first traversals, and buffering. Choosing the right discipline is often the key insight in solving a problem cleanly.
- Hash Tables and Trees: Fast Lookup and OrderExplain how hash tables achieve average O(1) lookup and how binary search trees maintain ordered data with logarithmic operations when balanced.A hash table stores key-value pairs in buckets chosen by a hash function, delivering average-case O(1) insertion, lookup, and deletion at the cost of no inherent ordering and worst-case O(n) behavior under collisions. A binary search tree (BST) keeps keys ordered so that search, insertion, and deletion take time proportional to the tree's height, which is O(log n) only when the tree stays balanced; self-balancing variants guarantee this. Together these structures cover the two dominant needs in computing: fast unordered lookup and efficient ordered queries.
- Build It: A Word-Frequency Analyzer ArtifactApply the course's data structures by designing and building a small word-frequency analyzer that uses a hash table to count words and an ordered structure to report top results.In this capstone you will build a word-frequency analyzer that reads text, counts how often each word appears, and reports the most frequent words. The design uses a hash table (dictionary) for O(1) average counting and a sorting or priority-queue step to extract the top results, directly applying the trade-offs taught in earlier lessons. By choosing each structure to match an operation, you turn abstract complexity analysis into a working, justified program. The result is a portfolio-ready artifact that demonstrates structure selection, not just coding.
Questions this course answers
What is the key distinction between an abstract data type (ADT) and a data structure?
An ADT is the interface or contract, listing operations and their semantics without dictating implementation. A data structure is one concrete realization of that contract in memory, so the same ADT can be implemented by different data structures with different costs.
If an operation runs in 3n + 50 steps, what is its Big-O time complexity?
Big-O ignores constant factors and lower-order terms. The dominant term in 3n + 50 is the linear term, so the complexity is O(n): when n doubles, the work roughly doubles.
Which statement best describes amortized cost?
Amortized cost spreads the total cost of a sequence of operations over the number of operations. It is how we justify calling dynamic-array insertion 'O(1) amortized' even though occasional resizes are O(n).
Why does an array support O(1) random access by index?
Array elements are stored contiguously and uniformly sized, so the address of element i is base + i times element size. This direct arithmetic addressing is what makes random access constant time.
What is the worst-case time to insert an element in the middle of an array of n elements while preserving order?
Inserting in the middle requires shifting every element after the insertion point one slot to the right, which is up to n moves. That makes order-preserving middle insertion O(n).
Why does a dynamic array grow its capacity by a constant factor (for example, doubling) on resize rather than adding a fixed number of slots?
Multiplying the capacity by a constant factor greater than one makes resizes geometrically rare, so the total cost of all the copies across n appends is proportional to n, yielding O(1) amortized cost per append. Growing by a fixed additive amount would make total copying O(n squared).
Grounded in trusted sources
- Cormen, Leiserson, Rivest, and Stein, "Introduction to Algorithms," 4th edition (MIT Press, 2022), Chapters 3 and 10
- Sedgewick and Wayne, "Algorithms," 4th edition (Addison-Wesley, 2011), Section 1.4
- Cormen, Leiserson, Rivest, and Stein, "Introduction to Algorithms," 4th edition (MIT Press, 2022), Sections 10.1 and 10.2
- Sedgewick and Wayne, "Algorithms," 4th edition (Addison-Wesley, 2011), Section 1.3
- Cormen, Leiserson, Rivest, and Stein, "Introduction to Algorithms," 4th edition (MIT Press, 2022), Section 10.1
- Cormen, Leiserson, Rivest, and Stein, "Introduction to Algorithms," 4th edition (MIT Press, 2022), Chapters 11, 12, and 13
Every Wunder lesson is built from real, reputable sources — never invented.
Related courses
Wunder is a personalized learn-anything platform — tell it any topic and it builds a beautiful, fact-checked course in minutes, with narration, a knowledge check, and a college-style University track.
© 2026 Wunder Learning LLC · Terms & Privacy