Data Structure Fundamentals

Data Structure Fundamentals

1. Data Type

   • domain of values
   • common data representation
     • e.g. binary
   • set of applicable operations

2. Abstract Data Type (ADT)

   • not concerned with data representation
   • 'specification'
     • 'contract' between ADT implementer and application programmer
   • many advantages
     • simplicity: abstraction separates essential qualities (data and operations) from inessential qualities (representation and implementation)
     • integrity: limiting operations to prevent users from perform operations which might destroy data integrity
     • implementation independence: can be implemented using any programming language
     • encapsulation: client applications can only manipulate data through well defined interfaces
   • Collection ADTs
     • consists of 0 or more elements
       • at least operations to add and remove elements

3. Data Structure

   • concrete implementation of an ADT