<< Chapter < Page Chapter >> Page >
In programming, it is often necessary to have objects with which one can store data, retrieve data when needed, and remove data when no longer needed. Such objects are instances of what we call container classes. There are basically two schemes for organizing the objects for storage: a linear scheme and a non-linear scheme. This leads to the notion of container structures. The linear container structure is called a list. The non-linear structure can be sub-classified into many sub-types such as the various tree structures and hash tables, which we will study in subsequent modules. This module focuses on the defining the list structure and designing its implementation.

Going shopping

Before I go to the groceries store, I make a list of what I want to buy. Note how I build my shopping list: I start with a blank sheet of paper then I add one item at a time.

When I get to the store, I start buying things by going down my list. For each item I buy, I mark it off the list.

After I am done shopping, I go to the cashier and check out my items.

The cashier scans my items one item at a time. Each time, the cash register prints one line showing the item just scanned together with its price. Again, note how the cash register builds the list: it start with a blank sheet of paper and then add one item at a time. After all items have been scanned, the cashier press a key and "poof", the cash register prints a subtotal, then a tax amount for all the taxable items, then a total amount, and finally a total number of items bought.

At different store, the cash register not only prints out all of the above, but also a total amount of "savings" due to the fact that I have a "member-plus" card. Some other stores don't care to print the total number of items bought at all. Whatever the store, wherever I go, I see "lists" and "list processing" all over.

The check out cash register uses a program to enter the items and print the receipt. At the heart of the program is a container structure to hold data (data structure) and a few algorithms to manipulate the structure and the data it holds. The simplest way to organize data is to structure them in a linear fashion; that is, intuitively, if we can get hold of one data element, then there is exactly one way to get to the next element, if any. We call this linear organization of data the list structure. In order to write program to process lists, it is necessary to define what lists are and express their definitions in terms of code.

What is a list?

Analogous to the notion of a shape, a list is an abstract notion. Recall how I built my list of groceries items? I started with a blank list: an empty list! The empty set!

An empty list is a list that has no element.

It is obvious that there are non-empty lists. But what do we mean by a non-empty list? How can we articulate such an obvious notion? Consider for example the following list consisting of three elements.

  • milk
  • bread
  • butter

In the above, we organize the items in a linear fashion with milk being the first element, bread being the next element following milk and butter being the next element following bread. Is there any item that follows butter?

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Design patterns. OpenStax CNX. Jun 04, 2009 Download for free at http://cnx.org/content/col10678/1.2
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Design patterns' conversation and receive update notifications?

Ask