Data structures #

We saw in the dedicated chapter that and abstract data type is a high-level interface that exposes a collection of values or objects. Examples include a list, a set, or an associative array. Abstract data types allow treating such collections as basic mathematical objects or structure, like a set, tuple, function, etc.

There are multiple ways to implement an abstract data type. Each implementation may have its benefits and drawbacks in terms of performance, depending on the operations that are performed on the collection:

• search,
• insertion
• deletion,
• etc.

Some implementations may provide additional guarantees, such as maintaining an order on its elements (e.g. order of insertion or some user-defined order).

In this chapter, we introduce a few elementary data structures, which are available (in one form another) in most modern programming languages.

In order to estimate their respective performance, we will rely on the on the notion of asymptotic cost, adopting the RAM cost model.