Abstract Data Type
What is ADT?
-
An Abstract Data Type (ADT) is a collection of behaviors.
-
An abstract data type is a data type that is packaged with the data type's relevant operations.
-
Example: List ADT
-
insert(L, x): Adds an item, x, of type “BaseType” to the List L. Where to insert?
-
get(L, index): Return an element from the list L at any given position “index”.
-
remove(L): Remove the first occurrence of any element from a non-empty list.
-
removeAt(L, index): Remove the element at a specified location “index” from a non-empty list.
-
replace(L, index, y): Replace an element at any position “index” with another element y.
-
size(L): Return the number of elements in the list L.
-
isEmpty(L): Return true if the list L is empty, otherwise return false.
-
isFull(L): Return true if the list L is full, otherwise return false.
-
Difference between ADT and Data Structures?
-
An Abstract Data Type (ADT) represents a particular set of
behaviors. -
whereas, a data structure is more concrete. Typically, it is a technique
or strategy for implementing an ADT. -
Examples of ADTs are Stack, queue, priority queue, dictionary, lists, set, etc.
-
data structures used to implement those ADTS:
– array, linked list, a hash table (open, closed, etc.)
– trees (binary search trees, heaps, AVL trees, 2-3 trees, B-trees,
etc.)
Characteristics of Abstract Data Types:
-
Data: ADTs define the type of data they store. For example, an ADT might define a data type called "Stack" that stores elements.
-
Operations: ADTs specify a set of operations or methods that can be performed on the data. These operations define how you interact with the data. Common operations include "insert," "delete," "search," and "retrieve."
-
Encapsulation: ADTs encapsulate the data and operations within a single unit. This encapsulation hides the internal details and exposes only the necessary interfaces to the user.
-
Information Hiding: ADTs hide the implementation details from the user, allowing the data structure to be changed or optimized without affecting the code that uses it.
