Data Structures & Algorithms Lecture Notes

10 September 2010 • Classes and Abstract Data Types

---

Outline

• Arrays
• Classes
• Abstract Data Types.
• Classes and Abstract Data Types.

Array Definition

• An array is a sequence of element values.
  • Each element has type T (arrays are homogeneous).
  • An array of T (or a T array).
• The sequence size is fixed at n ≥ 0.
  • An n-element T array.
• Elements in an n-element array are indexed by the integer set { 0, ..., n - 1 }.
  • What about 0-element arrays?

Array Properties

• Fast and efficient to implement and use.
  • Decades of hardware optimization.
  • Heap-allocated arrays tend to blunt this property.
• A simple and uniform cost model.
  • Arrays provide constant-cost random access.
  • a[0] vs a[1000000].
  • Little or no space overhead.
• Invalid indexes (e.g., -1) raise exceptions.

Array Operations

• Element access via the [ ] operator.
  • primes[i] = numbers[j]
• Determine array size via the length field.
  • final int n = primes.length
• Traverse the elements in order (0 to n - 1).
  • for (int p: primes) f(p)
• See the Arrays class for lots more.
  • Copying, sorting, searching, converting, …

Array Example

int [] collapse(int a[], int x)

  // Suppress runs of x in a.
  // collapse([0,0,1,1,0,0,0], 0) = [0,1,1,0]

  final int n = a.length
  int cpy [] = new int [n]
  int next = 0, i = 0

  while (i < n)
    cpy[next++] = a[i]
    if (a[i++] == x)
      while ((i < n) && (a[i] == x))
        i++

  return Arrays.copyOf(cpy, next)

See the code

Classes

• A class is a collection of data (state) and operations on the data.
• Class declarations have the form

  class: [ modifiers ]? class ClassName [ modifiers ]? 
    { [ declaration ]* }
    
  declaration: 
    instanceVariable | method | constructor
  

• As in C++, there is no need to declare class components before use.
  • Declarations may be ordered as desired.

Class Example

class AnArray {

  // blah blah blah

  }

Methods

• A class may have zero or more methods representing operations or actions.
• Method declarations have the format

  method: [ modifiers ]? returnType
           methodName ( [ arguments ]?  ) { ... }
  
  arguments: argument [ , argument ]*
  
  argument: [ modifiers ]? type argumentName
  
  

• Conventionally, a method name is camelCase with a lower-case first letter.

Method Example

class AnArray {

  void put(int i, int e) { ... }
  int get(int i) { ... }

  }

Constructors

• A constructor is a special method that creates class instances.
• Constructor declarations have the format

  constructor: 
    [ modifiers ]? ClassName ( [ arguments ]? ) {...}
  
  

  • There’s no return type and the method name is the class name.

Default Constructors

• Every class must have at least one constructor.
• A class without an explicitly declared constructor gets a default constructor.
  • It accepts no arguments and does nothing.
• Explicitly declared constructors inhibit the implicit default constructor.
  • Unlike C++, this is usually not a problem.
  • Explicitly declare a default constructor if it is.

Instance Variables

• A class may have zero or more instance variables representing model state.
• Instance variable declarations have the format

  instanceVariable: 
    [ modifiers ]? type variables ;
  
  variables: variable [ , variable ]*
  
  variable: variableName [ = initializer ]?

• Conventionally, a variable name is camelCase with a lower-case first letter.

Instance-Variable Example

class AnArray {
  void put(int i, int e) { ... }
  int get(int i) { ... }

  private int size;
  private int elements [];
  }

Class-Component Access

• A class’s non-constructor methods and instance variables (collectively known as the class’s fields) are accessed using dot notation:

  classInstance.fieldName

• Unlike C++, the only reason to access a Java class method is to call it.

  classInstance.methodName(arg, ...)

Instance Variable Initialization

• Java requires that every variable always contain a defined value.
  • “Defined” does not mean “sensible”.
  • It means (among other things) non-garbage.
• When instance variables are created, they have to be initialized to obey this property.
  • The compiler helps you maintain this property.

Default Initialization

• Instance variables without explicit initialization receive a default value at class-instance creation.

  class AnArray {
  
    // blah blah blah
  
    private int size;
    private int elements[];
    }
  

• The default value depends on variable type.

Explicit Initialization

• Explicitly-initialized instance variables receive the computed value.

  class AnArray {
  
    private int size = 0;
  
    // and so on.
    }
  

• The initialization value is computed at each instance creation.

Constructor Initialization

• Instance variables can also be initialized in constructors.

  class AnArray {
  
    AnArray(int n) {
      size = n;
      elements = new int [n];
      }
  
    private int size;
    private elements[];
    }

Abstract Data Types

• An abstract data type (ADT) is also a collection of data and operations on the data.
• An ADT defines a strong partition between accessible and inaccessible components.
  • All components are accessible within an ADT.
  • Only selected components are accessible outside the ADT.
    • Accessible by the ADT’s client.
  • “Strong” means compiler supported.

ADT Interfaces

• An ADT interface defines the partition between accessible and inaccessible components.
• The interface lists all the operations accessible outside the ADT.
  • Operations not listed in the interface are inaccessible outside the ADT.
  • Everything else not listed by the interface is inaccessible too.
    • In particular, data is inaccessible outside the ADT.

ADT Operators

• ADT interface operators divide into:
  1. Query operators: read-only operators that answer questions.
     • Examples: size(), find(), isEmpty().
  2. Manipulation operators: read-write operators that manipulate state.
     • Examples: add(), remove(), sort().
  3. Maintenance operators: read-write operators that change the ADT itself.
     • Examples: new(), free(), resize().

ADT Example

Classes and Abstract Data Types

What’s the difference? Why have both?

• ADTs are a concept; classes are an implementation.
• ADTs provide stronger access guarantees than do classes.
• ADTs got there first, but didn't win the race.
• ADTs are simpler than are classes (no inheritance).

ADTs are of objects, but are not objects.

What An Array Can Do

• What operations does an array support?
  • Maintence: create(), free(), resize(), ...
  • Query: get(), size(), ...
  • Manipulation: put(), swap(), ...
• There's no information about how the array is implemented, just how it behaves.
  • That is, the operations it supports.

An Array ADT

class ArrayADT {

  ArrayADT(int n) { ... }
  void resize(int n) { ... }

  int get(int i) { ... }
  int size() { ... }

  void put(int i, int, v) { ... }
  void swap(int i, int j) { ... }

  // and so on.
  }

Summary

• Classes group data and data operations into an organized unit.
• An abstract data type also groups data and data operations into an organized unit.
  • But with stronger, simpler organization then that of classes.
• Abstract data types are a concept; classes are an implementation.

References

• On Understanding Data Abstraction, Revisited by William Cook, OOPSLA 2009.

---

This page last modified on 10 September 2010.