In algorithms and data structures I implemented an unsorted unique container class for each of the following:
|Container||Description||Time Average||Time Worst||Space Worst|
|Python List||This is a simple list of items. The simplest type of array data structure is a linear array, also called one-dimensional array. Think of it as a giant filing cabinet drawer. Each item is placed in a folder and placed right behind another, but none of them are sorted. If you have to retrieve an item, each folder must be checked until the item is found.||O(n)||O(n)||O(n)|
|Binary Search Tree or Binary Tree (BST)||In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. (Wikipedia)||O(log(n))||O(n)||O(n)|
|Hash Table or Hash Map||In computing, a hash table (hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array ofbuckets or slots, from which the correct value can be found. (Wikipedia)||O(1)||O(n)||O(n)|
Big O Notation
Big O notation is used to classigy algoritms by how they respond (processing time or working space requirements) to changes in input size. More on big O notation can be found at Big-O Cheatsheet and on Wikipedia's Big O Notation page.
Each class should support these methods: Exists, Insert, Traverse, Delete, Retrieve, and Size. Compare the Insert, Traverse, Delete, and Retrieve times for each container class with the dataset. Each dataset is a text file containing a line of five whitespace separated "student records" with the following fields last name, first name, SSN, email, and age. Here is a sample line from the a data file:
WHITE WALTER 123-45-6789 W.WHITE@NEWMEXICO.ORG 49
There were three different sizes of datasets and only the small file should be used with the Python List container class. Also, for saving time one should create a smaller list of data for testing purposes.
Results using Python 2.7
- All times are listed in seconds.
- Hovering over a bar in histogram will modify the pie chart and legend.
- Hovering over pie slice will update the histogram.