CS210 Lab: Unsorted Lists


Prelab Questions:

For a review of relevant topics click here.

Highlights of This Lab:

Lab Exercise:


Click the little computer above for a detailed description.
For this excercise you will be asked to implement a function that Finds a particular data item

1. Definition of a List

Lists are everywhere. We make grocery lists, lists of things to do, lists of addresses, lists of party guests.

"From a theoretical point of view, a list is a homogeneous collection of elements, with a linear relationship between elements. Linear means that, at the logical level, each element in the list except the first one has a unique predecessor, and each element except the last one has a unique successor."
(C++ Plus Data Structures, page 196)

To summarize, a list has one element before it, and one element after it. With the exception of the first and last elements.

There are two different kinds of list:

  1. Unsorted--In these lists, there is no particular order
  2. Sorted--In these lists, there is some predefined order. For instance, you can have a list of names that are sorted alphabetically, or you can have a list of grades that are sorted numerically.

This lab focuses on the unsorted list, based on an array implementation.

A list whether sorted or unsorted should have a set of general purpose operations. These operations are listed in Section 1.2.

1.1 Applications of a List

There are too many applications of a list to "list" here. A few examples might be the following:

1.2 Typical Operations of an Unsorted List

The following are some general purpose list functions.

Note: The last five functions (gotoBeginning(), gotoEnd(), gotoNext(), gotoPrior(), and getCursor()) are relevant to the cursor. They allow you to iterate through the entire list--processing it item by item. This gives the user access to each item in sequence.

1.3 Pictorial Examples of these Functions

The operations are above, but what do they mean? Let's give some examples with pictures:

operations representation comments
testList.insert('a');
testList.insert('b');
testList.insert('r');
testList.insert('p');
    Notice, the cursor is positioned at the last item added, and the list is not in alphabetical order (it is unsorted).
testList.replace('c'); Notice that the cursor is at 3 and the 'p' (previously at index 3) has been replaced by 'c'.
testList.insert('u'); The 'u' is added to the end. The size and cursor are incremented.
testList.gotoBeginning(); testList.remove(); The cursor has been moved to the beginning (with gotoBeginning). Now, notice that since the cursor is at 0, the 'a' is removed. All the other elements are shifted "up" the array.
testList.gotoNext(); testList.insert('y'); With gotoNext(), the cursor moves to position 1 ('r'), Then the insert occurs after the cursor position. The cursor then points at 'y'.

To cycle through the list and print each item, we can make use of the cursor as an iterator. To do this we use a while statement and use the getCursor() function to get the data at the present cursor position. The code will look like this:

testList.gotoBeginning();
cout << testList.getCursor() << endl;
while (testList.gotoNext())
{
	cout << testList.getCursor() << endl;
}	

2. Implementation: Finding an Item in the List

Finding a particular item in a list is another very common function for lists. Later, in the lab exercise, you will be asked to implement this program.

In Section 1.3, we demonstrated the use of the insert, replace, remove and a few of the cursor operations (getCursor(), gotoNext(), gotoBeginning()).

Another function that we might need is a find function. This operation searches a list for a specified data item. The search begins with the data item marked by the cursor (not at the beginning of the list). This is an advantage because find can be applied iteratively to locate all of the occurences of a specified data item.

The prototype will look something like this:
bool find ( const DataType &searchDataItem ) throw ( logic_error )
The function will search through a list for searchDataItem. It begins the search with the data item marked by the cursor. It moves the cursor through the list until either searchDataItem is found (returns true) or the end of the list is reached without finding searchDataItem (returns false).

Note: It leaves the cursor at the last data item visited during the search.


3. Coding Details

First, let's describe some of details of the program. You won't need to change any of these components (unless we specify that you do), but they are good things to know for comprehending this and future code.


4. Lab Exercise