Using Interface Inheritance to Structure the Data Structures Course

Traditional instruction in the first data structures course treats object-oriented inheritance and polymorphism as isolated topics if at all. Course organization is an exploration of the plethora of commonly used implementation structures, along with analysis of their run-time costs and benefits. This paper examines an alternative organization of this course that uses inheritance and polymorphism as the primary means for organizing presentation and student projects in implementation, testing and application of data structures. Abstract sequence, map and set interfaces provide a conceptual and code-concrete framework within which students implement and extend arrays, linked lists, trees, hash tables, iterators and other structures. Reuse of student design and code modules fits seamlessly into this organization, saving time and effort and reinforcing the utility of reused classes. Achieving working exposure to type-generic container classes and class libraries is straightforward. The initial offering of a data structures course using this organization has been a success