Skip to content Skip to navigation Skip to collection information

OpenStax_CNX

You are here: Home » Content » Principles of Object-Oriented Programming » List Structure and the Composite Design Pattern

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • OrangeGrove display tagshide tags

    This collection is included inLens: Florida Orange Grove Textbooks
    By: Florida Orange Grove

    Click the "OrangeGrove" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

  • Rice Digital Scholarship

    This collection is included in aLens by: Digital Scholarship at Rice University

    Click the "Rice Digital Scholarship" link to see all content affiliated with them.

  • Bookshare

    This collection is included inLens: Bookshare's Lens
    By: Bookshare - A Benetech Initiative

    Comments:

    "Accessible versions of this collection are available at Bookshare. DAISY and BRF provided."

    Click the "Bookshare" link to see all content affiliated with them.

Also in these lenses

  • Busbee's Compter Science display tagshide tags

    This collection is included inLens: Busbee's Computer Science Lens
    By: Kenneth Leroy Busbee

    Comments:

    "Texas Common Course Numbering: COSC1337 or COSC1437"

    Click the "Busbee's Compter Science" link to see all content selected in this lens.

    Click the tag icon tag icon to display tags associated with this content.

  • eScience, eResearch and Computational Problem Solving

    This collection is included inLens: eScience, eResearch and Computational Problem Solving
    By: Jan E. Odegard

    Click the "eScience, eResearch and Computational Problem Solving" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

List Structure and the Composite Design Pattern

Module by: Stephen Wong, Dung Nguyen. E-mail the authors

Summary: 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?

Is

  • bread
  • butter

a list?

Is

  • butter

a list?

Is there a list that follows butter in the above?

A non-empty list is a list that has an element called first and a list called rest.

Note that in the above formulation, the rest of a list is itself a list! The definition of a list is an example of what we call a recursive definition: the list contains a substructure that is isomorphic to itself.

List Design and the Composite Design Pattern

The UML diagram below captures the recursive data definition of the list data structure.

Figure 1: A list can be represented using the composite design pattern
UML diagram of a list
UML diagram of a list (graphics1.png)

This definition translates into Java code as follows.

Table 1

/**
* Represents the abstract list structure.
*/
public interface IList {
}
                

/**
* Represents empty lists.
*/
public class MTList implements IList {
}
                

/**
* Represents non-empty lists.
*/
public class NEList implements IList {
    private Object _first;
    private IList _rest;
}
                

The above is an example of what is called the composite design pattern. The composite pattern is a structural pattern that prescribes how to build a container object that is composed of other objects whose structures are isomorphic to that of the container itself. In this pattern, the container is called a composite. In the above, IList is called the abstract component, MTList is called the basic component and NEList is called the composite. The composite design pattern embodies the concept of recursion, one of the most powerful thinking tool in computing. (There is a subject in theoretical computer science and mathematics called "recursive function theory," which studies the meaning of what computing means and in effect defines in the most abstract form what a computer is and what it can and cannot do.)

List Creation

Now that we have defined what a list is, we ask ourselves how we can process it? What can we do with a list? The above code makes it clear that there is not a whole lot we can do with a list besides instantiating a bunch of MTList objects via the call new MTList() (why?). Now that we are using the full Java language, we need to write a constructor for NEList in order to instantiate non-empty list objects with appropriate first and rest. The Java code for NEList now looks as follows (note how the comments are written).


  /**
  * Represents non-empty lists.
  */
  public class NEList implements IList {
     private Object _first;
     private IList _rest;

     /**
     * Initializes this NEList to a given first and a given rest.
     * @param f the first element of this NEList.
     * @param r the rest of this NEList.
     */
     public NEList(Object f, IList r) {
        _first = f;
        _rest = r;
     }
  }
      

The list structure as coded in the above is completely encapsulated, that is, all internal components (if any) of a list are private and cannot be accessed by any external code. Using the appropriate constructors, we can make a bunch of lists to store data but we cannot retrieve data nor do anything with these lists. In Object-Oriented Programming (OOP) parlance, the list is said to have no behavior at all. As such they are of no use to us.

List Processing

In order to perform any meaningful list processing at all, we need to program more "intelligence" into the list structure by adding appropriate methods to the list to provide the desired behaviors. So instead of asking what we can do with a list, the right question to ask in OOP is "what can a list do for us?" Let us start by presenting a few simple tasks that we want a list to perform and try to figure out how an "intelligent" list would carry out such tasks via some role acting.

In class role-acting exercises:

  • Compute the length of a list.
  • Compute the sum of a list that holds integers.

Collection Navigation

Content actions

Download:

Collection as:

PDF | More downloads ...

Module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks