A Simple Implementation
Last updated
Last updated
Like lists, a table is an abstract data type. That is, it describes what it is but not how to implement one. The underlying data structure needed to create a table can vary widely from arrays sorted by keys, hash tables and even trees.
A simple implementation is to simply use an array sorted by keys.
To add to this table, we must first find the spot where the item will go. This can be done by modifying a binary search algorithm. Once the location is found, if a record with the same key is not already in the table, we will need to shift every item over to make room for the new record. If a record with a matching key already exists, the old record can be replaced with the new.
The run time for performing the search is O(log n). If the record already exists, and we are just updating it, the run time would be O(log n). However, inserting a brand new record with a different key will require shifting on average 50% of the list, and thus we are looking at a run time of O(n) for that operation.
To remove a record, we can start with a binary search algorithm to find the record according to the key. If such a record exists, removal will involve shifting the records down.
The run time for search is O(log n). However to remove, we must shift all the records down. This process is O(n). Thus the remove operation is O(n)
As the array is sorted by key, all searching can be done using a binary search. This has a run time of O(log n)
This implementation clearly has a lot of drawbacks. While the search() function has an acceptable run time of , the other functions are generally slow. The only part that is fast is search. Ideally it would be faster than this.