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?
  15. Review
  16. 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
  17. 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
  18. 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()
  20. Practice
  21. 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
  22. 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
  23. 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

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. 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()
PreviousOverloading remove and the Integer Trap NextBinary Search: Why and How