UnorderedList Exercises

An UnorderedList class can be used to implement some of the Abstract Data Types that we've discussed already. For example:

1. List
   We've used Python to create an UnorderedList class, but Python already has a list class. Which implementation is better? You can start your experiment by timing how long it takes, say, to fill up each list with a series of random numbers, and then to remove those numbers from the list.

   More importantly, however, which strategy has the better big-O value? Ie. how does the time that it takes to work with the list vary with the increasing size of a list?

2. Stack
   Write an implementation of a Stack--ULStack--using the UnorderedList class. Recall that a Stack has five methods:

   1. push
   2. pop
   3. peek
   4. size
   5. is_empty

   Once the ULStack has been written, write a StackComparison program that constructs both kinds of stacks--the ULStack implemented with an UnorderedList and a Stack implemented with a Python list--and see which strategy Stack strategy is better.

   Note that this is determined not by finding out which strategy is faster, but by looking at which strategy has the better big-O value.