# CS210 Lab: Unsorted Lists

## 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:
• lists of student records
• lists of things to do
• lists of points (used in computer graphics to represent lines, curves, edges, and so forth).
• lists of football statistics over a playing season

### 1.2 Typical Operations of an Unsorted List

The following are some general purpose list functions.
• bool isEmpty()
Returns true if a list is empty. Otherwise, returns false.
• bool isFull()
Returns true if a list is full. Otherwise, returns false.
• void insert (DataType &newDataItem)
Inserts newDataItem into a list, after the cursor. Moves the cursor to newDataItem
• void remove()
Removes the data item marked by the cursor.
• void replace(DataType &newDataItem)
Replaces the data item marked by the cursor with newDataItem.
• void clear()
Removes all the data items in a list
• void showStructure()
Outputs the data items in the list. This operation is intended for testing/debugging purposes only.
• void gotoBeginning()
If a list is not empty, then move the cursor to the data item at the beginning of the list.
• void gotoEnd()
If a list is not empty, then move the cursor to the data item at the end of the list.
• bool gotoNext()
If the cursor is not at the end of the list, then moves the cursor to the next data item in the list and returns true. Otherwise, returns false.
• bool gotoPrior()
If the cursor is not at the beginning of the list, then moves the cursor to the preceding data item in the list and returns true. Otherwise, returns false.
• DataType getCursor()
Returns a copy of the data item marked by the cursor

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:

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.

• You will notice that some of the code has lines like this
```   if ( size >= maxSize )
throw logic_error("list is full\n");
```
Don't worry too much about it right now, it will be discussed in a later lab. Recognize for now, that this is part of an exception handling mechanism. For instance, in the above code segment (from the insert function), it checks to make sure that you are not going over the bounds of your array size. If you try to go over the maximum size, this statement will "throw an exception" indicating that your list is full. In the main program (test3.cpp), there are some try and catch statements to deal with this thrown exception.

• Lists can be of different types. For instance, in our above examples, the list was made up of single characters. The list might also contain integers, strings, floating-point numbers and so on. We could just change the types everytime we wanted to use them. A simpler approach is to use a made up data type name throughout the class, such as DataType and then use the C++ typedef statement at the beginning of the class declaration file to specify what DataType really is. For instance, to specify that the list of data items should be characters, you would type:
``` typedef char DataType
```
This makes DataType a type that is synonymous with char, and can be used in declarations just as other types are used. For instance,
```DataType mychar;
```
Declares a variable, called mychar, of type DataType (really char).

• You can implement a list in many ways. If you are using an array (like we are), it is good to decide if you want to declare the size of the array at compile-time, or be more flexible and specify the size at run-time and dynamically allocate the memory required to store it. If we declare it at compile-time, we use a statement like the following:
```DataType mylist[100]
```
This sets the array to have a length of 100. This means that for the entire program, our array (or list) will always have 100 elements. What if we want some lists to have 100 and some lists to have 50? Then, we can dynamically-allocate memory. We can do this using List's constructor, and the new operator. The constructor is invoked whenever a list declaration is encountered during the execution of a program. For instance let's look at a segment of List's constructor:
```List:: List ( int maxNumber )
{
. . .
dataItems = new DataType[maxSize];
}
```
This allocates an array of maxSize data items and assigns the address of the array to the pointer dataItems, where dataItems is of type DataType *. Whenever you allocate memory, you must ensure that it is deallocated when it is no longer needed. You can use the destructor to deallocate memory stored in the array. The destructor is automatically invoked whenever a list is destroyed. The destructor outlined below frees the memory used by the array that you allocated above.
```List:: ~List ()
{
delete [] dataItems;
}
```
Now, when you declare a list, you can specify the size in parenthesis. For instance, a list of eight elements would be declared in the following way:
```List testList(8);
```
• A final thing that you may have noted is the following code:
```cout << endl <<"Not finished yet but...";
system("pause");
```
When you try the program, you will notice that it prints:
```Not finished yet but...Press any key to continue . . .
```
The Press any key to continue . . . is generated through the call to pause. Without getting into details, it "pauses" the main routine at the current location and waits for keyboard input. After it gets keyboard input, it will continue executing the remaining code in "main". If you have time, you can try commenting these lines out or add additional ones to see what happens.

## 4. Lab Exercise

• Get the files:
```Click here
To get the zipped files for this exercise
```
• Extract all of the files to the WORKAREA. Open the WORKAREA and double click on UnSortedList.sln. This will open up the project. There are three files used in this program:
• listarr.cpp and listarr.h -- contain the array implementation of lists class
• test3.cpp -- the main program. This contains the code to test the working of the list's member functions. Right now, the code is a skeleton of what you should test.

Your primary tasks for this exercise are to edit the listarr.cpp and test3.cpp files to add in lines so that it does the following:

1. test the insert, replace, remove, clear, showStructure and cursor operations: gotoBeginning, gotoNext, and getCursor.
2. add code to implement the find member function described in Section 2.
3. add code to test the find member function.

Steps include:

• Run the executable, see what it currently does.

• Right now, test3.cpp is just skeleton code with comments. Add in the appropriate function calls according to the comments in the code. (up to ****Testing the find*****)

• The output will look something like the following: Numbers in the first row indicate the index, and the letters are the inserted data.
```*****Printing List to Start with*****
Empty list

*****Trying 4 insert statements******
size = 4   cursor = 3
0       1       2       3       4       5       6       7
a       b       r       p

*****Replacing 'b' with 'c'*****
size = 4   cursor = 1
0       1       2       3       4       5       6       7
a       c       r       p

*****Adding a 'u' to the end*****
size = 5   cursor = 4
0       1       2       3       4       5       6       7
a       c       r       p       u

Not finished yet but...Press any key to continue . . .

*****Removing the second last character*****
size = 4   cursor = 3
0       1       2       3       4       5       6       7
a       c       r       u

*****Inserting 'y' after the second character*****
size = 5   cursor = 2
0       1       2       3       4       5       6       7
a       c       y       r       u

*****Printing using cursor*****
acyru
*****Clearing the list*****
Empty list

*****Testing the find*****
Press any key to continue
```

• Add code to implement the find operation in listarr.cpp. The prototype for this operation is included in the declaration of the List class in the file listarr.h

• Add code (in test3.cpp to test this new function). Base this code on the Test Plan below.

• Build and run the executable (seeing if the test cases work). If you discover mistakes in your implementation of the find operation, correct them and execute your test plan again.

The output might look something like this:

```*****Testing the find*****
found a at position 0
found a at position 4
found b at position 1
didn't find b the cursor is 4
found c at position 2
found c at position 3
Press any key to continue
```

Test plan:
Test Case Commands Expected Result Checked
Set up list testList.insert('a');
testList.insert('b');
testList.insert('c');
testList.insert('c');
testList.insert('a');
a b c c a
Successful Search testList.gotoBeginning();
testList.find('a');
returns true;
a b c c a

Search for duplicate testList.gotoNext();
testList.find('a');
returns true;
a b c c a

Successful Search testList.gotoBeginning();
testList.find('b');
returns true;
a b c c a

Search for duplicate testList.gotoNext();
testList.find('b');
returns false;
a b c c a

Successful Search testList.gotoBeginning();
testList.find('c');
returns true;
a b c c a

Search for duplicate testList.gotoNext();
testList.find('c');
returns true;
a b c c a

Note: The data item marked by the cursor is shown in bold. This testing is not extensive.