Data structures organize data stored in memory so that it is quickly and usefully accessible. They are the building blocks of efficient algorithms. The greatest majority of algorithms rely on one or more of the data structures covered here1. Regardless of the domain, it’s highly probable that every software professional will need to both implement and design new data structures on a regular basis. As such, it’s highly recommended that readers master this material before moving on.
One concept to keep in mind is the difference between a data structure’s abstract interface and its concrete implementation. There are typically many possible concrete implementations that satisfy an abstract interface. A full treatment of all possible implementations is beyond the scope of this work. The topic merits deeper exploration.
Abstract Interface
A common cause of confusion is the difference between an abstract interface and it’s concrete implementation. As the name implies, an abstract interface is the methods via which a consumer interacts with a data structure in strictly functional terms. Stated differently, interfaces dictate behavior. They do not dictate non-functional attributes such as performance2. Those qualities arise as a consequence of the concrete implementation.
The concept is analogous to a vehicle. The steering wheel, pedals, and gear shift comprise the interface. The engine is the concrete implementation. It’s possible to increase the horse power of a vehicle without changing the interface. For a more intimate example, consider the previous section on list data structures. Each of them exhibit the same methods, that is the list interface. However, each concrete implementation (array, linked list, binary tree) has different run-time characteristics.
The description of each data structure in this section describes its abstract interface. As such, the pseudo code is far less precise than the previous section’s. Also provided with each data structure is a single concrete implementation representing an ideal asymptotic complexity. Keep in mind that it’s one of many and it’s easy to inadvertently alter the run-time characteristics when applying data structures to different contexts.
Source Code
Relevant Directories:
-
Including the data structures from this section as well as those introduced in the list data structures section. ↩
-
Most mainstream languages come equipped with implementations of standard data structures: the details of which are opaque. This is an important consideration for performance critical applications because the run-time isn’t guaranteed. ↩