Abstraction is the computer scientist s tool to master complexity. The more closely the implementations map to the abstract views of the data structures, the more elegant and flexible the implementations will be. This paper describes how object-oriented design patterns shape our thinking and aid us in designing data representations to the degree of abstraction we desire. By focusing on common data structures such as lists and trees, it illustrates how these patterns help narrow the gap between the abstract views of the data structures and their concrete implementations. The patterns also help exploit polymorphism in an effective way and keep control structures to a minimum.
Code complexity is reduced, and the overall complexity of the system becomes more manageable.
Section 2 examines lists and trees and views them as special cases of container classes. They are systems of objects that have states and that can change states dynamically. The key is to encapsulate the states of a system as classes. This calls for the state pattern. Section 3 describes in some details the state pattern and the null-object pattern, and applies them to partially implement the linked list structure.