IB Computer - Abstract Data Types

Abstraction

A model of a system that includes only necessary details for the user, hiding the complexity of the actual implementation.

Abstract Data Type (ADT)

Provides a collection of data and operations that act on the data, allowing usage without knowledge of implementation details.

List ADT

Represents a collection of data with defined operations like insert, remove, clear, contains, indexOf, get, size, and toString.

Stack ADT

Structures where elements are added and removed from the same end, following Last In First Out (LIFO) principle.

Queue ADT

Structures where elements are added to one end and removed from the other, following First In First Out (FIFO) principle.

Set ADT

Represents a collection of unique elements with operations like add, remove, contains, union, intersection, difference, size, isEmpty, and clear.

Map/Dictionary ADT

Represents key-value pairs with operations like put, get, remove, containsKey, containsValue, keySet, values, entrySet, size, isEmpty, and clear.

Features of ADT

Key features include Abstraction, Better Conceptualization, Robustness, Encapsulation, Data Abstraction, Data Structure Independence, Information Hiding, and Modularity.

Advantages of ADT

Encapsulation, Abstraction, Data Structure Independence, Information Hiding, and Modularity provide benefits in managing and working with data structures.

Disadvantages of ADT

Overhead, Complexity, Learning Curve, Limited Flexibility, and Cost are challenges associated with implementing and using ADTs.

Information Hiding

The complexity and details of actual implementation should be hidden from the user informal

Information 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.

StringList

Contains a (possibly empty) collection of objects of type String.

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.

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.

CharStack

Contains a (possibly empty) collection of objects of type Character.

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.

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.