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?

• Procedural abstraction --- what, not how
• Information hiding
• Data abstraction

Abstract Data Types (ADTs)

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

• Simula68
• Objects
• Object oriented programming

Interface/Implementation (data structure)

ADT examples:

• Integers
• Complex numbers
• The factorial of a number
• Matrices
• A chair
• An automobile
• A CD collection (classical vs. rock)

The List ADT

A list is a collection of ordered items

• Head
• Tail
• Successor, predecessor
• Order
• Items
• Insertion/deletion semantics --- yield different ``lists:''
  • Anywhere --- list
  • Insert at tail, delete at head --- queue
  • Insert, delete at head --- stack

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.