The debate over use vs. implementation of basic data structures mirrors the broader debate over component development vs. component integration. On these issues I come down firmly in the middle: I believe both exploration of implementation issues and use of objects based on their interfaces must be integrated into CS2. My concern is that reaction against past over emphasis on implementation issues will swing the pendulum too far in the direction of use with little concern for implementation.
It is instructive in this regard to see how other engineering disciplines have dealt with the explosive growth in technology. In particular, most introductory EE courses require students to design, analyze, implement, and measure simple RC circuits and the like. This is a result of a deeply held belief that mastery of the fundamentals is the essence of the discipline, and that what is taught should not be driven by the pace of technological change. What can change, however, is the scale and scope of the problems addressed, because of the tools newer technology can provide.
In a similar vein, I would be concerned if we were to produce graduates who have little or no appreciation for the tradeoffs involved in implementing something as simple as a dictionary of key/value pairs. While they would be able to use dictionaries, they would be at a loss to develop one were those available to prove inadequate. What is worse, we risk creating software developers with only a dim understanding of the differences between logarithmic, linear, quadratic, and exponential behavior. Experiments grounded in implementation of different data structures drive these concepts home in a way that no abstract use ever can.
I am not arguing for a return to the days of "here are three ways to implement a queue." Instead, I believe that implementation variations can be presented in the context of solving useful problem – say one involving dictionaries. In this way, we can use the implementation experiments to drive home the importance of separating the interface from the internal details; of providing plug-compatible components with different time/space tradeoffs; and of recognizing the different issues involved in developing and integrating components. The challenge for us as educators is to find a way to balance these issues so that the students we educate can specify, use, develop, and analyze the data structures – as a first step towards becoming competent component engineers and component integrators.