Class 32: Introduction to Lists

Held Wednesday, October 25, 2000

Summary

Today we consider the list ADT.

Notes

• Are there any final questions on exam 2?
  • One of you noted that C&C used 1 as the lower bound in one of the recursive calls to binary search. Yes, they should have used 0.
• I'm still thinking about appropriate applets for you to work on. I may leave it relatively open ended. Games are one possibility.
  • Adam: reminder to send me the URL of the Java tailgunner applet.
  • A sillier possibility is something that turns a picture into so-called "ASCII art".
• I'm still working on updating the syllabus.
• Juice and donuts today.

Overview

• Review: ADT and Data Structure
• Ad-libbed example: Integers
• What is a list?
• What is a Scheme list?

Abstract Data Types and Data Structures

• ADTs provide a model for the organization of some of the data in a program.
• Key aspects of ADTs:
  • The name. Tries to reveal something about the use.
  • The structuring principle. For example, "a collection that we index by name"; "a collection that grows".
  • Applications of the ADT.
  • Methods
• In Java, we represent ADTs as interfaces.
• Data structures provide implementations of ADTS.
• Key aspects of ADTs:
  • Structuring principle.
  • Implementations of methods.
  • Efficiency of methods.

The Design of Lists

I'm planning to use a somewhat different format for the rest of today's class.

• First, each of you will give a short summary of the lists described in your book.
• Next, we'll go around the room building a table of
  • constructors,
  • extractors, and
  • modifiers.
• Yes, I'll call you to the board.