An abstract data type is a collection of well-defined operations that can be performed on a particular structure. The operations define what the data type does, but not how it works. Abstract data types are black boxes that we dare not open when we design algorithms that use them.
For each of the most important abstract data types, several competing implementations, or data structures, are available. Often, alternative data structures realize different design tradeoffs that make certain operations (say, insertion) faster at the cost of other operations (say, search). In some applications, certain data structures yield simpler code than other implementations of a given abstract data type, or have some other specialized advantages.
We assume that the reader has had some previous exposure to elementary data structures and some fluency in pointer manipulation. Therefore, we do not discuss these topics here. The reader who wants to review elementary data structures is referred to any of the books in Section . Instead, we focus on three fundamental abstract data types: containers, dictionaries, and priority queues. Detailed discussion of the tradeoffs between implementations of these data types is deferred to the relevant catalog entry.