- Forward


Abstract Data Types
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Abstract Data Types
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
array
Linked Implementations
Back SMYC Forward
  • The Components:
    • linked_structure_components
  • Types of Nodes:
    • Endogenous - Data is in the node
    • Exogenous - Data is pointed to by the node
Linked Implementations (cont.)
Back SMYC Forward

Single, Linear (Endogenous)

linked_structure_endogenous_single_linear

Double, Linear (Endogenous)

linked_structure_endogenous_double_linear
Linked Implementations (cont.)
Back SMYC Forward

Single, Circular (Endogenous)

linked_structure_endogenous_single_circular

Double, Circular (Endogenous)

linked_structure_endogenous_double_circular
Linked Implementations (cont.)
Back SMYC Forward

Binary Tree (Endogenous)

linked_structure_endogenous_binary_tree
Linked Implementations (cont.)
Back SMYC Forward
  • 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
There's Always More to Learn
Back -