IB Computer - Abstract Data Types
Abstraction is a model of a system that includes only the details needed by the viewer/user of such system.
The complexity and details of actual implementation should be hidden from the user - that is called information hiding
An abstract data type (ADT) provides a collection of data and a set of operations that act on the data.
An ADT’s operations can be used without knowing their implementations or how the data is stored, as long as the interface to the ADT is precisely specified.
An ADT is implementation-independent and can be implemented in many different ways (and programming languages).
Two different ways of specifying an ADT:
informal specification - an English description that provides a list of all available operations on the data with their inputs and outputs;
formal specification - a Java interface definition that concrete classes can implement later.
We will be using ADTs from three different perspectives:
application level (or user, or client): using a class for which you only know the formal ADT specification;
logical level: designing the ADT itself given a set of requirements specified by the non-programmer user (this may involve asking questions);
implementation level: writing code for a class that implements a given ADT.
Many different possible List abstract data types require different sets of operations to be defined on them.
The ADT for the list we define in this lecture is very general. We will use it (after slight revisions) in several future lectures and provide different ways of implementing the list interface.
For now, we will specify List ADTs that expect objects of a specific type.
Later, we will revise the List ADT to be general enough to work with any chosen type of objects, i.e., we will define a generic List ADT.
Example: StringList ADT - Informal Specification
The StringList contains a (possibly empty) collection of objects of type String. The list supports the following operations:
insert: This operation adds a String object, given as a parameter, to the list of strings.
remove: This operation removes a String object, given as a parameter, from the list of strings. If the given String object is not on the list, the list content does not change.
clear: This operation removes all objects from the list. The list becomes empty.
contains: This operation determines whether a String object, given as a parameter, is stored in the list. It returns true or false, accordingly.
indexOf: This operation determines the index (or location) of a String object, given as a parameter. It returns -1 if the given String object is not stored in the list. (The indeces do not imply any ordering of the objects in the list and may have different value depending on the implementation of this ADT).
get: This operation returns an object stored at the index/location given as a parameter.
size: This operation determines the number of objects stored in the list.
toString: This operation produces a meaningful String representation of the list.
Stacks are structures in which elements are always added and removed from the same end (depending on how you visualise the stack, you may wish to think of that end as the top of the stack).
Stacks are last in first out (or LIFO) structures.
Example: CharStack ADT - Informal Specification
The CharStack contains a (possibly empty) collection of objects of type Character. The stack supports the following operations:
insert/push: This operation adds a Character object, given as a parameter, to the top of the stack of characters.
remove/pop: This operation removes and returns a Character object from the top of the stack of characters.
peek: This operation returns a Character object from the top of the stack of characters.
toString: This operation produces a meaningful String representation of the stack.
Queues are structures in which elements are added to one end (rear/back of a queue) and removed from the other end (front of a queue).
Queues are first in first out structures (FIFO).
Example:
ProcessQueue ADT - Informal Specification
insert/enqueue: This operation adds a Process object, given as a parameter, to the end of the queue of processes.
remove/dequeue: This operation removes and returns a Process object from the front of the queue of processes.
toString: This operation produces a meaningful String representation of the stack.
A Set ADT represents a collection of unique elements, meaning no duplicates are allowed.
Sets are used to test for membership, to eliminate duplicates, and to perform mathematical set operations.
Operations on Set ADT:
add(element): Adds an element to the set. If the element is already in the set, no change is made.
remove(element): Removes an element from the set if it exists.
contains(element): Checks if the set contains a specific element.
union(otherSet): Returns a new set containing all elements from both sets.
intersection(otherSet): Returns a new set containing only elements that are in both sets.
difference(otherSet): Returns a new set containing elements that are in the current set but not in the other set.
size(): Returns the number of elements in the set.
isEmpty(): Checks if the set is empty.
clear(): Removes all elements from the set.
Implementations on Set ADT:
Hash Set: Uses a hash table to store elements, providing average O(1) time complexity for add, remove, and contains operations.
Tree Set: Uses a balanced binary search tree (e.g., Red-Black tree) to store elements, providing O(log n) time complexity for add, remove, and contains operations. Elements are stored in sorted order.
Bit Set: Uses an array of bits to store elements, which is efficient for sets with a limited range of integer elements.
Applications on Set ADT:
Membership Testing: Quickly checking whether an element is part of a collection.
Removing Duplicates: Eliminating duplicate elements from a collection.
Mathematical Set Operations: Performing union, intersection, and difference operations in data analysis.
Database Operations: Implementing relational algebra operations in databases.
A Map ADT represents a collection of key-value pairs, where each key is unique, and each key maps to a value.
Maps are used for fast data retrieval based on keys.
Operations on Map/Dictionary ADT:
put(key, value): Associates the specified value with the specified key. If the key already exists, updates its value.
get(key): Returns the value associated with the specified key, or null if the key does not exist.
remove(key): Removes the key-value pair for the specified key if it exists.
containsKey(key): Checks if the map contains the specified key.
containsValue(value): Checks if the map contains one or more keys mapping to the specified value.
keySet(): Returns a set of all keys in the map.
values(): Returns a collection of all values in the map.
entrySet(): Returns a set of all key-value pairs in the map.
size(): Returns the number of key-value pairs in the map.
isEmpty(): Checks if the map is empty.
clear(): Removes all key-value pairs from the map.
Implementations on Map/Dictionary ADT:
Hash Map: Uses a hash table to store key-value pairs, providing average O(1) time complexity for put, get, and remove operations.
Tree Map: Uses a balanced binary search tree (e.g., Red-Black tree) to store key-value pairs, providing O(log n) time complexity for put, get, and remove operations. Keys are stored in sorted order.
Linked Hash Map: Maintains a doubly-linked list of the entries in the map, preserving the insertion order or access order, while providing O(1) time complexity for put, get, and remove operations.
Applications Map/Dictionary ADT:
Associative Arrays: Implementing associative arrays where values are accessed via keys, such as Python’s dict or JavaScript’s Object.
Configuration Management: Storing configuration settings in key-value pairs.
Caching: Implementing cache mechanisms where data can be quickly retrieved using keys.
Indexing: Creating indexes for databases and search engines to enable fast lookups.
Abstract data types (ADTs) encapsulate data and operations on that data into a single unit.
Some of the key features of ADTs include:
Abstraction: The user does not need to know the implementation of the data structure only essentials are provided.
Better Conceptualization: ADT gives us a better conceptualization of the real world.
Robust: The program is robust and has the ability to catch errors.
Encapsulation: ADTs hide the internal details of the data and provide a public interface for users to interact with the data.
This allows for easier maintenance and modification of the data structure.
Data Abstraction: ADTs provide a level of abstraction from the implementation details of the data.
Users only need to know the operations that can be performed on the data, not how those operations are implemented.
Data Structure Independence: ADTs can be implemented using different data structures, such as arrays or linked lists, without affecting the functionality of the ADT.
Information Hiding: ADTs can protect the integrity of the data by allowing access only to authorized users and operations.
This helps prevent errors and misuse of the data.
Modularity: ADTs can be combined with other ADTs to form larger, more complex data structures.
This allows for greater flexibility and modularity in programming.
Overall, ADTs provide a powerful tool for organizing and manipulating data in a structured and efficient manner.
Encapsulation: ADTs provide a way to encapsulate data and operations into a single unit, making managing and modifying the data structure easier.
Abstraction: ADTs allow users to work with data structures without having to know the implementation details, which can simplify programming and reduce errors.
Data Structure Independence: ADTs can be implemented using different data structures, which can make it easier to adapt to changing needs and requirements.
Information Hiding: ADTs can protect the integrity of data by controlling access and preventing unauthorized modifications.
Modularity: ADTs can be combined with other ADTs to form more complex data structures, which can increase flexibility and modularity in programming.
Overhead: Implementing ADTs can add overhead in terms of memory and processing, which can affect performance.
Complexity: ADTs can be complex to implement, especially for large and complex data structures.
Learning Curve: Using ADTs requires knowledge of their implementation and usage, which can take time and effort to learn.
Limited Flexibility: Some ADTs may be limited in their functionality or may not be suitable for all types of data structures.
Cost: Implementing ADTs may require additional resources and investment, which can increase the cost of development.
Abstraction is a model of a system that includes only the details needed by the viewer/user of such system.
The complexity and details of actual implementation should be hidden from the user - that is called information hiding
An abstract data type (ADT) provides a collection of data and a set of operations that act on the data.
An ADT’s operations can be used without knowing their implementations or how the data is stored, as long as the interface to the ADT is precisely specified.
An ADT is implementation-independent and can be implemented in many different ways (and programming languages).
Two different ways of specifying an ADT:
informal specification - an English description that provides a list of all available operations on the data with their inputs and outputs;
formal specification - a Java interface definition that concrete classes can implement later.
We will be using ADTs from three different perspectives:
application level (or user, or client): using a class for which you only know the formal ADT specification;
logical level: designing the ADT itself given a set of requirements specified by the non-programmer user (this may involve asking questions);
implementation level: writing code for a class that implements a given ADT.
Many different possible List abstract data types require different sets of operations to be defined on them.
The ADT for the list we define in this lecture is very general. We will use it (after slight revisions) in several future lectures and provide different ways of implementing the list interface.
For now, we will specify List ADTs that expect objects of a specific type.
Later, we will revise the List ADT to be general enough to work with any chosen type of objects, i.e., we will define a generic List ADT.
Example: StringList ADT - Informal Specification
The StringList contains a (possibly empty) collection of objects of type String. The list supports the following operations:
insert: This operation adds a String object, given as a parameter, to the list of strings.
remove: This operation removes a String object, given as a parameter, from the list of strings. If the given String object is not on the list, the list content does not change.
clear: This operation removes all objects from the list. The list becomes empty.
contains: This operation determines whether a String object, given as a parameter, is stored in the list. It returns true or false, accordingly.
indexOf: This operation determines the index (or location) of a String object, given as a parameter. It returns -1 if the given String object is not stored in the list. (The indeces do not imply any ordering of the objects in the list and may have different value depending on the implementation of this ADT).
get: This operation returns an object stored at the index/location given as a parameter.
size: This operation determines the number of objects stored in the list.
toString: This operation produces a meaningful String representation of the list.
Stacks are structures in which elements are always added and removed from the same end (depending on how you visualise the stack, you may wish to think of that end as the top of the stack).
Stacks are last in first out (or LIFO) structures.
Example: CharStack ADT - Informal Specification
The CharStack contains a (possibly empty) collection of objects of type Character. The stack supports the following operations:
insert/push: This operation adds a Character object, given as a parameter, to the top of the stack of characters.
remove/pop: This operation removes and returns a Character object from the top of the stack of characters.
peek: This operation returns a Character object from the top of the stack of characters.
toString: This operation produces a meaningful String representation of the stack.
Queues are structures in which elements are added to one end (rear/back of a queue) and removed from the other end (front of a queue).
Queues are first in first out structures (FIFO).
Example:
ProcessQueue ADT - Informal Specification
insert/enqueue: This operation adds a Process object, given as a parameter, to the end of the queue of processes.
remove/dequeue: This operation removes and returns a Process object from the front of the queue of processes.
toString: This operation produces a meaningful String representation of the stack.
A Set ADT represents a collection of unique elements, meaning no duplicates are allowed.
Sets are used to test for membership, to eliminate duplicates, and to perform mathematical set operations.
Operations on Set ADT:
add(element): Adds an element to the set. If the element is already in the set, no change is made.
remove(element): Removes an element from the set if it exists.
contains(element): Checks if the set contains a specific element.
union(otherSet): Returns a new set containing all elements from both sets.
intersection(otherSet): Returns a new set containing only elements that are in both sets.
difference(otherSet): Returns a new set containing elements that are in the current set but not in the other set.
size(): Returns the number of elements in the set.
isEmpty(): Checks if the set is empty.
clear(): Removes all elements from the set.
Implementations on Set ADT:
Hash Set: Uses a hash table to store elements, providing average O(1) time complexity for add, remove, and contains operations.
Tree Set: Uses a balanced binary search tree (e.g., Red-Black tree) to store elements, providing O(log n) time complexity for add, remove, and contains operations. Elements are stored in sorted order.
Bit Set: Uses an array of bits to store elements, which is efficient for sets with a limited range of integer elements.
Applications on Set ADT:
Membership Testing: Quickly checking whether an element is part of a collection.
Removing Duplicates: Eliminating duplicate elements from a collection.
Mathematical Set Operations: Performing union, intersection, and difference operations in data analysis.
Database Operations: Implementing relational algebra operations in databases.
A Map ADT represents a collection of key-value pairs, where each key is unique, and each key maps to a value.
Maps are used for fast data retrieval based on keys.
Operations on Map/Dictionary ADT:
put(key, value): Associates the specified value with the specified key. If the key already exists, updates its value.
get(key): Returns the value associated with the specified key, or null if the key does not exist.
remove(key): Removes the key-value pair for the specified key if it exists.
containsKey(key): Checks if the map contains the specified key.
containsValue(value): Checks if the map contains one or more keys mapping to the specified value.
keySet(): Returns a set of all keys in the map.
values(): Returns a collection of all values in the map.
entrySet(): Returns a set of all key-value pairs in the map.
size(): Returns the number of key-value pairs in the map.
isEmpty(): Checks if the map is empty.
clear(): Removes all key-value pairs from the map.
Implementations on Map/Dictionary ADT:
Hash Map: Uses a hash table to store key-value pairs, providing average O(1) time complexity for put, get, and remove operations.
Tree Map: Uses a balanced binary search tree (e.g., Red-Black tree) to store key-value pairs, providing O(log n) time complexity for put, get, and remove operations. Keys are stored in sorted order.
Linked Hash Map: Maintains a doubly-linked list of the entries in the map, preserving the insertion order or access order, while providing O(1) time complexity for put, get, and remove operations.
Applications Map/Dictionary ADT:
Associative Arrays: Implementing associative arrays where values are accessed via keys, such as Python’s dict or JavaScript’s Object.
Configuration Management: Storing configuration settings in key-value pairs.
Caching: Implementing cache mechanisms where data can be quickly retrieved using keys.
Indexing: Creating indexes for databases and search engines to enable fast lookups.
Abstract data types (ADTs) encapsulate data and operations on that data into a single unit.
Some of the key features of ADTs include:
Abstraction: The user does not need to know the implementation of the data structure only essentials are provided.
Better Conceptualization: ADT gives us a better conceptualization of the real world.
Robust: The program is robust and has the ability to catch errors.
Encapsulation: ADTs hide the internal details of the data and provide a public interface for users to interact with the data.
This allows for easier maintenance and modification of the data structure.
Data Abstraction: ADTs provide a level of abstraction from the implementation details of the data.
Users only need to know the operations that can be performed on the data, not how those operations are implemented.
Data Structure Independence: ADTs can be implemented using different data structures, such as arrays or linked lists, without affecting the functionality of the ADT.
Information Hiding: ADTs can protect the integrity of the data by allowing access only to authorized users and operations.
This helps prevent errors and misuse of the data.
Modularity: ADTs can be combined with other ADTs to form larger, more complex data structures.
This allows for greater flexibility and modularity in programming.
Overall, ADTs provide a powerful tool for organizing and manipulating data in a structured and efficient manner.
Encapsulation: ADTs provide a way to encapsulate data and operations into a single unit, making managing and modifying the data structure easier.
Abstraction: ADTs allow users to work with data structures without having to know the implementation details, which can simplify programming and reduce errors.
Data Structure Independence: ADTs can be implemented using different data structures, which can make it easier to adapt to changing needs and requirements.
Information Hiding: ADTs can protect the integrity of data by controlling access and preventing unauthorized modifications.
Modularity: ADTs can be combined with other ADTs to form more complex data structures, which can increase flexibility and modularity in programming.
Overhead: Implementing ADTs can add overhead in terms of memory and processing, which can affect performance.
Complexity: ADTs can be complex to implement, especially for large and complex data structures.
Learning Curve: Using ADTs requires knowledge of their implementation and usage, which can take time and effort to learn.
Limited Flexibility: Some ADTs may be limited in their functionality or may not be suitable for all types of data structures.
Cost: Implementing ADTs may require additional resources and investment, which can increase the cost of development.
