Introduction to ADTs

Tom Kelliher, CS23

Feb. 21, 1996

Modularity for the 1,000th Time

Imagine:

  1. Large team project to create, prove, develop product
  2. Fiefdoms
  3. Proof of concept prototype
  4. Re-write for time/space efficiency before shipping

What can go wrong?

How can these problems be addressed?

Abstract Data Types (ADTs)

A collection of data together with a set of operations on that data.

Interface/Implementation (data structure)

ADT examples:

The List ADT

A list is a collection of ordered items

ADT List Operations

  1. CreateList()
  2. DestroyList()
  3. ListIsEmpty()
  4. ListLength()
  5. ListInsert(newPosition, newItem, success)
  6. ListDelete(position, success)
  7. ListRetrieve(position, dataItem, success)

List Parameters???

Pre- Post-Conditions

Have we specified a data structure (implementation)?

Behavioral specification

Example:

List l;
dataItem d;

l.CreateList();
l.ListInsert(1, bread, success);
l.ListInsert(2, butter, success);
l.ListInsert(3, jam, success);
l.ListInsert(4, toaster, success);
l.ListRetrieve(2, d, success);
l.ListDelete(2, success);

Building on ADT List

Without knowledge of the implementation:

  1. Write a display function
  2. Write a multiple insert function
  3. Delete all items and destroy entire list
  4. Build other ADTs from ADT List:
    1. Sorted list
    2. queue
    3. stack

Example: ADT Sorted List Operations:

  1. CreateSortedList
  2. DestroySortedList
  3. SortedListIsEmpty
  4. SortedListLength
  5. SortedListInsert(newItem, success)
  6. SortedListDelete(item, success)
  7. SortedListRetrieve(position, dataItem, success)
  8. LocatePosition(anItem, position, success)

ADT Design Examples

  1. Set
  2. Matrix
  3. String
  4. Terry Winograd developed a program called SHRDLU that was intended to model a simple ``world'' consisting of children's blocks of various shapes and colors. Among other things, SHRDLU was designed to simulate manipulation of the blocks by picking them up and placing them elsewhere. Design ADT block operations.


Thomas P. Kelliher
Tue Feb 20 13:20:01 EST 1996
Tom Kelliher