Interfaces

In this lesson, we look at the operations supported by the most commonly used data structures. Anyone with a bit of programming experience can see that these operations are not hard to implement correctly. It should be considered required reading.

When discussing data structures, it is important to understand the difference between a data structure’s interface and its implementation. An interface describes what a data structure does, while an implementation describes how the data structure does it.

Interface versus implementation

An interface, sometimes also called an abstract data type, defines the set of operations supported by a data structure and the semantics, or meaning, of those operations. An interface tells us nothing about how the data structure implements these operations; it only provides a list of supported operations along with specifications about what types of arguments each operation accepts and the value returned by each operation.

A data structure implementation, on the other hand, includes the internal representation of the data structure as well as the definitions of the algorithms that implement the operations supported by the data structure. Thus, there can be many implementations of a single interface. For example, we can implement List interface using arrays and we can also implement it using pointer-based data structures. Each implements the same interface, List, but in different ways.