CMIS 240

Week 8

A stack is a simple kind of list, so it's an easy data structure to
use to learn about linked lists.  Remember that a linked list is at
the implementation-level.  A stack is at the logical-level.  A stack
can be implemented with an array or with a linked list.

A linked list has two benefits.  One is that there is no fixed upper
limit on its size (i.e. number of elements).  An array, even a
dynamically allocated one, has a size limit.  If you need to use more
elements than exist in the array, you're out of luck; you're stuck
with its declared size (of course you could create another, larger
array, copy the data from the current one to the new one and then use
the new one, but that's not only a bother, there might not be enough
memory to accomodate two large arrays simultaneously).  A linked list
can grow as much as needed, conceptually without limit, but in
practice limited by the size of the heap (free store).  The second
benefit of a linked list is that there is no "wasted" memory, that is,
space for unused elements as there is in an array with elements that
aren't used.  Since a linked list only allocates space for elements
that is needs, and returns to the heap elements deleted from the list,
no space is wasted.

The drawback of a linked list is that it is limited to sequential
access.  To access an element, you have to start at the beginning of
the list and traverse it until you reach the desired element.  An
array is "random" access, meaning any element can be accessed in the
same speed as any other.  An array can also be sequentially accessed,
and a lot of processing only requires sequential access.

Concentrate on the stack and unsorted list sections of Chapter 5. 


----------------------------------------

Homework Due: 10 Nov.

To give you some practice with linked list code, add two member
functions to the templated, linked list UnsortedType list class of
chapter 5.  The prototypes of the functions are:

    void FindMax(ItemType& item);
    //Gets the largest element in list.
    //Pre: list is not empty
    //Post: item is copy of largest value in list.

    void Reverse();
    //Reverses the order of the elements of the list
    //Post: list elements have been reversed.  what was first is now last,
    //what was second is now second-to-last...,what was last is now first.
    //listData points to what was last and is now first, or NULL if
    //list is empty.


Use the UnsortedType.h and UnsortedType.cpp files in
Chapter5/UnsortedType/ of the class web site.  
Use the unsorteddr.cpp driver program with the comments removed to
test your functions.
Allow multiple copies of the same value to be in the list (i.e. remove
the pre-condition of the InsertItem function that says that the item
is not in the list).  Change the DeleteItem function so that it works
if the requested item to delete is not in the list, in that case doing
nothing.  The Reverse function must work directly on the linked list,
you are not allowed to use a stack or an auxiliary array (this forces
you to do some linked list manipulation).

Submit your UnsortedType.h and UnsortedType.cpp files zipped as one
file.  Do not submit a driver program.  I will use my unsorteddr.cpp
with the comments removed as the driver.