Abstraction is our way to mastering complexity. Applying object-oriented patterns to the design of data structures and the development of algorithms teach students about getting the right abstraction, finding an implementation that most closely matches it. We illustrate this process by focusing on something as simple as a list.

A list can be viewed as system with two states: empty and non-empty. The list can change state dynamically and behaves differently in each of the states as if it changes classes. The state pattern offers a flexible and elegant design solution to implement this behavior for languages that do not support dynamic reclassification. The idea here is to encapsulate the concrete states into disjoint subclasses of a common abstract state class, and let the list maintain a reference to this abstract state. All the list has to do is to delegate all requests to its state. Polymorphism properly dispatches all requests dynamically to the current state, eliminating control statements, and reducing code complexity. As a result, algorithms on a list are easier to understand and manage.

Instead of bundling the list with as many methods as we can think of in advance, we seek to keep a minimal and complete set of behaviors for the list and endow it with the capability of executing any algorithm, past, present, and future. This can be achieved by applying the visitor pattern. In this pattern, the list plays the host, and the algorithms are concrete implementations of a common visitor interface. This visitor interface consists of two abstract methods: one for the empty state of the host, and one for the non-empty state. The list only provides intrinsic structural behaviors and a hook to accept any algorithm visitor. By delegating all requests to its state, the list will in effect call the correct visitor method at run time. As such, the list has evolved into a flexible and extensible framework, albeit a miniature one.

It may not be easy for students to fully comprehend and appreciate the power of abstraction if they are not shown what they are abstracting from. Thus, in order to effectively help students develop the skill to abstract, we must find ways to lead them through the whole process as illustrated in the above, instead of just presenting to them the final and polished product.