Abstract data types (ADT)
A description of information and a collection of operations on that information. The information is accessed only through the operations.
- Data Structure: how the information is stored
- Algorithms: how the operations are performed
A user defined class which bundles together data about the class and operations on it (e.g. stack, linked list). The point is to make the compiler catch illegal values in the class and illegal operations on it (programming errors) as type errors.
Also learned in CS138 - Introduction to Data Abstraction and Implementation. Defined as a mathematical structure that has well-defined and widely recognizable behaviour.
- Contains data that may be accessed only in a prescribed manner, by a set of named operations
- Each operation has
- A signature, which describes the params + the type of the returned value
- A pre-condition that specifies wha tis assumed to be true before the operation may be applied
- A post-condtion that describes the value / effect of the operation
#@# Examples of ADTs
- Vector / sequence is an ordered data container that allows random access to individual elements, but allows adds/deletes only at the end.
- Stack is an ordered data acontainer with LIFO policy on inserts/deletes.
- But no random access to arbitrary elements.
- Queue is an FIFO
- No random access to arbitrary elements.
- Set
- Dictionary/Map
C++ Standard Library has implementations of theses and many more! So no need to implement from scratch. Just use them.
Data Structures
- Array
- Stack
- Linked List
- Hash Table
- Graph
- Binary Tree
- Binary Search Tree
- B-Tree
- Tuple
- Priority Queue
- Skip List
- AVL Tree
- Red-Black Tree
Data structure is used to implement ADTs.
