# Class 16: Association lists

Back to Pairs and pair structures. On to Vectors.

Held Wednesday, September 20, 2000

Summary

Today we visit a database-like application of Scheme: Association lists. Association lists allow you to associate information with a ``key'' and then look up the value by the key.

Notes

• Lab: Association lists
• A reminder: There is almost always a link to the current lab at the top of the current day's outline.
• Another reminder: You can certaionly come to see me when you need help
• I haven't had many visitors, so I'm not sure if you're all getting the material well or ...
• I'll be in the office until about 2:45 today (I'm picking up my son after school) and most of the day tomorrow.
• As I hinted at in the reading on association lists, there will be a quiz today.

Overview

• Databases
• Association lists
• Sequential search

## Simple Database Problems

• Databases are among the most common applications of computers.
• After all, there's a reason that Larry Ellison is nearly as rich as Bill Gates.
• At the simplest level, a database is a mechanism for storing data so that you can easily access the data you need.
• Simple databases in which you can associate a value (or values) with a particular key are called dictionaries.

## Association Lists

• In Scheme, dictionaries are typically implemented with a data structure known as the association list.
• An association list is simply a list of (key,value) pairs.
• You can use the `(assoc key list)` procedure to look up values by key.

## Searching in Association Lists

• Suppose Scheme didn't include `assoc`. How would you write it?
• Probably recursively.
• If the list is empty, it does not contain the value.
• If the key of the first pair in the list is the key, return the corresponding value.
• Otherwise, look in the rest of the list.
• This technique is called sequential search.
• We'll turn that into Scheme together.

## History

Thursday, 24 August 2000

• Created as a blank outline.

Back to Pairs and pair structures. On to Vectors.

Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.