CS 455 Lecture Notes

Week Four, Tuesday: Container Classes

Properties of Containers

Various types of containers are useful in programming. Among them are:

Set (no duplicates, no order)
Bag (duplicates, no order)
List (duplicates, order)

The list container is also sometimes called a "sequence." These container abstract data types (ADTs) are conceptually utilized independently of their implementations. While the details of their implementations are important for computational analysis, they are not necessary for the logical design of a program. The first versions of these ADTs that we examine will use array implementations. Later versions will use "linked list" implementations.

The Bag

Suppose you are a coin collector specializing in Lincoln Head pennies. One way to build your collection is to go to the bank and get a hundred dollar's worth (10,000) pennies and carry them home in a canvas bag. Then you pull them out one at a time and check to see if you have each one in your collection. If not, put the penny in the collection (a set). If you have the penny already, examine the pair to see if the new one is in better condition. If so, replace the penny in the collection and put the old one in a second bag to return to the bank. If not, put it in the second bag.

Call the above process the "penny collector's algorithm." It uses three data containers: One bag for taking pennies from the bank, a set to hold the collection itself, and another bag for returning the pennies not added to the collection to the bank. If this algorithm is repeated often enough (assuming there is always some probability of finding each date and mint of penny), eventually the penny collection will be complete and you can move on to collecting nickels.

Now suppose that you find this manual process tedious so you build a robot to do it for you. You give the robot X-ray vision so it can see the contents of the penny bag all at once. You could write a program that would tell you instantly how many coins of each date are in the bag. Or you could query the robot: "Do you have any 1909 S pennies?" "Yes, there are six in the bag."

Bag Functions

Insert item into the bag.
Remove item from the bag.
Put the contents of an entire bag into another bag.
Find out how many items are in the bag.
Find out how many of one type of item are in the bag.

With a bag, we know only the number of items of a specific type that are stored in the bag, not where they are stored. "Location" in a bag has no meaning (from the user's viewpoint).

The List

A list keeps and allows access to information about the sequential ordering of its contents.

List Functions

Find the size of the list.
Move to the start of the list.
Advance through the list.
Remove the current item in the list.
Insert an item before (or after) the current position in the list.
Read the current item in the list.

This page established September 19, 1999; last updated September 19, 1999.