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.