Week 5: Data Structures
Building your own containers out of pointers: stacks, queues, linked lists, trees, hash tables, and tries, each trading one strength for another.
9 topics · 37 questions
Each topic is a path, not a menu: work down it in order and every question builds on the one above. Click any of them to watch the answer draw itself.
Abstract Data Types
- How it worksHow does an abstract data type define which operations are allowed without dictating how they're implemented?
- Worked exampleWalk me through implementing a stack's push and pop operations using nothing but an array and a top index.
- Going furtherWhat happens to a program's flexibility when it's written against an abstract data type instead of one fixed implementation?
- Ties togetherHow does separating interface from implementation connect back to abstraction in Scratch's building blocks?
Your turn1 of 2
A stack implemented with an array and a top index starts empty. After pushing 36 elements it has 36 elements. How many elements remain after popping 3 of them off?Stacks: LIFO
- How it worksHow do push and pop operations only ever touch the very top of a stack?
- Worked exampleWalk me through pushing 3, 7, and 9 onto an empty stack and then popping twice.
- Common mistakeWhy isn't a stack the right structure for a line of customers waiting to be served in order?
Your turn1 of 2
Starting with an empty stack, 36 values are pushed one at a time, then 3 of them are popped. How many values remain on the stack?Queues: FIFO
- Worked exampleWalk me through enqueueing 3, 7, and 9 into an empty queue and then dequeueing once.
- Common mistakeWhy isn't a queue just a stack that happens to be drawn sideways?
- Going furtherWhat happens to a queue's front and back pointers as elements are enqueued and dequeued in a circular buffer?
Your turn1 of 2
Starting with an empty queue, 36 values are enqueued one at a time, then 3 of them are dequeued. How many values remain in the queue?Singly Linked Lists
- How it worksHow does each node in a linked list hold both a value and a pointer to the next node?
- How it worksHow does traversing a linked list mean following its chain of next pointers one node at a time from the head?
- Worked exampleWalk me through building a linked list by inserting the values 5, then 3, then 8 at the front, one at a time.
- Common mistakeWhy isn't a linked list stored as one contiguous block of memory the way an array is?
Your turn1 of 2
A singly linked list has 35 nodes chained together. Finding the last node means following the chain from the head. How many next-pointers does the traversal follow to reach the last node?The Exact Order of Linked List Insertion
- How it worksHow does inserting a node at the front require setting its next pointer before the head pointer is moved?
- Common mistakeWhy isn't it safe to point the new node's next pointer at the list before saving where the list used to start?
- Worked exampleWalk me through inserting the value 4 at the front of the linked list 7 to 2 to 9, one pointer at a time.
- Going furtherWhat happens to the rest of a linked list if you move the head pointer before setting the new node's next pointer?
Your turn1 of 2
Inserting 28 nodes at the front of an empty linked list, one at a time, requires setting each new node's next-pointer before moving the head. How many total next-pointer assignments happen across all 28 insertions?Trees and Binary Search Trees
- How it worksHow does a binary search tree keep every left child smaller and every right child larger than its parent?
- How it worksHow does searching a binary search tree eliminate a whole subtree with each comparison, the way binary search eliminates half a list?
- Worked exampleWalk me through inserting 5, 3, 8, 1, 4 one at a time into an empty binary search tree.
- Common mistakeWhy isn't a binary search tree built from an already-sorted list automatically balanced?
- Going furtherWhat happens to search time in a binary search tree that has degenerated into one long chain?
Your turn1 of 2
A perfectly balanced binary search tree holding 29 - 1 nodes has height k - 1. What is the tree's height when k = 9?Hash Tables and Collision Resolution
- How it worksHow does a hash function turn a string into an index into an array of buckets?
- Worked exampleWalk me through hashing the words CAT and DOG into a table of 5 buckets using the sum of ASCII values mod 5.
- Worked exampleWalk me through chaining a collision when two different words hash to the same bucket index.
- Common mistakeWhy isn't a hash table's speed ruined by the occasional collision between two keys?
- Going furtherWhat happens to a hash table's average lookup time as more and more keys collide into the same buckets?
Your turn1 of 2
A hash table has 142 buckets, and 6 keys have already been inserted. What is the load factor (keys divided by buckets), as a decimal?Tries
- How it worksHow does each node in a trie hold one pointer per possible next letter, spelling words out path by path?
- Worked exampleWalk me through inserting the words CAT and CAR into an empty trie, letter by letter.
- Going furtherWhat happens to a trie's memory usage as more and more unrelated words are inserted into it?
- Ties togetherHow does a trie's lookup speed regardless of dictionary size connect to why hash tables were built in the first place?
Your turn1 of 2
A trie stores words up to 17 letters long, and each node holds one pointer per possible next letter. Looking up a word of length 6 follows how many pointers from the root to confirm it, one per letter?Tradeoffs Among Data Structures
- How it worksHow do arrays, linked lists, hash tables, and tries each trade away one strength to gain another?
- Worked exampleFind which structure gives faster lookup for a dictionary of 100,000 words: a linked list or a hash table, and why.
- Common mistakeWhy isn't a hash table always the right choice just because its average lookup time is so fast?
- Going furtherWhat happens to your choice of data structure when memory is scarce but lookup speed barely matters?
- Ties togetherHow does the tradeoff between a hash table's speed and a linked list's low memory use connect back to Big O's focus on the worst case?
Your turn1 of 2
A dictionary of 699 words is stored in a linked list. In the worst case, how many comparisons does the linked list need to determine that a word is NOT present?