ADTs and Specification Flashcards
What is a Data Structure
A collection of data elements with defined relationships between them
What characteristics does a data structure of a list usually have?
- The data elements are usually all of the same kind: integers, real numbers, character strings, or even a compound data type
- In a list, the relationship between elements (the structure) is that each element has a rank in a linear ordering of elements
What characteristics does a data structure of a tree usually have?
- The elements are of the same kind
- The relationship between elements is a hierarchical one: each element has a parent, and zero or more children.
What is a data type?
Simply describes the kind of data (e.g., integer, floating point, character string) and how it is interpreted in memory.
- It doesn’t involve a collection of elements or relationships between them.
What is an ADT (Abstract Data Type)?
An abstraction that allows programmers to use a data structure without needing to know its internal implementation details.
What are the components of an ADT?
- One or more data structures
- A set of publicly known operations on the data structure(s)
- Encapsulation (hiding) of the data structures and the implementation of the operations
What is the data structure, operations, and encapsulation of a string ADT?
- The data structure: an array, or list of characters (users of the string ADT don’t have to care which!)
- The operations (interface): create, compare, concatenate, convert to upper-case, etc.
- The encapsulation: implementation and underlying data structure are hidden in a library (e.g. a Java String object).
What is the data structure, operations, and encapsulation of a list ADT?
- The data structure: an array, or singly linked list, or doubly linked list, etc.
- The operations (interface): add at beginning, add at end, find element in list, delete n-th element, delete element equal to e, etc.
- The encapsulation: implementations of the operations and the choice of data structure are hidden in the software implementation
What is the data structure, operations, and encapsulation of a integer ADT?
- The data structure: a sequence of bits — might be 1’s complement representation, 2’s complement representation, signed magnitude representation; byte order might be big endian, little endian, doesn’t matter; Hidden implementations of the operations take care of everything.
- The operations (interface): +,−, /,×, . . . , %, ≤, ≥, ==, etc.
- The encapsulation: details of operations and choice of binary representation are hidden in hardware
What are two advantages of using ADTs?
- Specify expected behaviour before implementation: Allows independent development and implementation of different ADTs, promoting reusability through a well-documented interface.
- Postponement of unnecessary details: Enables focusing on the overall program design without getting bogged down in the specific implementation details of the ADT (e.g., whether a tree uses an array or linked list for storing children).
- Programming language independence: The specification of an ADT can be designed independently of any programming language, allowing for flexibility in choosing the most suitable language later in the development process.
Benefits of Encapsulation?
- Reduced coupling: Coupling refers to the degree of dependency between code modules. Encapsulation through ADTs lowers coupling, making the code more modular and adaptable to changes in the ADT implementation. For example, changing from a singly linked list to a doubly linked list in the ADT won’t require changes in the module using the list ADT.
- Increased cohesion: Cohesion refers to how closely related the components of a code module are. ADTs promote higher cohesion as the code within the ADT module is focused on implementing the ADT’s functionality.
What is the purpose of ADT Specification?
To define the expected behaviour of an ADT in a programming-language-independent way, serving as a contract between the ADT and its users
What is the focus of ADT Specification?
Outlines the inputs, outputs, and semantics of each ADT operation without dictating implementation details like programming language, data types, data structures, or algorithms.
What are the components of ADT specification?
- Name of the ADT
- Definition of sets used: Includes the set of all ADT instances, the set of allowed elements, and any other relevant sets (e.g., Booleans).
- Signatures of operations: Expressed as functions using mathematical notation, indicating the input and output sets for each operation.
- Preconditions: Conditions that must be met before an operation can be applied.
- Semantics: Description of what each operation does.
