One thing I find generally worth improving with these sorts of introductions is that they always seem to introduce data structures as a pick-and-mix bag of prebuilt parts, rather than a set of techniques which allow you to enforce <i>properties</i> which allow you to build objects that do what you want efficiently. Teaching the former is like teaching a physicist all the different kinds of gear systems, rather than the math that lets you model them.<p>Knowing how binary heaps and hash maps work is great, because binary heaps and hash maps are very useful data structures, but knowing the fundamental reasons behind them in a way that composes to building new things is much more useful. What happens when you want properties that someone hasn't already built a data structure for, at least as far as you can find? (Pet example: ordered container with efficient append and the ability to query the maximum of any subslice length k in O(log k). Extension: what are the minimal assumptions you need to do better, eg. amortized O(1)?)<p>I think this contributes to the attitude where programs are built out of monolithic, ill-fitting parts rather than actually looking at the problem and building the solution which does the right thing, the right way. (Pet example: if you designed websites as data structures and the browser to support doing so efficiently, 90% of requests on a site like Reddit would be a single `memcpy`.)<p>What I would attempt is rather than saying<p>"Here's one way we could do it: <explaination of pre-baked hash table>."<p>talk about the underlying tool first<p>"One tool that can help us is hashing: <explaination of general technique and why its properties are useful>. In this example we want <these properties> but can't immediately get it because our data has <these properties>. But we can apply hashing to get <technique that looks decent but has caveats>. Handling the caveats by doing <hash table things> gives us a data structure called a hash table."<p>Yes, this is probably a harder way to handle things, but I'd like to think it'd be worth the trouble.