The Dynamic Array

This chapter builds a dynamic array over a plain, fixed-size array: what a data structure is, abstraction, and the add, grow, and remove operations. Along the way it covers classes, objects, and encapsulation, and implements linear search and selection sort over the structure.

After reading this chapter, you should be able to:

  • Describe a data structure through three lenses: how it organizes data, what operations it offers, and what trade-offs it makes
  • Work with Java arrays (declare, initialize, index, and resize them) and explain why contiguous memory makes index access fast, and what the array’s trade-offs are (fixed size, costly insert/delete, wasted memory)
  • Explain abstraction as separating an interface (what) from its implementation (how), and identify both the array and the dynamic array as abstractions
  • Build a dynamic array over a fixed-size array: pair a backing array with a logical size, write its constructor, and implement size, add, and get
  • Implement grow by allocating a larger array, copying the elements over, and replacing the backing array, and explain why add is usually a single write but costly when the backing array is full
  • Distinguish a class from an object, and apply encapsulation: keep fields private and expose behavior through methods
  • Define an algorithm by its properties (finite, unambiguous, ordered, well-defined) and implement linear search and selection sort over the dynamic array using only its public operations, decomposing them into reusable helper methods (indexOfMin, swap, indexOf)

You can download the accompanying code for this chapter: starter and solution.

Notes

  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