Abstract Data Types

CMPUT 175 Introduction to Foundations of Computing

ADT: Abstract Data Types

  • Post-test: Review vignettes on:

    • Abstract Data Types

    • Concept of Encapsulation

    • Encapsulation, the Gearbox example

    • Stacks

Objectives

  • Discussion points:

    • Abstract Data Types (ADTs)

    • Data structures and their implementation

    • Creating data types independent of implementation details

    • Describing properties and operations of data types

Data Types

  • Familiar data types: Integers, Strings, Booleans

  • Accessing data operations:

    • In Python, use square bracket notation (e.g., myList[i]) to access list elements

Type Definitions

  • Selecting a variable type defines:

    • Possible values for that variable

    • Operations applicable on it

    • Meaning of the data

  • Need to define complex data structures and enhance existing data types

Example: Datetime Type

  • Common operations on a datetime type include:

    • Replacing year, month, day, time zone

    • Retrieving year, month, day, hour, minute, weekday

    • Conversion to string

    • Date manipulation using datedelta() and timedelta()

  • Details on datetime package not critical to the current stage.

The Need for More Data Types

  • Software evolution requires new data structures to handle updated requirements

  • Changes to programs often involve modifying existing data structures (e.g., adding fields to personnel records)

The Need for Isolation

  • Changes in data structures or behavior (interface) can lead to high maintenance costs

  • Minimize impact of changes by separating data structure implementation from program implementation

  • Avoid rewriting procedures that use the altered data structure

Abstract Data Types

  • Definition: Abstraction hides details of data structure implementation, exposing only possible operations (interface)

  • Encapsulation allows accessing data only via the interface, not directly.

Concrete Examples of ADTs

  • Usage analogy:

    • Driving a car: Understanding use without knowing engine mechanics

    • Using a calculator: Operations without knowing internal computations

    • Operating a phone: Knowing how to function without understanding inner workings

Example: Floating Point Numbers

  • Floating point arithmetic is an ADT; users need not understand its implementation

  • Encapsulation hides implementation details from users; focus on operators like +, -, *, /

Existing Encapsulated Structures

  • Python's built-in list functions without needing to understand their implementation:

    • list.append(x): Add item to end

    • list.extend(L): Append items from list L

    • list.insert(i, x): Insert item at position i

    • Other operations: remove(), pop(), index(), count(), sort(), reverse()

ADT = Properties + Operations

  • Definition: ADT comprises objects sharing properties and behaviors

  • Properties represent internal data state (e.g., double d)

  • Behaviors represent operations on data (e.g., sqrt(d) / 2)

  • Focus on OOP principles: data abstraction

Formal Language-Independent ADTs

  • ADTs serve as formal descriptions, independent of programming languages

  • Benefits include promoting design by contract, specifying responsibilities for suppliers and clients

Examples of ADTs: Bags and Sets

  • Bags: Can have duplicates, allow addition, removal, access, no order

  • Sets: Similar to bags but do not allow duplicate elements; can perform union, intersection, difference, subset operations

Example: Stacks

  • Definition: Collection with access only to the last element inserted (Last In - First Out)

  • Operations:

    • Push: Add an element

    • Pop: Remove the element from the top

    • Example of usage: Browser history management with back button

Other Examples of ADTs

  • Additional structures:

    • Lists

    • Queues

    • Deques

    • Trees

    • Heaps

    • Binary search trees

    • Maps

    • Graphs

Abstraction and Implementation

  • ADTs are specifications that cannot be used directly in programming

  • Implementation of an ADT is called a Data Structure

  • In OOP, create a new class to implement an ADT

Data Structures

  • Definition: Implementation of an ADT and organization of information in memory for better efficiency

Data Structure Concepts

  • Data Structures as containers: hold data organized for specific operations

  • Linear data structures: collections with ordered items

  • Different structures optimize for different operations, defined by how items are managed

Core Operations

  • Essential operations of Data Structures:

    • Add items

    • Remove items

    • Access items

  • Operation details vary based on Data Structure type (e.g., List)

Mutator and Accessor Methods

  • Mutator: Controls changes to a variable (setter)

    • Sets a value, validates it, and updates the variable

  • Accessor: Returns the value of a variable (getter)

    • Provides data without alteration

Examples of Templates and Instances

  • Usage of templates and instances from classes:

    • List instance: Functions include show(), update(word, character)

    • Integer instance: Functions include increment(), hangman()

ADTs and Data Structures in Programming Languages

  • Modern languages include libraries for data structures:

    • Java: Collections framework

    • C++: Standard Template Library

    • Python: Lists, tuples, sets, dictionaries

    • Lisp: Lists

Object Concepts

  • Objects exhibit:

    • Private state

    • Public protocol for interaction and resource access

  • Every object is an instance of a class; shared protocol among instances

  • State of an object differentiates instances of the same class

Getters and Setters Best Practices

  • Avoid exposing member properties directly through getters and setters

  • Ensure public interface methods modify or retrieve data without revealing implementation details

  • Interface knowledge is available outside the class, but data structure implementation remains hidden.