Why Study Data Structures?

Every major language already ships a dynamic array: Java’s ArrayList, Python’s list, C++'s std::vector. If someone already built and tested this for us, why bother understanding how it works?

The cost of add is a good answer.

To the caller, add is a single operation. The interface tells you what it does, which is append a value. It does not tell you what that costs. We just saw that the cost is nuanced. Usually add is a single write, and when the array is full it allocates a larger array and copies the existing elements over.

If all you know is the interface, you cannot see that variation. You might assume every add costs the same and then be surprised when a program that adds millions of elements spends a noticeable part of its time copying.

Once you know how it works inside, you can reason about the behavior instead of guessing at it:

• You know most adds are cheap and only the occasional one is expensive.
• You know why the expensive adds happen. The array is full. If you see a spike in a profiler, you can explain it.
• You can act on it. If you know roughly how many elements you will add, you can ask for that capacity up front and avoid growing the array entirely. ArrayList has a constructor that takes an initial capacity. That constructor is only useful if you know what grow does.

That is why we study data structures. We are not going to reinvent ArrayList. We are learning how a structure is organized inside and what its operations cost, so that we can predict how it will behave and pick the right one for a problem.

We will ask the same questions about every data structure from here on: what it organizes, what it lets us do, and what it costs.