Data Structures Lecture Notes

Why Object-Oriented Programming?

Most programs organized around data

Making data the focus is the good fit

Objects leverage analogy to real world

Time, Stack, Event, Message, etc…

Abstraction clears away details

Can focus on other tasks

Encapsulation provides robustness

Object intervals can be kept private and secure

Modularity in development

Design, Develop, Test classes independently

Potential for reuse

Class is tidy package that can be re-used in other programs

Source: Programming Abstractions, Julie Zelenski

Abstract Data Types

Client uses class as abstraction

  • Invokes public operations only
  • Internal implementation not relevant

Client can’t and shouldn’t muck with internals

  • Class data should private

Imagine a wall between client and implementator

  • Wall prevents either from getting involved in other’s business
  • Interface is the “chink” in the wall
    • Conduit allows controlled access between the two

Consider Lexicon

  • Abstraction is a word list, operations to verift word/prefix
  • How does it store list? using array? vector? set? does it matter or client?

Why ADTs?


Client insulated from details, works at higher-level


Internals private to ADT, not accessible by client


Seperate tasks for each side (once agreed on interface)


ADT implementation can be changed without affecting client

Source: Lecture 18: Programming Abstractions, Julie Zelenski

The three pillars of OOP

  • Encapsulation
  • Inheritance
  • Polymorphism

Classes and Objects

A class is a user defined abstract data type that further expands upon the concept of a structure but instead of containing just data, it also includes functions.

A class consists of three elements:

  • Identity
    • Name for the class
  • Attributes
    • Data members
  • Methods
    • Function members


class identity {
        members ;
        members ;
        members ;
} objects;

— 2023-07-09


The concept of combining attributes and methods (data and functions), collectively referred to as members, into a single named object / entity.

Access to an object’s attributes should only be controlled by the object itself, and no other object should directly change an attribute of another object.

This concept is known as data hiding.

Interface Vs Implementation

This concept focuses upon separating what an object does from how it does it.