abstract data types - note

An abstract data type (ADT) is a type of data structure that specifies a set of values and the operations that can be performed on those values. It is a theoretical concept that serves as a template for implementing data structures in a programming language.

An ADT defines the logical properties and behavior of a data type, independent of any particular implementation. For example, the ADT "stack" specifies a collection of values that can be added and removed in a last-in, first-out (LIFO) manner. The ADT does not specify how the stack should be implemented (e.g. using an array or a linked list), but rather just defines the operations that can be performed on the stack (e.g. push, pop, peek).

There are many different types of ADTs, including lists, queues, stacks, sets, maps, and graphs. Each ADT has its own set of operations that can be performed on it, and these operations may have different time complexities depending on the implementation.

Using ADTs allows for a separation of concerns between the logical properties of a data type and its physical implementation, making it easier to design and maintain software systems. It also enables the use of different implementations for the same ADT, depending on the specific needs of a given application.