CMPUT 175

Introduction to Foundations
of Computing
ADT: Abstract Data Types

You should view the vignettes:

Abstract data Types
Concept of Encapsulation
Encapsulation, the Gearbox example
Post-test Stacks

January 29, 2024 © Osmar R. Zaïane : University of Alberta 1

 Objectives
In this lecture we will discuss Abstract Data
Types.

We will talk about data structures, the

implementation of Abstract Data Types.

We will learn how to create data types and

describe their properties and operations
independently of any implementation

January 29, 2024 © Osmar R. Zaïane : University of Alberta 2

 Data Types
You are by now acquainted with data types
like Integers, Strings, Booleans, and so on.

To access the data, you use operations

defined in the programming language
(Python) for the data type.

For instance by accessing list elements in

Python, you would use the square bracket
notation myList[i]
January 29, 2024 © Osmar R. Zaïane : University of Alberta 3
 Type Definitions
Selecting a type for a variable determines
the possible values for that variable; the
operations that can be done on it; and the
meaning of the data.
We might want to define data with complex
data structures that are not readily provided
by the programming language
We might want to enrich the behaviour
(operations) of an existing data type.
January 29, 2024 © Osmar R. Zaïane : University of Alberta 4
The need for more data types
Software evolve as a result of new
requirements or constraints.
A modification to a program commonly
requires a change in one or more of its
data structures.
A new field might be added to a personnel
record to keep track of more information;
a list might be replaced by some other
structure to improve the program's
efficiency
January 29, 2024 © Osmar R. Zaïane : University of Alberta 5
 The need for isolation
If a data structure is changed or its behaviour
(interface) enhanced due to Software evolution or
new requirements, maintenance of the software can
become expensive if we need to revisit all the
program.
By separating the implementation of a data
structure and its behaviour from the implementation
of the program that uses this data structure we
minimize impact of change.
You don't want a change in a data structure to
require rewriting every procedure that uses the
changed structure.
January 29, 2024 © Osmar R. Zaïane : University of Alberta 6
 Abstract data types
What does ‘abstract’ mean?
We make abstraction of the implementation of
the data structure.
We hide the details of the implementation and
show only the possible operations (interface).
We talk about encapsulating the data
structure.
Implementation
of data structure
Access the data via
interface (behaviour) and
never directly to data Implementation
structure implementation of behaviour
January 29, 2024 © Osmar R. Zaïane : University of Alberta 7
 Concrete examples

You don’t need to know You don’t need to know You don’t need to know
how the engine works, how calculators handle how the phone does
the mechanics of the operations in order to use establish connections and
gearbox, etc. in order to the calculator for even transmits voice in order
drive the car. complex reckoning. to use it.
You need to know You need to know You need to know how to
how to use the clutch how to operate the dial and where is the
speakerphone and the
and how to shift provided buttons and microphone, etc.
gears, etc. functions, etc.
January 29, 2024 © Osmar R. Zaïane : University of Alberta
Interface 8
 Ford Model A

https://www.mecum.com/

Who knows how a 1924 Ford Model T is driven?

January 29, 2024 © Osmar R. Zaïane : University of Alberta 9

 ADT Example: Floating point
numbers
You don't need to know how floating point
arithmetic is implemented to use float
Indeed, the details can vary depending on processor,
even virtual coprocessor.
But the compiler hides all the details from you--some
numeric ADTs are built-in
All you need to know is the syntax and meaning of
operators, +, -, *, /, etc.
Float Result
Operator

Hiding the details of the implementation is called

encapsulation (data hiding)
January 29, 2024 © Osmar R. Zaïane : University of Alberta 10
 Other Existing encapsulated
structures

Python provides a built in structure list

You do not need to know how Lists are
implemented in order to use them.
All you need to know is the interface, the set of
provided methods to use and manipulate the list
list.append(x) Add an item to the end of the list;
list.extend(L) Extend the list by appending all the items in the given list;
list.insert(i, x) Insert an item at a given position.
list.remove(x) Remove the first item from the list whose value is x.
list.pop([i]) Remove the last item in the list or the item at the given position in the list, and return it.
list.index(x) Return the index in the list of the first item whose value is x.
list.count(x) Return the number of times x appears in the list.
list.sort() Sort the items of the list, in place.
list.reverse() Reverse the elements of the list, in place.

January 29, 2024 © Osmar R. Zaïane : University of Alberta 11

