Skip to content
CourseBook Data Structures
Size
Font
Theme
Warmth
  1. Syllabus
  2. Schedule
  3. Instruction
  4. Logistics
  5. Exams
  6. Homework
  7. How to Study
  8. Demos
  10. Read
  11. The Dynamic Array
    1. What is a Data Structure?
    2. The Array Data Structure
    3. Arrays Have a Fixed Size
    4. Dynamic Arrays
    5. What is Abstraction?
    6. Inside the Dynamic Array
    7. Adding Elements
    8. Growing the Array
    9. Why Study Data Structures?
    10. Classes and Objects
    11. Encapsulation and Information Hiding
    12. What is an Algorithm?
    13. Selection Sort
    14. Where Algorithms Live
    15. Selection Sort with Helper Methods
    16. Removing Elements
    17. A Shared indexOf
    18. The Remove Contract
    19. Structures and Algorithms Together
  12. Generics
    1. Why Generics?
    2. Why Not Just Store Object?
    3. A Generic DynamicArray
    4. The Array Problem
    5. Using It
    6. The Trouble with Primitives
    7. Comparing Elements: equals vs ==
    8. Defining Equality for Student
    9. Ordering Elements: Comparable
    10. Making Student Comparable
    11. A Generic ArrayUtils
    12. Sorting, Generically
    13. Custom Orderings: Comparator
    14. Sorting with a Comparator
    15. Overloading remove: by Index or by Value
    16. The DynamicArray<Integer> Trap
  13. The Sorted Array
    1. Why Keep It Sorted?
    2. Binary Search
    3. Binary Search, Recursively
    4. Searching Half the Array
    5. Passing the Bounds
    6. The Base Case
    7. The Base Case and the Recursive Case
    8. Recursive Linear Search
    9. A Public Method and a Private Helper
    10. A Helper for Binary Search
    11. Recursive vs. Iterative
    12. Counting the Steps in Binary Search
    13. Linear vs. Binary Search, Side by Side
    14. The SortedArray
    15. Adding in Order
    16. Searching with Binary Search
    17. Removing
    18. Should we offer a set operation?
  14. Asymptotic Notation
    1. Why We Need a Way to Analyze Algorithms
    2. Why Not Just Time Them?
    3. Big-Oh Notation
    4. Why We Suppress Coefficients
    5. Why We Drop Lower Terms
    6. Reading Big-Oh from Code
    7. Two Loops, Still Linear
    8. Nested Loops Multiply
    9. Half the Work, Same Class
    10. A Loop That Doubles
    11. Building Up to Selection Sort
    12. Reasoning About Operations Without the Code
    13. Which Structure for the Roster?
    14. Why Not Sort Only When We Search?
    15. Growth Rate
    16. Common Running Times
    17. The Formal Definition of Big-Oh
  15. Complexity Analysis
    1. Time Complexity
    2. Best Case and Worst Case
    3. Average Case Analysis
    4. Space Complexity
    5. Space Complexity of Recursion
    6. Time and Space of Recursive Fibonacci
    7. A Faster Fibonacci
    8. A Leaner Fibonacci
    9. Complexity of grow and add
    10. Amortized Analysis
    11. Growing One Slot at a Time
    12. Why Doubling Works
    13. Computational Complexity
  16. Lists Without Arrays
    1. A Different Kind of List
    2. The ListItem Class
    3. A Linked List
    4. Two Kinds of Lists
    5. Following the Chain
    6. Traversing a List
    7. The Size of a List
    8. Getting an Item by Index
    9. Setting an Item by Index
    10. Searching for an Item
    11. Prepend Operation
    12. Append Operation
    13. A Tail Pointer
    14. Inserting After an Item
    15. Inserting Before an Item
    16. Removing an Item
    17. Getting the Item Itself
    18. A Backward Link
    19. Removing a Given Item
    20. Singly and Doubly Linked Lists
  17. Building a LinkedList
    1. Why the List Needs an Abstraction
    2. A Class to Own the List
    3. From ListItem to Node
    4. Keeping the Size
    5. Adding to the List
    6. Getting by Index
    7. Setting by Index
    8. Searching the List
    9. Removing by Index
    10. Removing by Value
    11. The Whole Class
    12. Two Lists, Side by Side
    13. Special Cases at the Ends
    14. A Sentinel Node
  18. The List ADT
    1. Run Selection Sort on LinkedList
    2. The List Interface
    3. Implementing a List Interface
    4. Operation Costs Behind the Interface
    5. Abstract Data Types
    6. Documenting the Contract
    7. Naming the Implementations
    8. Program to the Interface
    9. A Second ADT: SortedList
    10. A Class to Hold a Sorted List
    11. Adding in Order
    12. Access and Search
    13. Removing a Value
  19. Testing
    1. How Do We Know It’s Correct?
    2. JUnit, a Testing Library
    3. Your First Test
    4. Writing Good Tests
    5. Saying the Setup Once
    6. Testing That a Method Throws
    7. From Testing a Class to Testing a Contract
    8. One Suite, Many Implementations
    9. Covering the Edge Cases
    10. Test-First Development
    11. Kinds of Testing
  20. The Stack
    1. Implementing Undo
    2. The Stack ADT
    3. Stack ADT Specification
    4. Using an Array to Implement a Stack
    5. The ArrayStack Class
    6. Implementing isEmpty, top, and pop
    7. Implementing push
    8. Tracing the ArrayStack
    9. Using a Linked List to Implement a Stack
    10. The LinkedStack Class
    11. Implementing pop, top, and push
    12. Tracing the LinkedStack
    13. Two Stacks, Side by Side
  21. The Queue
    1. Sharing a Printer
    2. The Queue ADT
    3. Queue ADT Specification
    4. Using a Linked List to Implement a Queue
    5. The LinkedQueue Class
    6. Implementing front, dequeue, and enqueue
    7. Tracing the LinkedQueue
    8. Using an Array to Implement a Queue
    9. The Circular Array
    10. Designing the ArrayQueue
    11. The ArrayQueue Class
    12. Implementing enqueue
    13. Tracing the ArrayQueue
    14. Two Queues, Side by Side
  22. The Deque
    1. Double-Ended Queue (Deque)
    2. The Deque ADT
    3. Deque ADT Specification
    4. Using a Linked List to Implement a Deque
    5. The LinkedDeque Class
    6. Implementing addFirst and addLast
    7. Implementing getFirst, getLast, removeFirst, and removeLast
    8. Tracing the LinkedDeque
    9. Using an Array to Implement a Deque
    10. Designing the ArrayDeque
    11. The ArrayDeque Class
    12. Implementing addFirst, addLast, and grow
    13. Tracing the ArrayDeque
    14. Two Deques, Side by Side
  23. Quadratic Sorting
    1. Selection Sort, Again
    2. Selection Sort: Comparisons and Swaps
    3. Bubble Sort: The Idea
    4. Implementing Bubble Sort
    5. Bubble Sort: Comparisons and Swaps
    6. Bubble Sort with Early Termination
    7. Insertion Sort: The Idea
    8. Implementing Insertion Sort
    9. Insertion Sort: Comparisons and Swaps
    10. Insertion Sort: Shifting Instead of Swapping
    11. Classifying the Sorts We Have Written
    12. Stable Sorting
  24. Merge Sort
    1. Merge Two Sorted Hands
    2. Merge Two Sorted Arrays
    3. Implementing the Merge Process
    4. Complexity of the Merge Process
    5. In-Place Merge
    6. In-Place Merge: Analysis
    7. The Common Way to Merge
    8. Repeating the Merge Process
    9. Bottom-Up Merge Sort
    10. Merge Sort: Time and Space Complexity
    11. Merge Sort: Best and Worst Case
    12. Merge Sort for Any Length
    13. Counting Up and Counting Down
    14. A Top-Down Trace
    15. Merge Sort, Recursively
    16. Analyzing the Recursive Version
    17. Properties of Merge Sort
  25. Maze Solving
    1. Why Mazes?
    2. Representing a Maze
    3. The Maze Path Problem
    4. Asking About a Cell
    5. A First Recursive Search
    6. Remembering Where We Have Been
    7. Returning Through a Path
    8. Tracing Recursive Backtracking
    9. Searching with an Explicit Stack
    10. Tidying Up the Stack-Based Search
    11. The Stack Search in Code
    12. Swapping in a Queue
    13. Tracing the Queue Search
    14. The Cost of the Three Searches
  26. The Set
    1. Choosing a Username
    2. The Set ADT
    3. Set ADT Specification
    4. Using a Linked List to Implement a Set
    5. The LinkedSet Class
    6. Implementing contains, add, and remove
    7. Tracing the LinkedSet
    8. Using an Array to Implement a Set
    9. The ArraySet Class
    10. Implementing contains, add, and remove
    11. Tracing the ArraySet
    12. The Move-to-Front Heuristic
    13. The Transpose Heuristic
    14. Using a Sorted Array to Implement a Set
  27. Iterators
    1. Visiting Every Element
    2. Making a Set Iterable
    3. Borrowing an Iterator
    4. Writing the ArraySet Iterator
    5. Tracing the ArraySet Iterator
    6. The Cost of Iterating
    7. Iterable and Iterator
    8. The LinkedSet Iterator
    9. Inner Classes and Static Nested Classes
    10. Testing the Iterator
    11. Modifying a Set While Iterating
    12. Failing Fast
  28. The Map
    1. Storing a Password
    2. The Map ADT
    3. Map ADT Specification
    4. Using a Linked List to Implement a Map
    5. The LinkedMap Class
    6. Implementing get, containsKey, put, and remove
    7. Tracing the LinkedMap
    8. Using an Array to Implement a Map
    9. The ArrayMap Class
    10. Implementing get, containsKey, put, and remove
    11. Tracing the ArrayMap
    12. Keys Must Not Change
    13. Iterating a Map
    14. Returning the Stored Entries
    15. Why Not Return the Stored Object
    16. The Map.Entry Interface
    17. Iterating the Entries
  29. Recursion and Trees
    1. Revisiting Recursion
    2. The Call Tree
    3. A Linked List Is Recursive
    4. A Tree Is Recursive
    5. Linked Lists and Trees
    6. Anatomy of a Tree
    7. Narrowing to Binary Trees
    8. From a Definition to a Node
    9. Counting the Nodes
    10. Measuring Height
    11. Measuring Depth
    12. Traversing the Tree
    13. Tracing the Three Orders
    14. Traversing Level by Level
    15. Trying Recursion
    16. A Queue of Waiting Nodes
    17. Level-order in Code
    18. Traversals in Practice
  30. The Binary Search Tree
    1. The Ordering Property
    2. The Node and the Tree
    3. Searching for a Value
    4. Search in Code
    5. Tracing a Search
    6. Adding a Value
    7. Add in Code
    8. Tracing an Add
    9. In-order Is Sorted
    10. Minimum, Maximum, and Successor
    11. Removing a Leaf or a Single Child
    12. Removing a Node with Two Children
    13. Remove in Code
    14. Tracing a Remove
    15. Iterating in Sorted Order
    16. Tracing the Iterator
    17. The Cost of the Iterator
    18. How Short Can a Tree Be?
  31. The AVL Tree
    1. Keeping the Tree Balanced
    2. The Balance Factor
    3. The AVL Property
    4. Structural Rotation
    5. Single Rotations
    6. Double Rotations
    7. Choosing the Rotation
    8. Tracing a Full Sequence
    9. One Repair per Insertion
    10. Removal Can Rebalance Several Ancestors
    11. Why Balance Keeps the Tree Short
  32. The TreeMap
    1. Using a Balanced Tree to Implement a Map
    2. Starting from the Search Tree
    3. Implementing get and containsKey
    4. Where Balancing Goes
    5. Rotations in Code
    6. The Rebalance Helper
    7. put, First Version
    8. Why Recomputing Height Is Slow
    9. Caching the Height
    10. Rotations Keep the Height
    11. put, Final Version
    12. Implementing remove
    13. Iterating in Key Order
    14. Tracing the TreeMap
    15. The Complete TreeMap
    16. Four Maps, Side by Side
  33. The Priority Queue
    1. The Emergency Room
    2. The Priority Queue ADT
    3. Priority Queue ADT Specification
    4. Should a Priority Queue Be Iterable?
    5. Two Unsorted Designs
    6. A Sorted Design
    7. The Binary Heap
    8. The Structure Property
    9. The Order Property
    10. add: Insert and Swim Up
    11. remove: Replace the Root and Sink Down
    12. Tracing a Heap
    13. Tracing peek, remove, and add
    14. The Height of a Heap
    15. Why Every Operation Is O(log n) or Better
  34. Implementing the Binary Heap
    1. A Heap Built from Nodes
    2. Finding the Next Open Slot
    3. The Path in Binary
    4. Reaching the Parent
    5. add, Recursively
    6. remove in Code
    7. Tracing a Recursive add
    8. A Heap in an Array
    9. Tracing the Array
    10. The ArrayHeap Class and Its Helpers
    11. swim and sink in an Array
    12. Implementing peek, add, and remove
    13. Two Heaps, Side by Side
  36. Review
  37. The Dynamic Array
    1. Data Structures and Arrays
    2. Abstraction
    3. Dynamic Array Operations
    4. Search and Removal
    5. Dynamic Array Trace
    6. Algorithms and Selection Sort
  38. Generics
    1. Why Generics, and How to Declare One
    2. Defining Equality
    3. Natural Ordering with Comparable
    4. Generic Sorting with Bounded Type Parameters
    5. External Ordering with Comparator
    6. Overloading remove and the Integer Trap
  39. The Sorted Array
    1. Binary Search: Why and How
    2. Recursive Binary Search and the Base Case
    3. Counting Search Steps
    4. Building SortedArray: the Invariant and Adding
    5. Searching, Removing, and Why No set()
  40. Asymptotic Notation
    1. What Big-Oh Measures
    2. From a Step Count to Big-Oh
    3. Big-Oh from Loop Structure
    4. Operation Costs and Choosing by Workload
    5. Growth Rate and the Common Families
  41. Complexity Analysis
    1. Best, Worst, and Average Case
    2. Time and Space Complexity
    3. Space Complexity of Recursion
    4. Amortized Analysis
  42. Lists Without Arrays
    1. Linked List Concept
    2. Traversal and Read-Only Operations
    3. Structural Operations by Index
    4. Trace: Building and Changing a List
    5. Operating on a ListItem Directly
    6. Singly vs. Doubly Linked Lists
  43. Building a LinkedList
    1. The List’s Invariant
    2. Access and Search
    3. Adding and Removing
    4. Trace
    5. LinkedList vs. DynamicArray
    6. Sentinel Nodes
  44. The List ADT
    1. Type Substitution
    2. The List ADT
    3. The SortedList ADT
    4. Implementing SortedLinkedList
    5. Tracing SortedLinkedList
  45. Testing
    1. Correctness and Confidence
    2. Writing JUnit Tests
    3. Testing Multiple Implementations
    4. Choosing Edge Cases
    5. Test-First Development
  46. The Stack
    1. The Stack ADT
    2. Implementing ArrayStack
    3. Implementing LinkedStack
    4. Tracing the Two Stacks
  47. The Queue
    1. The Queue ADT
    2. Implementing LinkedQueue
    3. The Circular Array
    4. Implementing ArrayQueue
    5. Tracing the Two Queues
  48. The Deque
    1. The Deque ADT
    2. Implementing LinkedDeque
    3. The Circular Array for a Deque
    4. Implementing ArrayDeque
    5. Tracing the Two Deques
  49. Quadratic Sorting
    1. Selection Sort
    2. Bubble Sort
    3. Insertion Sort
    4. Comparing the Sorts and Stability
  50. Merge Sort
    1. Merging Two Sorted Arrays
    2. In-Place Merge and the Common Merge
    3. Bottom-Up Merge Sort
    4. Recursive Merge Sort
    5. Properties of Merge Sort
  51. Maze Solving
    1. Maze Helpers and Edge Cases
    2. Recursive Backtracking
    3. Searching with a Stack
    4. Queue Search and Cost
  52. The Set
    1. The Set ADT
    2. Implementing LinkedSet
    3. Implementing ArraySet
    4. Tracing the Two Sets
    5. Self-Organizing Heuristics
    6. The Sorted Array Set
  53. Iterators
    1. Iterable and Iterator
    2. Writing Iterators
    3. Testing an Iterator
    4. Modifying a Set While Iterating
  54. The Map
    1. The Map ADT
    2. Implementing LinkedMap
    3. Implementing ArrayMap
    4. Tracing the Two Maps
    5. Keys Must Not Change
    6. Iterating the Keys
    7. Iterating Key–Value Pairs
    8. Implementing entries()
  55. Recursion and Trees
    1. Call Trees and the Parts of a Tree
    2. Recursive Methods on a Binary Tree
    3. Depth-First Traversals
    4. Level-Order Traversal
    5. Choosing a Traversal
  56. The Binary Search Tree
    1. The Ordering Property
    2. Search, Add, and Remove by Hand
    3. Implementing the Operations
    4. The In-order Iterator
    5. Height and Shape
  57. The AVL Tree
    1. Balance and the AVL Property
    2. Rotations by Hand
    3. Choosing a Rotation
    4. Insertion and Removal by Hand
    5. The Height of an AVL Tree
  58. The TreeMap
    1. TreeMap Design and Costs
    2. Rotations and Rebalancing in Code
    3. Implementing put and remove
    4. The Height Cache
    5. Iterating a TreeMap
  59. The Priority Queue
    1. The Priority Queue ADT
    2. Flat Designs
    3. The Heap Properties
    4. Adding to and Removing from a Heap
    5. Tracing a Heap
    6. Heap Height and Analysis
  60. Implementing the Binary Heap
    1. Finding a Position in a Linked Heap
    2. Implementing the Linked Heap
    3. Tracing add on a Linked Heap
    4. Storing a Heap in an Array
    5. Tracing an Array Heap
    6. Implementing ArrayHeap
    7. Comparing the Two Heaps
  62. Practice
  63. The Dynamic Array
    1. Problem: Build a Bag
    2. Solution: Fields and Constructor
    3. Solution: Adding a Ball
    4. Solution: Growing the Bag
    5. Solution: Drawing a Ball at Random
  64. Generics
    1. Problem: Make a Card Orderable
    2. Solution: Value Equality
    3. Solution: A Natural Order
    4. Solution: A Second Order
    5. Problem: A Generic max
    6. Solution: Max by Natural Order
    7. Solution: Max by a Comparator
  65. The Sorted Array
    1. Problem: Build a Leaderboard
    2. Leaderboard: Fields and get
    3. Leaderboard: add, Phase 1 — the Guard
    4. Leaderboard: add, Phase 2 — Insert
    5. Leaderboard: add, Phase 3 — Trim
  66. Asymptotic Notation
    1. Problem: Remove Duplicates from Sorted Array
    2. Solution: Brute Force
    3. Solution: Two Pointers
    4. Problem: Two Sum When Input Array is Sorted
    5. Solution: Brute Force
    6. Solution: Binary Search
    7. Solution: Two Pointers
  67. Complexity Analysis
    1. Problem: Fibonacci with Memoization
    2. Solution: Caching the Results
    3. Problem: A DynamicArray That Shrinks
    4. Solution: Shrinking at Half Empty
    5. Solution: Shrinking at a Quarter Full
  68. Lists Without Arrays
    1. Problem: Reverse a Linked List
    2. Solution: Building a New List
    3. Solution: Re-Pointing the Links
    4. Problem: Detect a Cycle in a Linked List
    5. Solution: Re-Searching Seen Items
    6. Solution: Slow and Fast Pointers
    7. Problem: Kth to Last Element in Linked List
    8. Solution: A Fixed Gap Between Two Pointers
  69. Building a LinkedList
    1. Problem: Rebuild LinkedList with Sentinels
    2. Solution: Fields and Constructor
    3. Solution: Adding with Sentinels
    4. Solution: Access and Search
    5. Solution: Removing by Index
    6. Solution: Removing by Value
  70. The List ADT
    1. Problem: SparseList
    2. Solution: Fields and Constructor
    3. Solution: Reading a Value: get
    4. Solution: Writing a Value: set
    5. Solution: Growing the List: add
  71. Testing
    1. Problem: Testing a MaxList
    2. Solution: The getMax Tests
    3. Solution: Designing the Implementation
    4. Problem: Testing the Bag
    5. Solution: Testing a Random Draw
    6. Solution: A Seeded Constructor
  72. The Stack
    1. Problem: Valid Parentheses
    2. Solution: A Naive Attempt
    3. Solution: Removing Adjacent Pairs
    4. Solution: Matching with a Stack
    5. Problem: Evaluate Reverse Polish Notation
    6. Solution: Reducing the First Operator
    7. Solution: Evaluating with a Stack
    8. Problem: MinStack
    9. Solution: Tracking the Minimum
    10. Problem: MonotonicStack
    11. Solution: Evicting on Push
  73. The Queue
    1. Problem: Round-Robin Scheduling
    2. Solution: A Queue of Burst Times
    3. Solution: A Queue of Task Indices
    4. Solution: Cost of the Simulation
    5. Problem: Josephus
    6. Solution: Marking the Eliminated
    7. Solution: Rotating a Queue
    8. Solution: The Circularly Linked List
    9. Solution: Counting Around a Circular List
    10. Problem: Moving Average
    11. Solution: Keeping a Running Sum
    12. Problem: Queue with Two Stacks
    13. Solution: Pouring Only When Empty
  74. The Deque
    1. Problem: MaxQueue
    2. Solution: Scanning for the Maximum
    3. Solution: Copying MinStack
    4. Solution: Keeping the Candidates
    5. Solution: Two Deques
    6. Solution: Tracing MaxQueue
    7. Solution: Cost
    8. Solution: Two MaxStacks
    9. Problem: Sliding Window Maximum
    10. Solution: Scanning Every Window
    11. Solution: A Running Maximum
    12. Solution: Keeping the Candidates
    13. Solution: Storing Positions, Not Values
    14. Solution: A Deque of Indices
    15. Solution: Tracing the Deque
    16. Solution: Edge Cases and Cost
  75. Quadratic Sorting
    1. Problem: Insertion Sort with Binary Search
    2. Solution: Fewer Comparisons, the Same Shifts
    3. Problem: Cocktail Shaker Sort
    4. Solution: Bubbling in Both Directions
  76. Merge Sort
    1. Problem: Union of Two Sorted Arrays
    2. Solution: Merge, Skipping the Ties
    3. Problem: Merge k Sorted Arrays
    4. Solution: One Array at a Time
    5. Solution: Merging in Pairs
  77. Maze Solving
    1. Problem: Reachable Cells
    2. Solution: Counting Cells with a Stack
    3. Problem: Maze Distance
    4. Solution: Measuring Distance with a Queue
    5. Problem: Maze Path
    6. Solution: Recovering the Path
  78. The Set
    1. Problem: Set Operations
    2. Solution: Union
    3. Solution: Intersection
    4. Solution: Difference
  79. Iterators
    1. Problem: Iterating a SparseList
    2. Solution: Two Cursors in Step
    3. Problem: The Collatz Sequence
    4. Solution: Knowing When to Stop
  80. The Map
    1. Problem: A Sorted Array Map
    2. Solution: Fields and Finding a Key
    3. Solution: Adding a Pair: put
    4. Solution: Removing a Pair: remove
    5. Solution: Iterating Keys and Entries
    6. Problem: A Set Backed by a Map
    7. Solution: A Set Backed by a Map
  81. Recursion and Trees
    1. Why Write Iterative Traversals
    2. Problem: Iterative Pre-order Traversal
    3. Solution: Right Child First
    4. Problem: Iterative In-order Traversal
    5. Solution: Following the Left Spine
    6. Problem: Iterative Post-order Traversal
    7. Solution: Pre-order in Reverse
  82. The Binary Search Tree
    1. Problem: Validating a Binary Search Tree
    2. Solution: Carrying Bounds Down the Recursion
    3. Problem: The k-th Smallest Value
    4. Solution: The k-th In-order Visit
  83. The AVL Tree
    1. Problem: Validating an AVL Tree
    2. Solution: Two Separate Checks
    3. Solution: One Post-Order Pass
    4. Problem: Balancing a Binary Search Tree
    5. Solution: Choosing the Middle as the Root
    6. Solution: Flatten, Then Rebuild
  84. The TreeMap
    1. Problem: Ordered Queries on the TreeMap
    2. Solution: Descending Toward the Key
    3. Solution: Pruning the Traversal
    4. Problem: Order Statistics
    5. Solution: Caching Subtree Sizes
    6. Solution: select
    7. Solution: rank
  85. The Priority Queue
    1. Problem: Validate a Heap
    2. Solution: Checking the Order
    3. Solution: Checking Completeness
  86. Implementing the Binary Heap
    1. Problem: The Kth Largest Element
    2. Solution: Sorting the Array
    3. Solution: A Max-Heap
    4. Solution: Keeping Only the k Largest
    5. Problem: Median of a Data Stream
    6. Solution: Keep a Sorted List
    7. Solution: Two Heaps
  88. Homework
  89. HW1: Sort and Search
    1. Rules and Starter Code
    2. Task 1: The Measured List
    3. Task 2: Sorting
    4. Task 3: Sets
    5. Task 4: Discussion of the Sorts
    6. Task 4: Discussion of the Sets
    7. Submission
    8. Rubric

Review Overview

These questions cover the chapter’s material. Try each one on your own before opening the sample answer. Compare your answer to the sample. If they line up, move on; if they do not, or the sample answer is not clear, it may help to revisit the chapter notes.

  1. The Map ADT
  2. Implementing LinkedMap
  3. Implementing ArrayMap
  4. Tracing the Two Maps
  5. Keys Must Not Change
  6. Iterating the Keys
  7. Iterating Key–Value Pairs
  8. Implementing entries()
PreviousModifying a Set While Iterating NextThe Map ADT