*************************************************************
*   Answer to Project 2:                                    *
*                                                           *
*   CMSC 341 -- Fall 2001 -- Project 2                      *
*   kyu bae xxx-xx-5868, Section 201                        *
*   kyu_bae@yahoo.com / kbae1@umbc.edu                      *
*   Created : 30 September 2001                             *
*   Current : 02 October   2001                             *
*************************************************************
These questions count for 10% of your project grade.


1. (20 points) Discuss the asymptotic performance of your project.
What is the best case big-Oh performance?  Describe the best case.
What is the worst case big-Oh performance? Describe the worst case.

answer:
oOn best case, all of the operations except find(), findPrevious() and remove()
take O(1) time. This is  true because in all cases only a fixed 
number of instructions are performed, no matter how large the 
list is.But for the worst case, they can be O(N).
For find() and findPrevious() routines, the running 
time is O(N) in the worst case. because the entire list might 
need to be traversed if the element either is not found or is last
in the list. On the best case the running time is O(1) because
on best case the list must be traversed only 1 element. 

2. (10 points)  The List method findPrevious( ) is no longer needed
by the List class once you have changed it from a singly-linked list
to a doubly-linked circular list.  Explain why this is true.

Answer:
Find(Object & x ) just returns an iterator representing the first
occurrance of X in the list. If not present, the iterator is pastend.
You need findPrev() when you do remove() &  insert().Because you want 
to remove Object x you have to call findPrevious(). You need to
know previous object to use next->next when removing. Also when 
using  insert()  after x node, you have to know previous of  
x. so you want a  pointer pointing previous object. 
findPrevious() gives this pointer.findPrevioud() returns an iterator
representing the element before x in the list. If x is not 
in the list, the iterator represents the last element in 
the list. That is what happend in the singly linked list.
The doubly linked list has previous object stored in a pointer
to the previus Object. That is why you don't need 
findPrevious(). You can access the previous object of X.