DSA Notes: Data Abstraction

Page 1

Data Abstraction

Definiton

Process of separating the properties of data from its non essential implementation details.

Hence, properties are those visible to client code that uses the data while implementation details are kept entirely hidden.

Benefits

Reduces complexity of large programs

Supports modular program development(easy to read, write and modify)

Page 2

Data Structures & Algorithms

Data Structures

are schemes or ways in which data is organized (in the computer memory) e.g. array, list, queue, stack, set, tree, graph

Algorithms

are operations use to process the data in a data structure e.g. list : add, insert, delete, get queue : enqueue, dequeue, front

Data structures and algorithms are closely linked, as the way in which data is organized will determine the type of operations that can operate on them

Page 3

Abstract Data Types

Definition

the abstraction of a data structure where the specification (interface) is separated from its implementation.

Implementation

An Abstract Data Type is implemented as a class in C++ where

specification (interface) is placed in a header file (xxx.h)

implementation is placed in an implementation file (xxx.cpp)

Steps

1. Identify and list the operations required for the ADT

list of operations

2. Specify the operations (interface)

function headers of the operations (xxx.h)

3. Implement the operations

implementation of the operations (xxx.cpp)

*Specification

The specification of an ADT operation should include the following information:

Purpose

to specify what it is supposed to do

2. Precondition

to specify the condition that must be met for the operation to work correctly

3. Postcondition

to specify what happens (the result) when the operation is executed

i.e.

// check the size of the list

// pre : none

// post: none

// return the number of items in the list

Page 4

List ADT

Definition

is a collection of items

items are referenced by their position in the list

position starts from 1 (not 0)

new items can be added to any position in the list

items can be removed from any position in the list

Steps for List ADT

1. Identify and list the operations required for the List ADT

create an empty list

add an item to the end of the list (append)

add an item at a given position in the list (insert)

remove an item at a given position in the list

get the item at a given position in the list (retrieve)

check whether the list is empty

check the number of items in a list

2. Specify the List ADT interface

List()

add(ItemType item):boolean

add(int index, ItemType item):boolean

remove(int index):void

get(int index):ItemType

isEmpty():boolean

getLength():int

3. Implement the List operations

implementation of the operations for the List ADT (List.cpp)

Page 5

Array based List Implementation

s

Page 6