ADT = properties + operations
An ADT describes a set of objects sharing the
same properties and behaviors
The properties of an ADT are its data (representing
the internal state of each object
double d; -- bits representing exponent & mantissa are its
data or state 12.987654321  12987654321 x 10 -9

The behaviors of an ADT are its operations or

functions (operations on each instance)
sqrt(d) / 2; //operators & functions are its behaviors

Thus, an ADT couples its data and operations

OOP emphasizes data abstraction

January 29, 2024 © Osmar R. Zaïane : University of Alberta 12

Formal, language-independent ADTs
An ADT is a formal description, not code;
independent of any programming language
Why is code independence a good idea?

Promotes design by contract:

Specify responsibilities of suppliers and clients
explicitly, so they can be enforced, if necessary

January 29, 2024 © Osmar R. Zaïane : University of Alberta 13

 Example: Bags and Sets
Simplest ADT is a Bag (sets with duplication)
items can be added, removed, accessed
no implied order to the items
duplicates allowed

Set
same as a bag, except duplicate elements are
not allowed
union, intersection, difference, subset
January 29, 2024 © Osmar R. Zaïane : University of Alberta 14
 Example: Stacks
Collection with access only to the last
element inserted
New Data Data5
Push Pop

Last in - first out (LIFO)

Add element: push
Remove element: pop
top
is empty Think of when you are
browsing the web. The
browser pushes the visited

make empty URLs on a stack. The

back button pops them
back.

January 29, 2024 © Osmar R. Zaïane : University of Alberta 15

 Other examples of ADT

Lists Binary search trees

Queues B trees
Deque Maps
Pile (sorted deque) Graphs
Trees …
Heaps

January 29, 2024 © Osmar R. Zaïane : University of Alberta 16

Abstraction and Implementation

ADT represents a specification

Cannot be used directly in programming
The physical implementation of an ADT is
referred to at Data Structure
Data Structure=Implementation of ADT
In O-O programming, the implementation
of choice for an ADT is the creation of a
new class
Methods implement behaviour (operations)
January 29, 2024 © Osmar R. Zaïane : University of Alberta 17
 Data Structures
A Data Structure is:
an implementation of an Abstract Data Type and
"An organization of information, usually in
computer memory", for better algorithm
efficiency."
List Object
aList
size 5
myElements
0 1 2 3 4 5 6 7 8 9 10
A C E B A
January 29, 2024 © Osmar R. Zaïane : University of Alberta 18
 Data Structure Concepts
Data Structures are containers:
they hold data
Different types of data structures are
optimized for certain types of operations
Linear data structures are containers of data
collections with ordered items. They differ on
how items are added and removed.
Linear structures have two ends: Front and
Rear (or Top and Bottom) (or Head and Tail)
Linear structures are containers that differ on
the location their items are added or removed
January 29, 2024 © Osmar R. Zaïane : University of Alberta 19
 Core Operations
Data Structures will have 3 core operations
a way to add things
Mutators or setters
a way to remove things
a way to access things Accessors or getters
Details of these operations depend on the
data structure
Example: List, add at the end, access by location,
remove by location
More operations added depending on what
data structure is designed to do

January 29, 2024 © Osmar R. Zaïane : University of Alberta 20

 Mutator and Accessor
A mutator method is a method used to control
changes to a variable
It is also called a setter because it sets the value of a
variable.
Based on the principle of encapsulation a member’s
variable of a class is made private to hide and protect
it from other code.
A public mutator method gets a new value as
parameter, validates it (optionally) and assigns it to
the private member variable.
An accessor method returns the value of a member
variable without altering it.
It is also called a getter because it gets the value.
January 29, 2024 © Osmar R. Zaïane : University of Alberta 21
 Examples we saw
Instance from Class Template
template
Displays the template show()
dashes
Changes the template
position with
update(word,character) List
character if in word Returns True/False
Checks whether all isFull()
letters are guessed
Returns True/False
hangman Instance from Class Gallows
Displays the gallows show()
Inquires about the get() step
number of wrong
guesses Returns Integer
Integer
Adds 1 to step increment()
January 29, 2024 © Osmar R. Zaïane : University of Alberta 22
 ADTs and Data Structures in
Programming Languages

Modern programming languages

usually have a library of data structures
Java collections framework
C++ standard template library
Python lists, tuples, sets and dictionaries
Lisp lists

January 29, 2024 © Osmar R. Zaïane : University of Alberta 23

 Object Concepts
Remember:
An object has: The implementation of
choice for an ADT is the
A private state creation of a new class.

A set of resources that it provides.

Class stickman

Let’s call this its public protocol

Each object is an instance of a class.
The class defines the public protocol, so all
objects of a class have the same protocol.
The state of an object differentiates it from
other objects in the same class.
January 29, 2024 © Osmar R. Zaïane : University of Alberta 24
Instances of class stickman
Object Class, Protocol and
State

Private
state
external request
Public protocol

class

January 29, 2024 © Osmar R. Zaïane : University of Alberta 25

 What getters and setters
should not do
To enforce encapsulation and data hiding, it is bad practice
to have getter and setter methods expose the members
properties (private state of objects).

The exposed methods (public protocol) should act on the

object to change its private state (setter or mutator) or act
on the object to provide its data (getter or accessor)
without exposing its implementation or properties.

Outside the class, only the interface is known, while the

implementation of the data structure is unknown (hidden).

January 29, 2024 © Osmar R. Zaïane : University of Alberta 26