Specifying “The Rules”
At each stage—the interface, the encoding, and the implementation—we need to pay attention to what promises we're making and what promises we're not making. Sometimes we call that set of promises (and nonpromises) a data structure's “contract” with its users.
For example,
- The interface might specify a required asymptotic complexity for a given operation.
- The encoding might specify a required relationship between two data members (e.g., it is always the case that
size_ <= capacity_). - The implementation might specify that it gracefully handles unexpected situations, such as running out of memory, or that it includes optimizations for a particular CPU.
But there are also, as always, trade-offs. Providing certainty about behavior provides certainty for users, but it also ties our hands as programmers and precludes some options we might have taken.
Constraints Imposed by Allowing Constant-Time Indexing
If our STRING-LIST data structure provides a constant-time indexing operation, we cannot implement it using a linked list. Let's just check why...
But we could use a different encoding, right?
Yes, we could. We could use an array-backed list, for example. But that would have other trade-offs.
Okay, we've made good progress and are about halfway through the lesson. Let's head up to the parent page to see our progress, and maybe take a stretch break.
(When logged in, completion status appears here.)