The computing field has grown immensely since most of us were students. There is too much information now for any one person to be able to know the entire field in any real depth. In order to make room for new areas, we have to rethink what is fundamental information for our students to know. What is fundamental will also depend on the kind of student being taught in the courses. Are the students Computer Science majors, Computer Engineering majors, Information Science/Technology majors? Depending on the audience, the answer to the question "what is fundamental" will differ.
Here are some questions, and our views, on what is needed in the Data Structures area. Does every student in a data structures course need to know how to select an appropriate structure for the problem at hand, and understand its behavior? Absolutely. Does every student in a data structures course need to be able to develop each data structure from scratch? No. Do some students need to be able to develop these data structures from scratch? Yes. Someone has to develop the libraries for the new languages and environments that will developed in the future. Also, students that go into areas where speed and size are critical may need to develop their own structures in order to meet special needs.
At Rochester Institute of Technology (RIT), we've taken the approach of teaching the use of data structures to all students in our CS 1 and CS 2 courses, which serve Computer Science, Software Engineering, Computer Engineering, Biomedical Computing and Computational Math students. We use a robust, very comprehensive and consistent library provided with our language environment. We have found that students have a much better grasp of the abstract concepts when selection and use of a data structure is emphasized rather than how it is built. In a sophomore level course, we teach Computer Science and Software Engineering majors the details of implementation, as they are the ones likely to need to develop these structures in a new environment. By this time, they have had almost a year of using the structures, and can separate the implementation details from the abstract concepts. Other majors do not require this course, and continue on in the rest of the sequence with no apparent ill effects.