Abstract Data Types

Abstract Data Types
An Introduction

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Abstract Data Types

Defined:
1. The set of possible values that an instance can take (i.e., the domain or carrier set); and
2. The set of allowable operations on its instances
An Observation:
- Each ADT can be implemented in more than one way

Implementation of an ADT

Defined:
1. A realization in computer memory (called a data structure) of the values; and
2. An executable realization of a mechanism (called an algorithm) for performing each of the operations
An Observation:
- In an object-oriented language, an ADT is usually implemented as a class

Data Structures

Contiguous Implementations:
- Values are stored in adjacent memory locations
Linked Implementations:
- Values are "connected" using pointers or references
- Note: Many books call these "linked list" implementations. This is inappropriate since a "list" is an ADT and, hence, a "linked list" is a particular way of implementing a "list".
A Physical Analogue:
- A warehouse containing outgoing orders

Contiguous Implementations

Linked Implementations

The Components:
Types of Nodes:
- Endogenous - Data is in the node
- Exogenous - Data is pointed to by the node

Linked Implementations (cont.)

Single, Linear (Endogenous)

Double, Linear (Endogenous)

Linked Implementations (cont.)

Single, Circular (Endogenous)

Double, Circular (Endogenous)

Linked Implementations (cont.)

Binary Tree (Endogenous)

Linked Implementations (cont.)

One Observation:
- All linked structures can be studied using ideas from graph theory
Another Observation:
- Networks/Graphs are the most general
- Trees are special cases of networks/graphs
- Linear structures are special cases of trees